libstdc++-v3/include/bits/vector.tcc

   1 // Vector implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001-2017 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /*
  26  *
  27  * Copyright (c) 1994
  28  * Hewlett-Packard Company
  29  *
  30  * Permission to use, copy, modify, distribute and sell this software
  31  * and its documentation for any purpose is hereby granted without fee,
  32  * provided that the above copyright notice appear in all copies and
  33  * that both that copyright notice and this permission notice appear
  34  * in supporting documentation.  Hewlett-Packard Company makes no
  35  * representations about the suitability of this software for any
  36  * purpose.  It is provided "as is" without express or implied warranty.
  37  *
  38  *
  39  * Copyright (c) 1996
  40  * Silicon Graphics Computer Systems, Inc.
  41  *
  42  * Permission to use, copy, modify, distribute and sell this software
  43  * and its documentation for any purpose is hereby granted without fee,
  44  * provided that the above copyright notice appear in all copies and
  45  * that both that copyright notice and this permission notice appear
  46  * in supporting documentation.  Silicon Graphics makes no
  47  * representations about the suitability of this  software for any
  48  * purpose.  It is provided "as is" without express or implied warranty.
  49  */
  50
  51 /** @file bits/vector.tcc
  52  *  This is an internal header file, included by other library headers.
  53  *  Do not attempt to use it directly. @headername{vector}
  54  */
  55
  56 #ifndef _VECTOR_TCC
  57 #define _VECTOR_TCC 1
  58
  59 namespace std _GLIBCXX_VISIBILITY(default)
  60 {
  61 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  62 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  63
  64   template<typename _Tp, typename _Alloc>
  65     void
  66     vector<_Tp, _Alloc>::
  67     reserve(size_type __n)
  68     {
  69       if (__n > this->max_size())
  70         __throw_length_error(__N("vector::reserve"));
  71       if (this->capacity() < __n)
  72         {
  73           const size_type __old_size = size();
  74           pointer __tmp = _M_allocate_and_copy(__n,
  75             _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start),
  76             _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish));
  77           _GLIBCXX_ASAN_ANNOTATE_REINIT;
  78           std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
  79                         _M_get_Tp_allocator());
  80           _M_deallocate(this->_M_impl._M_start,
  81                         this->_M_impl._M_end_of_storage
  82                         - this->_M_impl._M_start);
  83           this->_M_impl._M_start = __tmp;
  84           this->_M_impl._M_finish = __tmp + __old_size;
  85           this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
  86         }
  87     }
  88
  89 #if __cplusplus >= 201103L
  90   template<typename _Tp, typename _Alloc>
  91     template<typename... _Args>
  92 #if __cplusplus > 201402L
  93       typename vector<_Tp, _Alloc>::reference
  94 #else
  95       void
  96 #endif
  97       vector<_Tp, _Alloc>::
  98       emplace_back(_Args&&... __args)
  99       {
 100         if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
 101           {
 102             _GLIBCXX_ASAN_ANNOTATE_GROW(1);
 103             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
 104                                      std::forward<_Args>(__args)...);
 105             ++this->_M_impl._M_finish;
 106             _GLIBCXX_ASAN_ANNOTATE_GREW(1);
 107           }
 108         else
 109           _M_realloc_insert(end(), std::forward<_Args>(__args)...);
 110 #if __cplusplus > 201402L
 111         return back();
 112 #endif
 113       }
 114 #endif
 115
 116   template<typename _Tp, typename _Alloc>
 117     typename vector<_Tp, _Alloc>::iterator
 118     vector<_Tp, _Alloc>::
 119 #if __cplusplus >= 201103L
 120     insert(const_iterator __position, const value_type& __x)
 121 #else
 122     insert(iterator __position, const value_type& __x)
 123 #endif
 124     {
 125       const size_type __n = __position - begin();
 126       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
 127         if (__position == end())
 128           {
 129             _GLIBCXX_ASAN_ANNOTATE_GROW(1);
 130             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
 131                                      __x);
 132             ++this->_M_impl._M_finish;
 133             _GLIBCXX_ASAN_ANNOTATE_GREW(1);
 134           }
 135         else
 136           {
 137 #if __cplusplus >= 201103L
 138             const auto __pos = begin() + (__position - cbegin());
 139             // __x could be an existing element of this vector, so make a
 140             // copy of it before _M_insert_aux moves elements around.
 141             _Temporary_value __x_copy(this, __x);
 142             _M_insert_aux(__pos, std::move(__x_copy._M_val()));
 143 #else
 144             _M_insert_aux(__position, __x);
 145 #endif
 146           }
 147       else
 148 #if __cplusplus >= 201103L
 149         _M_realloc_insert(begin() + (__position - cbegin()), __x);
 150 #else
 151         _M_realloc_insert(__position, __x);
 152 #endif
 153
 154       return iterator(this->_M_impl._M_start + __n);
 155     }
 156
 157   template<typename _Tp, typename _Alloc>
 158     typename vector<_Tp, _Alloc>::iterator
 159     vector<_Tp, _Alloc>::
 160     _M_erase(iterator __position)
 161     {
 162       if (__position + 1 != end())
 163         _GLIBCXX_MOVE3(__position + 1, end(), __position);
 164       --this->_M_impl._M_finish;
 165       _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
 166       _GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
 167       return __position;
 168     }
 169
 170   template<typename _Tp, typename _Alloc>
 171     typename vector<_Tp, _Alloc>::iterator
 172     vector<_Tp, _Alloc>::
 173     _M_erase(iterator __first, iterator __last)
 174     {
 175       if (__first != __last)
 176         {
 177           if (__last != end())
 178             _GLIBCXX_MOVE3(__last, end(), __first);
 179           _M_erase_at_end(__first.base() + (end() - __last));
 180         }
 181       return __first;
 182     }
 183
 184   template<typename _Tp, typename _Alloc>
 185     vector<_Tp, _Alloc>&
 186     vector<_Tp, _Alloc>::
 187     operator=(const vector<_Tp, _Alloc>& __x)
 188     {
 189       if (&__x != this)
 190         {
 191           _GLIBCXX_ASAN_ANNOTATE_REINIT;
 192 #if __cplusplus >= 201103L
 193           if (_Alloc_traits::_S_propagate_on_copy_assign())
 194             {
 195               if (!_Alloc_traits::_S_always_equal()
 196                   && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
 197                 {
 198                   // replacement allocator cannot free existing storage
 199                   this->clear();
 200                   _M_deallocate(this->_M_impl._M_start,
 201                                 this->_M_impl._M_end_of_storage
 202                                 - this->_M_impl._M_start);
 203                   this->_M_impl._M_start = nullptr;
 204                   this->_M_impl._M_finish = nullptr;
 205                   this->_M_impl._M_end_of_storage = nullptr;
 206                 }
 207               std::__alloc_on_copy(_M_get_Tp_allocator(),
 208                                    __x._M_get_Tp_allocator());
 209             }
 210 #endif
 211           const size_type __xlen = __x.size();
 212           if (__xlen > capacity())
 213             {
 214               pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
 215                                                    __x.end());
 216               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 217                             _M_get_Tp_allocator());
 218               _M_deallocate(this->_M_impl._M_start,
 219                             this->_M_impl._M_end_of_storage
 220                             - this->_M_impl._M_start);
 221               this->_M_impl._M_start = __tmp;
 222               this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
 223             }
 224           else if (size() >= __xlen)
 225             {
 226               std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
 227                             end(), _M_get_Tp_allocator());
 228             }
 229           else
 230             {
 231               std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
 232                         this->_M_impl._M_start);
 233               std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
 234                                           __x._M_impl._M_finish,
 235                                           this->_M_impl._M_finish,
 236                                           _M_get_Tp_allocator());
 237             }
 238           this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
 239         }
 240       return *this;
 241     }
 242
 243   template<typename _Tp, typename _Alloc>
 244     void
 245     vector<_Tp, _Alloc>::
 246     _M_fill_assign(size_t __n, const value_type& __val)
 247     {
 248       if (__n > capacity())
 249         {
 250           vector __tmp(__n, __val, _M_get_Tp_allocator());
 251           __tmp._M_impl._M_swap_data(this->_M_impl);
 252         }
 253       else if (__n > size())
 254         {
 255           std::fill(begin(), end(), __val);
 256           const size_type __add = __n - size();
 257           _GLIBCXX_ASAN_ANNOTATE_GROW(__add);
 258           this->_M_impl._M_finish =
 259             std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
 260                                           __add, __val, _M_get_Tp_allocator());
 261           _GLIBCXX_ASAN_ANNOTATE_GREW(__add);
 262         }
 263       else
 264         _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
 265     }
 266
 267   template<typename _Tp, typename _Alloc>
 268     template<typename _InputIterator>
 269       void
 270       vector<_Tp, _Alloc>::
 271       _M_assign_aux(_InputIterator __first, _InputIterator __last,
 272                     std::input_iterator_tag)
 273       {
 274         pointer __cur(this->_M_impl._M_start);
 275         for (; __first != __last && __cur != this->_M_impl._M_finish;
 276              ++__cur, ++__first)
 277           *__cur = *__first;
 278         if (__first == __last)
 279           _M_erase_at_end(__cur);
 280         else
 281           _M_range_insert(end(), __first, __last,
 282                           std::__iterator_category(__first));
 283       }
 284
 285   template<typename _Tp, typename _Alloc>
 286     template<typename _ForwardIterator>
 287       void
 288       vector<_Tp, _Alloc>::
 289       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
 290                     std::forward_iterator_tag)
 291       {
 292         const size_type __len = std::distance(__first, __last);
 293
 294         if (__len > capacity())
 295           {
 296             pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
 297             _GLIBCXX_ASAN_ANNOTATE_REINIT;
 298             std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 299                           _M_get_Tp_allocator());
 300             _M_deallocate(this->_M_impl._M_start,
 301                           this->_M_impl._M_end_of_storage
 302                           - this->_M_impl._M_start);
 303             this->_M_impl._M_start = __tmp;
 304             this->_M_impl._M_finish = this->_M_impl._M_start + __len;
 305             this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
 306           }
 307         else if (size() >= __len)
 308           _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
 309         else
 310           {
 311             _ForwardIterator __mid = __first;
 312             std::advance(__mid, size());
 313             std::copy(__first, __mid, this->_M_impl._M_start);
 314             const size_type __attribute__((__unused__)) __n = __len - size();
 315             _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
 316             this->_M_impl._M_finish =
 317               std::__uninitialized_copy_a(__mid, __last,
 318                                           this->_M_impl._M_finish,
 319                                           _M_get_Tp_allocator());
 320             _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
 321           }
 322       }
 323
 324 #if __cplusplus >= 201103L
 325   template<typename _Tp, typename _Alloc>
 326     auto
 327     vector<_Tp, _Alloc>::
 328     _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
 329     {
 330       const auto __n = __position - cbegin();
 331       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
 332         if (__position == cend())
 333           {
 334             _GLIBCXX_ASAN_ANNOTATE_GROW(1);
 335             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
 336                                      std::move(__v));
 337             ++this->_M_impl._M_finish;
 338             _GLIBCXX_ASAN_ANNOTATE_GREW(1);
 339           }
 340         else
 341           _M_insert_aux(begin() + __n, std::move(__v));
 342       else
 343         _M_realloc_insert(begin() + __n, std::move(__v));
 344
 345       return iterator(this->_M_impl._M_start + __n);
 346     }
 347
 348   template<typename _Tp, typename _Alloc>
 349     template<typename... _Args>
 350       auto
 351       vector<_Tp, _Alloc>::
 352       _M_emplace_aux(const_iterator __position, _Args&&... __args)
 353       -> iterator
 354       {
 355         const auto __n = __position - cbegin();
 356         if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
 357           if (__position == cend())
 358             {
 359               _GLIBCXX_ASAN_ANNOTATE_GROW(1);
 360               _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
 361                                        std::forward<_Args>(__args)...);
 362               ++this->_M_impl._M_finish;
 363               _GLIBCXX_ASAN_ANNOTATE_GREW(1);
 364             }
 365           else
 366             {
 367               // We need to construct a temporary because something in __args...
 368               // could alias one of the elements of the container and so we
 369               // need to use it before _M_insert_aux moves elements around.
 370               _Temporary_value __tmp(this, std::forward<_Args>(__args)...);
 371               _M_insert_aux(begin() + __n, std::move(__tmp._M_val()));
 372             }
 373         else
 374           _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...);
 375
 376         return iterator(this->_M_impl._M_start + __n);
 377       }
 378
 379   template<typename _Tp, typename _Alloc>
 380     template<typename _Arg>
 381       void
 382       vector<_Tp, _Alloc>::
 383       _M_insert_aux(iterator __position, _Arg&& __arg)
 384 #else
 385   template<typename _Tp, typename _Alloc>
 386     void
 387     vector<_Tp, _Alloc>::
 388     _M_insert_aux(iterator __position, const _Tp& __x)
 389 #endif
 390     {
 391       _GLIBCXX_ASAN_ANNOTATE_GROW(1);
 392       _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
 393                                _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
 394       ++this->_M_impl._M_finish;
 395       _GLIBCXX_ASAN_ANNOTATE_GREW(1);
 396 #if __cplusplus < 201103L
 397       _Tp __x_copy = __x;
 398 #endif
 399       _GLIBCXX_MOVE_BACKWARD3(__position.base(),
 400                               this->_M_impl._M_finish - 2,
 401                               this->_M_impl._M_finish - 1);
 402 #if __cplusplus < 201103L
 403       *__position = __x_copy;
 404 #else
 405       *__position = std::forward<_Arg>(__arg);
 406 #endif
 407     }
 408
 409 #if __cplusplus >= 201103L
 410   template<typename _Tp, typename _Alloc>
 411     template<typename... _Args>
 412       void
 413       vector<_Tp, _Alloc>::
 414       _M_realloc_insert(iterator __position, _Args&&... __args)
 415 #else
 416   template<typename _Tp, typename _Alloc>
 417     void
 418     vector<_Tp, _Alloc>::
 419     _M_realloc_insert(iterator __position, const _Tp& __x)
 420 #endif
 421     {
 422       const size_type __len =
 423         _M_check_len(size_type(1), "vector::_M_realloc_insert");
 424       pointer __old_start = this->_M_impl._M_start;
 425       pointer __old_finish = this->_M_impl._M_finish;
 426       const size_type __elems_before = __position - begin();
 427       pointer __new_start(this->_M_allocate(__len));
 428       pointer __new_finish(__new_start);
 429       __try
 430         {
 431           // The order of the three operations is dictated by the C++11
 432           // case, where the moves could alter a new element belonging
 433           // to the existing vector.  This is an issue only for callers
 434           // taking the element by lvalue ref (see last bullet of C++11
 435           // [res.on.arguments]).
 436           _Alloc_traits::construct(this->_M_impl,
 437                                    __new_start + __elems_before,
 438 #if __cplusplus >= 201103L
 439                                    std::forward<_Args>(__args)...);
 440 #else
 441                                    __x);
 442 #endif
 443           __new_finish = pointer();
 444
 445           __new_finish
 446             = std::__uninitialized_move_if_noexcept_a
 447             (__old_start, __position.base(),
 448              __new_start, _M_get_Tp_allocator());
 449
 450           ++__new_finish;
 451
 452           __new_finish
 453             = std::__uninitialized_move_if_noexcept_a
 454             (__position.base(), __old_finish,
 455              __new_finish, _M_get_Tp_allocator());
 456         }
 457       __catch(...)
 458         {
 459           if (!__new_finish)
 460             _Alloc_traits::destroy(this->_M_impl,
 461                                    __new_start + __elems_before);
 462           else
 463             std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
 464           _M_deallocate(__new_start, __len);
 465           __throw_exception_again;
 466         }
 467       _GLIBCXX_ASAN_ANNOTATE_REINIT;
 468       std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator());
 469       _M_deallocate(__old_start,
 470                     this->_M_impl._M_end_of_storage - __old_start);
 471       this->_M_impl._M_start = __new_start;
 472       this->_M_impl._M_finish = __new_finish;
 473       this->_M_impl._M_end_of_storage = __new_start + __len;
 474     }
 475
 476   template<typename _Tp, typename _Alloc>
 477     void
 478     vector<_Tp, _Alloc>::
 479     _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
 480     {
 481       if (__n != 0)
 482         {
 483           if (size_type(this->_M_impl._M_end_of_storage
 484                         - this->_M_impl._M_finish) >= __n)
 485             {
 486 #if __cplusplus < 201103L
 487               value_type __x_copy = __x;
 488 #else
 489               _Temporary_value __tmp(this, __x);
 490               value_type& __x_copy = __tmp._M_val();
 491 #endif
 492               const size_type __elems_after = end() - __position;
 493               pointer __old_finish(this->_M_impl._M_finish);
 494               if (__elems_after > __n)
 495                 {
 496                   _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
 497                   std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
 498                                               this->_M_impl._M_finish,
 499                                               this->_M_impl._M_finish,
 500                                               _M_get_Tp_allocator());
 501                   this->_M_impl._M_finish += __n;
 502                   _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
 503                   _GLIBCXX_MOVE_BACKWARD3(__position.base(),
 504                                           __old_finish - __n, __old_finish);
 505                   std::fill(__position.base(), __position.base() + __n,
 506                             __x_copy);
 507                 }
 508               else
 509                 {
 510                   _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
 511                   this->_M_impl._M_finish =
 512                     std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
 513                                                   __n - __elems_after,
 514                                                   __x_copy,
 515                                                   _M_get_Tp_allocator());
 516                   _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
 517                   std::__uninitialized_move_a(__position.base(), __old_finish,
 518                                               this->_M_impl._M_finish,
 519                                               _M_get_Tp_allocator());
 520                   this->_M_impl._M_finish += __elems_after;
 521                   _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
 522                   std::fill(__position.base(), __old_finish, __x_copy);
 523                 }
 524             }
 525           else
 526             {
 527               const size_type __len =
 528                 _M_check_len(__n, "vector::_M_fill_insert");
 529               const size_type __elems_before = __position - begin();
 530               pointer __new_start(this->_M_allocate(__len));
 531               pointer __new_finish(__new_start);
 532               __try
 533                 {
 534                   // See _M_realloc_insert above.
 535                   std::__uninitialized_fill_n_a(__new_start + __elems_before,
 536                                                 __n, __x,
 537                                                 _M_get_Tp_allocator());
 538                   __new_finish = pointer();
 539
 540                   __new_finish
 541                     = std::__uninitialized_move_if_noexcept_a
 542                     (this->_M_impl._M_start, __position.base(),
 543                      __new_start, _M_get_Tp_allocator());
 544
 545                   __new_finish += __n;
 546
 547                   __new_finish
 548                     = std::__uninitialized_move_if_noexcept_a
 549                     (__position.base(), this->_M_impl._M_finish,
 550                      __new_finish, _M_get_Tp_allocator());
 551                 }
 552               __catch(...)
 553                 {
 554                   if (!__new_finish)
 555                     std::_Destroy(__new_start + __elems_before,
 556                                   __new_start + __elems_before + __n,
 557                                   _M_get_Tp_allocator());
 558                   else
 559                     std::_Destroy(__new_start, __new_finish,
 560                                   _M_get_Tp_allocator());
 561                   _M_deallocate(__new_start, __len);
 562                   __throw_exception_again;
 563                 }
 564               _GLIBCXX_ASAN_ANNOTATE_REINIT;
 565               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 566                             _M_get_Tp_allocator());
 567               _M_deallocate(this->_M_impl._M_start,
 568                             this->_M_impl._M_end_of_storage
 569                             - this->_M_impl._M_start);
 570               this->_M_impl._M_start = __new_start;
 571               this->_M_impl._M_finish = __new_finish;
 572               this->_M_impl._M_end_of_storage = __new_start + __len;
 573             }
 574         }
 575     }
 576
 577 #if __cplusplus >= 201103L
 578   template<typename _Tp, typename _Alloc>
 579     void
 580     vector<_Tp, _Alloc>::
 581     _M_default_append(size_type __n)
 582     {
 583       if (__n != 0)
 584         {
 585           if (size_type(this->_M_impl._M_end_of_storage
 586                         - this->_M_impl._M_finish) >= __n)
 587             {
 588               _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
 589               this->_M_impl._M_finish =
 590                 std::__uninitialized_default_n_a(this->_M_impl._M_finish,
 591                                                  __n, _M_get_Tp_allocator());
 592               _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
 593             }
 594           else
 595             {
 596               const size_type __len =
 597                 _M_check_len(__n, "vector::_M_default_append");
 598               const size_type __old_size = this->size();
 599               pointer __new_start(this->_M_allocate(__len));
 600               pointer __new_finish(__new_start);
 601               __try
 602                 {
 603                   __new_finish
 604                     = std::__uninitialized_move_if_noexcept_a
 605                     (this->_M_impl._M_start, this->_M_impl._M_finish,
 606                      __new_start, _M_get_Tp_allocator());
 607                   __new_finish =
 608                     std::__uninitialized_default_n_a(__new_finish, __n,
 609                                                      _M_get_Tp_allocator());
 610                 }
 611               __catch(...)
 612                 {
 613                   std::_Destroy(__new_start, __new_finish,
 614                                 _M_get_Tp_allocator());
 615                   _M_deallocate(__new_start, __len);
 616                   __throw_exception_again;
 617                 }
 618               _GLIBCXX_ASAN_ANNOTATE_REINIT;
 619               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 620                             _M_get_Tp_allocator());
 621               _M_deallocate(this->_M_impl._M_start,
 622                             this->_M_impl._M_end_of_storage
 623                             - this->_M_impl._M_start);
 624               this->_M_impl._M_start = __new_start;
 625               this->_M_impl._M_finish = __new_finish;
 626               this->_M_impl._M_end_of_storage = __new_start + __len;
 627             }
 628         }
 629     }
 630
 631   template<typename _Tp, typename _Alloc>
 632     bool
 633     vector<_Tp, _Alloc>::
 634     _M_shrink_to_fit()
 635     {
 636       if (capacity() == size())
 637         return false;
 638       _GLIBCXX_ASAN_ANNOTATE_REINIT;
 639       return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
 640     }
 641 #endif
 642
 643   template<typename _Tp, typename _Alloc>
 644     template<typename _InputIterator>
 645       void
 646       vector<_Tp, _Alloc>::
 647       _M_range_insert(iterator __pos, _InputIterator __first,
 648                       _InputIterator __last, std::input_iterator_tag)
 649       {
 650         if (__pos == end())
 651           {
 652             for (; __first != __last; ++__first)
 653               insert(end(), *__first);
 654           }
 655         else if (__first != __last)
 656           {
 657             vector __tmp(__first, __last, _M_get_Tp_allocator());
 658             insert(__pos,
 659                    _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.begin()),
 660                    _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.end()));
 661           }
 662       }
 663
 664   template<typename _Tp, typename _Alloc>
 665     template<typename _ForwardIterator>
 666       void
 667       vector<_Tp, _Alloc>::
 668       _M_range_insert(iterator __position, _ForwardIterator __first,
 669                       _ForwardIterator __last, std::forward_iterator_tag)
 670       {
 671         if (__first != __last)
 672           {
 673             const size_type __n = std::distance(__first, __last);
 674             if (size_type(this->_M_impl._M_end_of_storage
 675                           - this->_M_impl._M_finish) >= __n)
 676               {
 677                 const size_type __elems_after = end() - __position;
 678                 pointer __old_finish(this->_M_impl._M_finish);
 679                 if (__elems_after > __n)
 680                   {
 681                     _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
 682                     std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
 683                                                 this->_M_impl._M_finish,
 684                                                 this->_M_impl._M_finish,
 685                                                 _M_get_Tp_allocator());
 686                     this->_M_impl._M_finish += __n;
 687                     _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
 688                     _GLIBCXX_MOVE_BACKWARD3(__position.base(),
 689                                             __old_finish - __n, __old_finish);
 690                     std::copy(__first, __last, __position);
 691                   }
 692                 else
 693                   {
 694                     _ForwardIterator __mid = __first;
 695                     std::advance(__mid, __elems_after);
 696                     _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
 697                     std::__uninitialized_copy_a(__mid, __last,
 698                                                 this->_M_impl._M_finish,
 699                                                 _M_get_Tp_allocator());
 700                     this->_M_impl._M_finish += __n - __elems_after;
 701                     _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
 702                     std::__uninitialized_move_a(__position.base(),
 703                                                 __old_finish,
 704                                                 this->_M_impl._M_finish,
 705                                                 _M_get_Tp_allocator());
 706                     this->_M_impl._M_finish += __elems_after;
 707                     _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
 708                     std::copy(__first, __mid, __position);
 709                   }
 710               }
 711             else
 712               {
 713                 const size_type __len =
 714                   _M_check_len(__n, "vector::_M_range_insert");
 715                 pointer __new_start(this->_M_allocate(__len));
 716                 pointer __new_finish(__new_start);
 717                 __try
 718                   {
 719                     __new_finish
 720                       = std::__uninitialized_move_if_noexcept_a
 721                       (this->_M_impl._M_start, __position.base(),
 722                        __new_start, _M_get_Tp_allocator());
 723                     __new_finish
 724                       = std::__uninitialized_copy_a(__first, __last,
 725                                                     __new_finish,
 726                                                     _M_get_Tp_allocator());
 727                     __new_finish
 728                       = std::__uninitialized_move_if_noexcept_a
 729                       (__position.base(), this->_M_impl._M_finish,
 730                        __new_finish, _M_get_Tp_allocator());
 731                   }
 732                 __catch(...)
 733                   {
 734                     std::_Destroy(__new_start, __new_finish,
 735                                   _M_get_Tp_allocator());
 736                     _M_deallocate(__new_start, __len);
 737                     __throw_exception_again;
 738                   }
 739                 _GLIBCXX_ASAN_ANNOTATE_REINIT;
 740                 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 741                               _M_get_Tp_allocator());
 742                 _M_deallocate(this->_M_impl._M_start,
 743                               this->_M_impl._M_end_of_storage
 744                               - this->_M_impl._M_start);
 745                 this->_M_impl._M_start = __new_start;
 746                 this->_M_impl._M_finish = __new_finish;
 747                 this->_M_impl._M_end_of_storage = __new_start + __len;
 748               }
 749           }
 750       }
 751
 752
 753   // vector<bool>
 754   template<typename _Alloc>
 755     void
 756     vector<bool, _Alloc>::
 757     _M_reallocate(size_type __n)
 758     {
 759       _Bit_pointer __q = this->_M_allocate(__n);
 760       iterator __start(std::__addressof(*__q), 0);
 761       iterator __finish(_M_copy_aligned(begin(), end(), __start));
 762       this->_M_deallocate();
 763       this->_M_impl._M_start = __start;
 764       this->_M_impl._M_finish = __finish;
 765       this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
 766     }
 767
 768   template<typename _Alloc>
 769     void
 770     vector<bool, _Alloc>::
 771     _M_fill_insert(iterator __position, size_type __n, bool __x)
 772     {
 773       if (__n == 0)
 774         return;
 775       if (capacity() - size() >= __n)
 776         {
 777           std::copy_backward(__position, end(),
 778                              this->_M_impl._M_finish + difference_type(__n));
 779           std::fill(__position, __position + difference_type(__n), __x);
 780           this->_M_impl._M_finish += difference_type(__n);
 781         }
 782       else
 783         {
 784           const size_type __len =
 785             _M_check_len(__n, "vector<bool>::_M_fill_insert");
 786           _Bit_pointer __q = this->_M_allocate(__len);
 787           iterator __start(std::__addressof(*__q), 0);
 788           iterator __i = _M_copy_aligned(begin(), __position, __start);
 789           std::fill(__i, __i + difference_type(__n), __x);
 790           iterator __finish = std::copy(__position, end(),
 791                                         __i + difference_type(__n));
 792           this->_M_deallocate();
 793           this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
 794           this->_M_impl._M_start = __start;
 795           this->_M_impl._M_finish = __finish;
 796         }
 797     }
 798
 799   template<typename _Alloc>
 800     template<typename _ForwardIterator>
 801       void
 802       vector<bool, _Alloc>::
 803       _M_insert_range(iterator __position, _ForwardIterator __first,
 804                       _ForwardIterator __last, std::forward_iterator_tag)
 805       {
 806         if (__first != __last)
 807           {
 808             size_type __n = std::distance(__first, __last);
 809             if (capacity() - size() >= __n)
 810               {
 811                 std::copy_backward(__position, end(),
 812                                    this->_M_impl._M_finish
 813                                    + difference_type(__n));
 814                 std::copy(__first, __last, __position);
 815                 this->_M_impl._M_finish += difference_type(__n);
 816               }
 817             else
 818               {
 819                 const size_type __len =
 820                   _M_check_len(__n, "vector<bool>::_M_insert_range");
 821                 _Bit_pointer __q = this->_M_allocate(__len);
 822                 iterator __start(std::__addressof(*__q), 0);
 823                 iterator __i = _M_copy_aligned(begin(), __position, __start);
 824                 __i = std::copy(__first, __last, __i);
 825                 iterator __finish = std::copy(__position, end(), __i);
 826                 this->_M_deallocate();
 827                 this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
 828                 this->_M_impl._M_start = __start;
 829                 this->_M_impl._M_finish = __finish;
 830               }
 831           }
 832       }
 833
 834   template<typename _Alloc>
 835     void
 836     vector<bool, _Alloc>::
 837     _M_insert_aux(iterator __position, bool __x)
 838     {
 839       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
 840         {
 841           std::copy_backward(__position, this->_M_impl._M_finish,
 842                              this->_M_impl._M_finish + 1);
 843           *__position = __x;
 844           ++this->_M_impl._M_finish;
 845         }
 846       else
 847         {
 848           const size_type __len =
 849             _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
 850           _Bit_pointer __q = this->_M_allocate(__len);
 851           iterator __start(std::__addressof(*__q), 0);
 852           iterator __i = _M_copy_aligned(begin(), __position, __start);
 853           *__i++ = __x;
 854           iterator __finish = std::copy(__position, end(), __i);
 855           this->_M_deallocate();
 856           this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
 857           this->_M_impl._M_start = __start;
 858           this->_M_impl._M_finish = __finish;
 859         }
 860     }
 861
 862   template<typename _Alloc>
 863     typename vector<bool, _Alloc>::iterator
 864     vector<bool, _Alloc>::
 865     _M_erase(iterator __position)
 866     {
 867       if (__position + 1 != end())
 868         std::copy(__position + 1, end(), __position);
 869       --this->_M_impl._M_finish;
 870       return __position;
 871     }
 872
 873   template<typename _Alloc>
 874     typename vector<bool, _Alloc>::iterator
 875     vector<bool, _Alloc>::
 876     _M_erase(iterator __first, iterator __last)
 877     {
 878       if (__first != __last)
 879         _M_erase_at_end(std::copy(__last, end(), __first));
 880       return __first;
 881     }
 882
 883 #if __cplusplus >= 201103L
 884   template<typename _Alloc>
 885     bool
 886     vector<bool, _Alloc>::
 887     _M_shrink_to_fit()
 888     {
 889       if (capacity() - size() < int(_S_word_bit))
 890         return false;
 891       __try
 892         {
 893           _M_reallocate(size());
 894           return true;
 895         }
 896       __catch(...)
 897         { return false; }
 898     }
 899 #endif
 900
 901 _GLIBCXX_END_NAMESPACE_CONTAINER
 902 _GLIBCXX_END_NAMESPACE_VERSION
 903 } // namespace std
 904
 905 #if __cplusplus >= 201103L
 906
 907 namespace std _GLIBCXX_VISIBILITY(default)
 908 {
 909 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 910
 911   template<typename _Alloc>
 912     size_t
 913     hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>::
 914     operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept
 915     {
 916       size_t __hash = 0;
 917       using _GLIBCXX_STD_C::_S_word_bit;
 918       using _GLIBCXX_STD_C::_Bit_type;
 919
 920       const size_t __words = __b.size() / _S_word_bit;
 921       if (__words)
 922         {
 923           const size_t __clength = __words * sizeof(_Bit_type);
 924           __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength);
 925         }
 926
 927       const size_t __extrabits = __b.size() % _S_word_bit;
 928       if (__extrabits)
 929         {
 930           _Bit_type __hiword = *__b._M_impl._M_finish._M_p;
 931           __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits);
 932
 933           const size_t __clength
 934             = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__;
 935           if (__words)
 936             __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash);
 937           else
 938             __hash = std::_Hash_impl::hash(&__hiword, __clength);
 939         }
 940
 941       return __hash;
 942     }
 943
 944 _GLIBCXX_END_NAMESPACE_VERSION
 945 } // namespace std
 946
 947 #endif // C++11
 948
 949 #undef _GLIBCXX_ASAN_ANNOTATE_REINIT
 950 #undef _GLIBCXX_ASAN_ANNOTATE_GROW
 951 #undef _GLIBCXX_ASAN_ANNOTATE_GREW
 952 #undef _GLIBCXX_ASAN_ANNOTATE_SHRINK
 953
 954 #endif /* _VECTOR_TCC */