contrib/gcc-8.0/libstdc++-v3/include/bits/vector.tcc

   1 // Vector implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001-2018 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           const size_type __size = size();
 586           size_type __navail = size_type(this->_M_impl._M_end_of_storage
 587                                          - this->_M_impl._M_finish);
 588
 589           if (__size > max_size() || __navail > max_size() - __size)
 590             __builtin_unreachable();
 591
 592           if (__navail >= __n)
 593             {
 594               _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
 595               this->_M_impl._M_finish =
 596                 std::__uninitialized_default_n_a(this->_M_impl._M_finish,
 597                                                  __n, _M_get_Tp_allocator());
 598               _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
 599             }
 600           else
 601             {
 602               const size_type __len =
 603                 _M_check_len(__n, "vector::_M_default_append");
 604               pointer __new_start(this->_M_allocate(__len));
 605               pointer __destroy_from = pointer();
 606               __try
 607                 {
 608                   std::__uninitialized_default_n_a(__new_start + __size,
 609                                                    __n, _M_get_Tp_allocator());
 610                   __destroy_from = __new_start + __size;
 611                   std::__uninitialized_move_if_noexcept_a(
 612                       this->_M_impl._M_start, this->_M_impl._M_finish,
 613                       __new_start, _M_get_Tp_allocator());
 614                 }
 615               __catch(...)
 616                 {
 617                   if (__destroy_from)
 618                     std::_Destroy(__destroy_from, __destroy_from + __n,
 619                                   _M_get_Tp_allocator());
 620                   _M_deallocate(__new_start, __len);
 621                   __throw_exception_again;
 622                 }
 623               _GLIBCXX_ASAN_ANNOTATE_REINIT;
 624               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 625                             _M_get_Tp_allocator());
 626               _M_deallocate(this->_M_impl._M_start,
 627                             this->_M_impl._M_end_of_storage
 628                             - this->_M_impl._M_start);
 629               this->_M_impl._M_start = __new_start;
 630               this->_M_impl._M_finish = __new_start + __size + __n;
 631               this->_M_impl._M_end_of_storage = __new_start + __len;
 632             }
 633         }
 634     }
 635
 636   template<typename _Tp, typename _Alloc>
 637     bool
 638     vector<_Tp, _Alloc>::
 639     _M_shrink_to_fit()
 640     {
 641       if (capacity() == size())
 642         return false;
 643       _GLIBCXX_ASAN_ANNOTATE_REINIT;
 644       return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
 645     }
 646 #endif
 647
 648   template<typename _Tp, typename _Alloc>
 649     template<typename _InputIterator>
 650       void
 651       vector<_Tp, _Alloc>::
 652       _M_range_insert(iterator __pos, _InputIterator __first,
 653                       _InputIterator __last, std::input_iterator_tag)
 654       {
 655         if (__pos == end())
 656           {
 657             for (; __first != __last; ++__first)
 658               insert(end(), *__first);
 659           }
 660         else if (__first != __last)
 661           {
 662             vector __tmp(__first, __last, _M_get_Tp_allocator());
 663             insert(__pos,
 664                    _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.begin()),
 665                    _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.end()));
 666           }
 667       }
 668
 669   template<typename _Tp, typename _Alloc>
 670     template<typename _ForwardIterator>
 671       void
 672       vector<_Tp, _Alloc>::
 673       _M_range_insert(iterator __position, _ForwardIterator __first,
 674                       _ForwardIterator __last, std::forward_iterator_tag)
 675       {
 676         if (__first != __last)
 677           {
 678             const size_type __n = std::distance(__first, __last);
 679             if (size_type(this->_M_impl._M_end_of_storage
 680                           - this->_M_impl._M_finish) >= __n)
 681               {
 682                 const size_type __elems_after = end() - __position;
 683                 pointer __old_finish(this->_M_impl._M_finish);
 684                 if (__elems_after > __n)
 685                   {
 686                     _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
 687                     std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
 688                                                 this->_M_impl._M_finish,
 689                                                 this->_M_impl._M_finish,
 690                                                 _M_get_Tp_allocator());
 691                     this->_M_impl._M_finish += __n;
 692                     _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
 693                     _GLIBCXX_MOVE_BACKWARD3(__position.base(),
 694                                             __old_finish - __n, __old_finish);
 695                     std::copy(__first, __last, __position);
 696                   }
 697                 else
 698                   {
 699                     _ForwardIterator __mid = __first;
 700                     std::advance(__mid, __elems_after);
 701                     _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
 702                     std::__uninitialized_copy_a(__mid, __last,
 703                                                 this->_M_impl._M_finish,
 704                                                 _M_get_Tp_allocator());
 705                     this->_M_impl._M_finish += __n - __elems_after;
 706                     _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
 707                     std::__uninitialized_move_a(__position.base(),
 708                                                 __old_finish,
 709                                                 this->_M_impl._M_finish,
 710                                                 _M_get_Tp_allocator());
 711                     this->_M_impl._M_finish += __elems_after;
 712                     _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
 713                     std::copy(__first, __mid, __position);
 714                   }
 715               }
 716             else
 717               {
 718                 const size_type __len =
 719                   _M_check_len(__n, "vector::_M_range_insert");
 720                 pointer __new_start(this->_M_allocate(__len));
 721                 pointer __new_finish(__new_start);
 722                 __try
 723                   {
 724                     __new_finish
 725                       = std::__uninitialized_move_if_noexcept_a
 726                       (this->_M_impl._M_start, __position.base(),
 727                        __new_start, _M_get_Tp_allocator());
 728                     __new_finish
 729                       = std::__uninitialized_copy_a(__first, __last,
 730                                                     __new_finish,
 731                                                     _M_get_Tp_allocator());
 732                     __new_finish
 733                       = std::__uninitialized_move_if_noexcept_a
 734                       (__position.base(), this->_M_impl._M_finish,
 735                        __new_finish, _M_get_Tp_allocator());
 736                   }
 737                 __catch(...)
 738                   {
 739                     std::_Destroy(__new_start, __new_finish,
 740                                   _M_get_Tp_allocator());
 741                     _M_deallocate(__new_start, __len);
 742                     __throw_exception_again;
 743                   }
 744                 _GLIBCXX_ASAN_ANNOTATE_REINIT;
 745                 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 746                               _M_get_Tp_allocator());
 747                 _M_deallocate(this->_M_impl._M_start,
 748                               this->_M_impl._M_end_of_storage
 749                               - this->_M_impl._M_start);
 750                 this->_M_impl._M_start = __new_start;
 751                 this->_M_impl._M_finish = __new_finish;
 752                 this->_M_impl._M_end_of_storage = __new_start + __len;
 753               }
 754           }
 755       }
 756
 757
 758   // vector<bool>
 759   template<typename _Alloc>
 760     void
 761     vector<bool, _Alloc>::
 762     _M_reallocate(size_type __n)
 763     {
 764       _Bit_pointer __q = this->_M_allocate(__n);
 765       iterator __start(std::__addressof(*__q), 0);
 766       iterator __finish(_M_copy_aligned(begin(), end(), __start));
 767       this->_M_deallocate();
 768       this->_M_impl._M_start = __start;
 769       this->_M_impl._M_finish = __finish;
 770       this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
 771     }
 772
 773   template<typename _Alloc>
 774     void
 775     vector<bool, _Alloc>::
 776     _M_fill_insert(iterator __position, size_type __n, bool __x)
 777     {
 778       if (__n == 0)
 779         return;
 780       if (capacity() - size() >= __n)
 781         {
 782           std::copy_backward(__position, end(),
 783                              this->_M_impl._M_finish + difference_type(__n));
 784           std::fill(__position, __position + difference_type(__n), __x);
 785           this->_M_impl._M_finish += difference_type(__n);
 786         }
 787       else
 788         {
 789           const size_type __len =
 790             _M_check_len(__n, "vector<bool>::_M_fill_insert");
 791           _Bit_pointer __q = this->_M_allocate(__len);
 792           iterator __start(std::__addressof(*__q), 0);
 793           iterator __i = _M_copy_aligned(begin(), __position, __start);
 794           std::fill(__i, __i + difference_type(__n), __x);
 795           iterator __finish = std::copy(__position, end(),
 796                                         __i + difference_type(__n));
 797           this->_M_deallocate();
 798           this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
 799           this->_M_impl._M_start = __start;
 800           this->_M_impl._M_finish = __finish;
 801         }
 802     }
 803
 804   template<typename _Alloc>
 805     template<typename _ForwardIterator>
 806       void
 807       vector<bool, _Alloc>::
 808       _M_insert_range(iterator __position, _ForwardIterator __first,
 809                       _ForwardIterator __last, std::forward_iterator_tag)
 810       {
 811         if (__first != __last)
 812           {
 813             size_type __n = std::distance(__first, __last);
 814             if (capacity() - size() >= __n)
 815               {
 816                 std::copy_backward(__position, end(),
 817                                    this->_M_impl._M_finish
 818                                    + difference_type(__n));
 819                 std::copy(__first, __last, __position);
 820                 this->_M_impl._M_finish += difference_type(__n);
 821               }
 822             else
 823               {
 824                 const size_type __len =
 825                   _M_check_len(__n, "vector<bool>::_M_insert_range");
 826                 _Bit_pointer __q = this->_M_allocate(__len);
 827                 iterator __start(std::__addressof(*__q), 0);
 828                 iterator __i = _M_copy_aligned(begin(), __position, __start);
 829                 __i = std::copy(__first, __last, __i);
 830                 iterator __finish = std::copy(__position, end(), __i);
 831                 this->_M_deallocate();
 832                 this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
 833                 this->_M_impl._M_start = __start;
 834                 this->_M_impl._M_finish = __finish;
 835               }
 836           }
 837       }
 838
 839   template<typename _Alloc>
 840     void
 841     vector<bool, _Alloc>::
 842     _M_insert_aux(iterator __position, bool __x)
 843     {
 844       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
 845         {
 846           std::copy_backward(__position, this->_M_impl._M_finish,
 847                              this->_M_impl._M_finish + 1);
 848           *__position = __x;
 849           ++this->_M_impl._M_finish;
 850         }
 851       else
 852         {
 853           const size_type __len =
 854             _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
 855           _Bit_pointer __q = this->_M_allocate(__len);
 856           iterator __start(std::__addressof(*__q), 0);
 857           iterator __i = _M_copy_aligned(begin(), __position, __start);
 858           *__i++ = __x;
 859           iterator __finish = std::copy(__position, end(), __i);
 860           this->_M_deallocate();
 861           this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
 862           this->_M_impl._M_start = __start;
 863           this->_M_impl._M_finish = __finish;
 864         }
 865     }
 866
 867   template<typename _Alloc>
 868     typename vector<bool, _Alloc>::iterator
 869     vector<bool, _Alloc>::
 870     _M_erase(iterator __position)
 871     {
 872       if (__position + 1 != end())
 873         std::copy(__position + 1, end(), __position);
 874       --this->_M_impl._M_finish;
 875       return __position;
 876     }
 877
 878   template<typename _Alloc>
 879     typename vector<bool, _Alloc>::iterator
 880     vector<bool, _Alloc>::
 881     _M_erase(iterator __first, iterator __last)
 882     {
 883       if (__first != __last)
 884         _M_erase_at_end(std::copy(__last, end(), __first));
 885       return __first;
 886     }
 887
 888 #if __cplusplus >= 201103L
 889   template<typename _Alloc>
 890     bool
 891     vector<bool, _Alloc>::
 892     _M_shrink_to_fit()
 893     {
 894       if (capacity() - size() < int(_S_word_bit))
 895         return false;
 896       __try
 897         {
 898           _M_reallocate(size());
 899           return true;
 900         }
 901       __catch(...)
 902         { return false; }
 903     }
 904 #endif
 905
 906 _GLIBCXX_END_NAMESPACE_CONTAINER
 907 _GLIBCXX_END_NAMESPACE_VERSION
 908 } // namespace std
 909
 910 #if __cplusplus >= 201103L
 911
 912 namespace std _GLIBCXX_VISIBILITY(default)
 913 {
 914 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 915
 916   template<typename _Alloc>
 917     size_t
 918     hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>::
 919     operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept
 920     {
 921       size_t __hash = 0;
 922       using _GLIBCXX_STD_C::_S_word_bit;
 923       using _GLIBCXX_STD_C::_Bit_type;
 924
 925       const size_t __words = __b.size() / _S_word_bit;
 926       if (__words)
 927         {
 928           const size_t __clength = __words * sizeof(_Bit_type);
 929           __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength);
 930         }
 931
 932       const size_t __extrabits = __b.size() % _S_word_bit;
 933       if (__extrabits)
 934         {
 935           _Bit_type __hiword = *__b._M_impl._M_finish._M_p;
 936           __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits);
 937
 938           const size_t __clength
 939             = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__;
 940           if (__words)
 941             __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash);
 942           else
 943             __hash = std::_Hash_impl::hash(&__hiword, __clength);
 944         }
 945
 946       return __hash;
 947     }
 948
 949 _GLIBCXX_END_NAMESPACE_VERSION
 950 } // namespace std
 951
 952 #endif // C++11
 953
 954 #undef _GLIBCXX_ASAN_ANNOTATE_REINIT
 955 #undef _GLIBCXX_ASAN_ANNOTATE_GROW
 956 #undef _GLIBCXX_ASAN_ANNOTATE_GREW
 957 #undef _GLIBCXX_ASAN_ANNOTATE_SHRINK
 958
 959 #endif /* _VECTOR_TCC */