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

   1 // Vector implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001-2013 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_CONTAINER
  62
  63   template<typename _Tp, typename _Alloc>
  64     void
  65     vector<_Tp, _Alloc>::
  66     reserve(size_type __n)
  67     {
  68       if (__n > this->max_size())
  69         __throw_length_error(__N("vector::reserve"));
  70       if (this->capacity() < __n)
  71         {
  72           const size_type __old_size = size();
  73           pointer __tmp = _M_allocate_and_copy(__n,
  74             _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start),
  75             _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish));
  76           std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
  77                         _M_get_Tp_allocator());
  78           _M_deallocate(this->_M_impl._M_start,
  79                         this->_M_impl._M_end_of_storage
  80                         - this->_M_impl._M_start);
  81           this->_M_impl._M_start = __tmp;
  82           this->_M_impl._M_finish = __tmp + __old_size;
  83           this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
  84         }
  85     }
  86
  87 #if __cplusplus >= 201103L
  88   template<typename _Tp, typename _Alloc>
  89     template<typename... _Args>
  90       void
  91       vector<_Tp, _Alloc>::
  92       emplace_back(_Args&&... __args)
  93       {
  94         if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
  95           {
  96             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
  97                                      std::forward<_Args>(__args)...);
  98             ++this->_M_impl._M_finish;
  99           }
 100         else
 101           _M_emplace_back_aux(std::forward<_Args>(__args)...);
 102       }
 103 #endif
 104
 105   template<typename _Tp, typename _Alloc>
 106     typename vector<_Tp, _Alloc>::iterator
 107     vector<_Tp, _Alloc>::
 108     insert(iterator __position, const value_type& __x)
 109     {
 110       const size_type __n = __position - begin();
 111       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
 112           && __position == end())
 113         {
 114           _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
 115           ++this->_M_impl._M_finish;
 116         }
 117       else
 118         {
 119 #if __cplusplus >= 201103L
 120           if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
 121             {
 122               _Tp __x_copy = __x;
 123               _M_insert_aux(__position, std::move(__x_copy));
 124             }
 125           else
 126 #endif
 127             _M_insert_aux(__position, __x);
 128         }
 129       return iterator(this->_M_impl._M_start + __n);
 130     }
 131
 132   template<typename _Tp, typename _Alloc>
 133     typename vector<_Tp, _Alloc>::iterator
 134     vector<_Tp, _Alloc>::
 135     erase(iterator __position)
 136     {
 137       if (__position + 1 != end())
 138         _GLIBCXX_MOVE3(__position + 1, end(), __position);
 139       --this->_M_impl._M_finish;
 140       _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
 141       return __position;
 142     }
 143
 144   template<typename _Tp, typename _Alloc>
 145     typename vector<_Tp, _Alloc>::iterator
 146     vector<_Tp, _Alloc>::
 147     erase(iterator __first, iterator __last)
 148     {
 149       if (__first != __last)
 150         {
 151           if (__last != end())
 152             _GLIBCXX_MOVE3(__last, end(), __first);
 153           _M_erase_at_end(__first.base() + (end() - __last));
 154         }
 155       return __first;
 156     }
 157
 158   template<typename _Tp, typename _Alloc>
 159     vector<_Tp, _Alloc>&
 160     vector<_Tp, _Alloc>::
 161     operator=(const vector<_Tp, _Alloc>& __x)
 162     {
 163       if (&__x != this)
 164         {
 165 #if __cplusplus >= 201103L
 166           if (_Alloc_traits::_S_propagate_on_copy_assign())
 167             {
 168               if (!_Alloc_traits::_S_always_equal()
 169                   && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
 170                 {
 171                   // replacement allocator cannot free existing storage
 172                   this->clear();
 173                   _M_deallocate(this->_M_impl._M_start,
 174                                 this->_M_impl._M_end_of_storage
 175                                 - this->_M_impl._M_start);
 176                   this->_M_impl._M_start = nullptr;
 177                   this->_M_impl._M_finish = nullptr;
 178                   this->_M_impl._M_end_of_storage = nullptr;
 179                 }
 180               std::__alloc_on_copy(_M_get_Tp_allocator(),
 181                                    __x._M_get_Tp_allocator());
 182             }
 183 #endif
 184           const size_type __xlen = __x.size();
 185           if (__xlen > capacity())
 186             {
 187               pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
 188                                                    __x.end());
 189               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 190                             _M_get_Tp_allocator());
 191               _M_deallocate(this->_M_impl._M_start,
 192                             this->_M_impl._M_end_of_storage
 193                             - this->_M_impl._M_start);
 194               this->_M_impl._M_start = __tmp;
 195               this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
 196             }
 197           else if (size() >= __xlen)
 198             {
 199               std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
 200                             end(), _M_get_Tp_allocator());
 201             }
 202           else
 203             {
 204               std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
 205                         this->_M_impl._M_start);
 206               std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
 207                                           __x._M_impl._M_finish,
 208                                           this->_M_impl._M_finish,
 209                                           _M_get_Tp_allocator());
 210             }
 211           this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
 212         }
 213       return *this;
 214     }
 215
 216   template<typename _Tp, typename _Alloc>
 217     void
 218     vector<_Tp, _Alloc>::
 219     _M_fill_assign(size_t __n, const value_type& __val)
 220     {
 221       if (__n > capacity())
 222         {
 223           vector __tmp(__n, __val, _M_get_Tp_allocator());
 224           __tmp.swap(*this);
 225         }
 226       else if (__n > size())
 227         {
 228           std::fill(begin(), end(), __val);
 229           std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
 230                                         __n - size(), __val,
 231                                         _M_get_Tp_allocator());
 232           this->_M_impl._M_finish += __n - size();
 233         }
 234       else
 235         _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
 236     }
 237
 238   template<typename _Tp, typename _Alloc>
 239     template<typename _InputIterator>
 240       void
 241       vector<_Tp, _Alloc>::
 242       _M_assign_aux(_InputIterator __first, _InputIterator __last,
 243                     std::input_iterator_tag)
 244       {
 245         pointer __cur(this->_M_impl._M_start);
 246         for (; __first != __last && __cur != this->_M_impl._M_finish;
 247              ++__cur, ++__first)
 248           *__cur = *__first;
 249         if (__first == __last)
 250           _M_erase_at_end(__cur);
 251         else
 252           insert(end(), __first, __last);
 253       }
 254
 255   template<typename _Tp, typename _Alloc>
 256     template<typename _ForwardIterator>
 257       void
 258       vector<_Tp, _Alloc>::
 259       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
 260                     std::forward_iterator_tag)
 261       {
 262         const size_type __len = std::distance(__first, __last);
 263
 264         if (__len > capacity())
 265           {
 266             pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
 267             std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 268                           _M_get_Tp_allocator());
 269             _M_deallocate(this->_M_impl._M_start,
 270                           this->_M_impl._M_end_of_storage
 271                           - this->_M_impl._M_start);
 272             this->_M_impl._M_start = __tmp;
 273             this->_M_impl._M_finish = this->_M_impl._M_start + __len;
 274             this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
 275           }
 276         else if (size() >= __len)
 277           _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
 278         else
 279           {
 280             _ForwardIterator __mid = __first;
 281             std::advance(__mid, size());
 282             std::copy(__first, __mid, this->_M_impl._M_start);
 283             this->_M_impl._M_finish =
 284               std::__uninitialized_copy_a(__mid, __last,
 285                                           this->_M_impl._M_finish,
 286                                           _M_get_Tp_allocator());
 287           }
 288       }
 289
 290 #if __cplusplus >= 201103L
 291   template<typename _Tp, typename _Alloc>
 292     template<typename... _Args>
 293       typename vector<_Tp, _Alloc>::iterator
 294       vector<_Tp, _Alloc>::
 295       emplace(iterator __position, _Args&&... __args)
 296       {
 297         const size_type __n = __position - begin();
 298         if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
 299             && __position == end())
 300           {
 301             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
 302                                      std::forward<_Args>(__args)...);
 303             ++this->_M_impl._M_finish;
 304           }
 305         else
 306           _M_insert_aux(__position, std::forward<_Args>(__args)...);
 307         return iterator(this->_M_impl._M_start + __n);
 308       }
 309
 310   template<typename _Tp, typename _Alloc>
 311     template<typename... _Args>
 312       void
 313       vector<_Tp, _Alloc>::
 314       _M_insert_aux(iterator __position, _Args&&... __args)
 315 #else
 316   template<typename _Tp, typename _Alloc>
 317     void
 318     vector<_Tp, _Alloc>::
 319     _M_insert_aux(iterator __position, const _Tp& __x)
 320 #endif
 321     {
 322       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
 323         {
 324           _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
 325                                    _GLIBCXX_MOVE(*(this->_M_impl._M_finish
 326                                                    - 1)));
 327           ++this->_M_impl._M_finish;
 328 #if __cplusplus < 201103L
 329           _Tp __x_copy = __x;
 330 #endif
 331           _GLIBCXX_MOVE_BACKWARD3(__position.base(),
 332                                   this->_M_impl._M_finish - 2,
 333                                   this->_M_impl._M_finish - 1);
 334 #if __cplusplus < 201103L
 335           *__position = __x_copy;
 336 #else
 337           *__position = _Tp(std::forward<_Args>(__args)...);
 338 #endif
 339         }
 340       else
 341         {
 342           const size_type __len =
 343             _M_check_len(size_type(1), "vector::_M_insert_aux");
 344           const size_type __elems_before = __position - begin();
 345           pointer __new_start(this->_M_allocate(__len));
 346           pointer __new_finish(__new_start);
 347           __try
 348             {
 349               // The order of the three operations is dictated by the C++0x
 350               // case, where the moves could alter a new element belonging
 351               // to the existing vector.  This is an issue only for callers
 352               // taking the element by const lvalue ref (see 23.1/13).
 353               _Alloc_traits::construct(this->_M_impl,
 354                                        __new_start + __elems_before,
 355 #if __cplusplus >= 201103L
 356                                        std::forward<_Args>(__args)...);
 357 #else
 358                                        __x);
 359 #endif
 360               __new_finish = 0;
 361
 362               __new_finish
 363                 = std::__uninitialized_move_if_noexcept_a
 364                 (this->_M_impl._M_start, __position.base(),
 365                  __new_start, _M_get_Tp_allocator());
 366
 367               ++__new_finish;
 368
 369               __new_finish
 370                 = std::__uninitialized_move_if_noexcept_a
 371                 (__position.base(), this->_M_impl._M_finish,
 372                  __new_finish, _M_get_Tp_allocator());
 373             }
 374           __catch(...)
 375             {
 376               if (!__new_finish)
 377                 _Alloc_traits::destroy(this->_M_impl,
 378                                        __new_start + __elems_before);
 379               else
 380                 std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
 381               _M_deallocate(__new_start, __len);
 382               __throw_exception_again;
 383             }
 384           std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 385                         _M_get_Tp_allocator());
 386           _M_deallocate(this->_M_impl._M_start,
 387                         this->_M_impl._M_end_of_storage
 388                         - this->_M_impl._M_start);
 389           this->_M_impl._M_start = __new_start;
 390           this->_M_impl._M_finish = __new_finish;
 391           this->_M_impl._M_end_of_storage = __new_start + __len;
 392         }
 393     }
 394
 395 #if __cplusplus >= 201103L
 396   template<typename _Tp, typename _Alloc>
 397     template<typename... _Args>
 398       void
 399       vector<_Tp, _Alloc>::
 400       _M_emplace_back_aux(_Args&&... __args)
 401       {
 402         const size_type __len =
 403           _M_check_len(size_type(1), "vector::_M_emplace_back_aux");
 404         pointer __new_start(this->_M_allocate(__len));
 405         pointer __new_finish(__new_start);
 406         __try
 407           {
 408             _Alloc_traits::construct(this->_M_impl, __new_start + size(),
 409                                      std::forward<_Args>(__args)...);
 410             __new_finish = 0;
 411
 412             __new_finish
 413               = std::__uninitialized_move_if_noexcept_a
 414               (this->_M_impl._M_start, this->_M_impl._M_finish,
 415                __new_start, _M_get_Tp_allocator());
 416
 417             ++__new_finish;
 418           }
 419         __catch(...)
 420           {
 421             if (!__new_finish)
 422               _Alloc_traits::destroy(this->_M_impl, __new_start + size());
 423             else
 424               std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
 425             _M_deallocate(__new_start, __len);
 426             __throw_exception_again;
 427           }
 428         std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 429                       _M_get_Tp_allocator());
 430         _M_deallocate(this->_M_impl._M_start,
 431                       this->_M_impl._M_end_of_storage
 432                       - this->_M_impl._M_start);
 433         this->_M_impl._M_start = __new_start;
 434         this->_M_impl._M_finish = __new_finish;
 435         this->_M_impl._M_end_of_storage = __new_start + __len;
 436       }
 437 #endif
 438
 439   template<typename _Tp, typename _Alloc>
 440     void
 441     vector<_Tp, _Alloc>::
 442     _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
 443     {
 444       if (__n != 0)
 445         {
 446           if (size_type(this->_M_impl._M_end_of_storage
 447                         - this->_M_impl._M_finish) >= __n)
 448             {
 449               value_type __x_copy = __x;
 450               const size_type __elems_after = end() - __position;
 451               pointer __old_finish(this->_M_impl._M_finish);
 452               if (__elems_after > __n)
 453                 {
 454                   std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
 455                                               this->_M_impl._M_finish,
 456                                               this->_M_impl._M_finish,
 457                                               _M_get_Tp_allocator());
 458                   this->_M_impl._M_finish += __n;
 459                   _GLIBCXX_MOVE_BACKWARD3(__position.base(),
 460                                           __old_finish - __n, __old_finish);
 461                   std::fill(__position.base(), __position.base() + __n,
 462                             __x_copy);
 463                 }
 464               else
 465                 {
 466                   std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
 467                                                 __n - __elems_after,
 468                                                 __x_copy,
 469                                                 _M_get_Tp_allocator());
 470                   this->_M_impl._M_finish += __n - __elems_after;
 471                   std::__uninitialized_move_a(__position.base(), __old_finish,
 472                                               this->_M_impl._M_finish,
 473                                               _M_get_Tp_allocator());
 474                   this->_M_impl._M_finish += __elems_after;
 475                   std::fill(__position.base(), __old_finish, __x_copy);
 476                 }
 477             }
 478           else
 479             {
 480               const size_type __len =
 481                 _M_check_len(__n, "vector::_M_fill_insert");
 482               const size_type __elems_before = __position - begin();
 483               pointer __new_start(this->_M_allocate(__len));
 484               pointer __new_finish(__new_start);
 485               __try
 486                 {
 487                   // See _M_insert_aux above.
 488                   std::__uninitialized_fill_n_a(__new_start + __elems_before,
 489                                                 __n, __x,
 490                                                 _M_get_Tp_allocator());
 491                   __new_finish = 0;
 492
 493                   __new_finish
 494                     = std::__uninitialized_move_if_noexcept_a
 495                     (this->_M_impl._M_start, __position.base(),
 496                      __new_start, _M_get_Tp_allocator());
 497
 498                   __new_finish += __n;
 499
 500                   __new_finish
 501                     = std::__uninitialized_move_if_noexcept_a
 502                     (__position.base(), this->_M_impl._M_finish,
 503                      __new_finish, _M_get_Tp_allocator());
 504                 }
 505               __catch(...)
 506                 {
 507                   if (!__new_finish)
 508                     std::_Destroy(__new_start + __elems_before,
 509                                   __new_start + __elems_before + __n,
 510                                   _M_get_Tp_allocator());
 511                   else
 512                     std::_Destroy(__new_start, __new_finish,
 513                                   _M_get_Tp_allocator());
 514                   _M_deallocate(__new_start, __len);
 515                   __throw_exception_again;
 516                 }
 517               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 518                             _M_get_Tp_allocator());
 519               _M_deallocate(this->_M_impl._M_start,
 520                             this->_M_impl._M_end_of_storage
 521                             - this->_M_impl._M_start);
 522               this->_M_impl._M_start = __new_start;
 523               this->_M_impl._M_finish = __new_finish;
 524               this->_M_impl._M_end_of_storage = __new_start + __len;
 525             }
 526         }
 527     }
 528
 529 #if __cplusplus >= 201103L
 530   template<typename _Tp, typename _Alloc>
 531     void
 532     vector<_Tp, _Alloc>::
 533     _M_default_append(size_type __n)
 534     {
 535       if (__n != 0)
 536         {
 537           if (size_type(this->_M_impl._M_end_of_storage
 538                         - this->_M_impl._M_finish) >= __n)
 539             {
 540               std::__uninitialized_default_n_a(this->_M_impl._M_finish,
 541                                                __n, _M_get_Tp_allocator());
 542               this->_M_impl._M_finish += __n;
 543             }
 544           else
 545             {
 546               const size_type __len =
 547                 _M_check_len(__n, "vector::_M_default_append");
 548               const size_type __old_size = this->size();
 549               pointer __new_start(this->_M_allocate(__len));
 550               pointer __new_finish(__new_start);
 551               __try
 552                 {
 553                   __new_finish
 554                     = std::__uninitialized_move_if_noexcept_a
 555                     (this->_M_impl._M_start, this->_M_impl._M_finish,
 556                      __new_start, _M_get_Tp_allocator());
 557                   std::__uninitialized_default_n_a(__new_finish, __n,
 558                                                    _M_get_Tp_allocator());
 559                   __new_finish += __n;
 560                 }
 561               __catch(...)
 562                 {
 563                   std::_Destroy(__new_start, __new_finish,
 564                                 _M_get_Tp_allocator());
 565                   _M_deallocate(__new_start, __len);
 566                   __throw_exception_again;
 567                 }
 568               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 569                             _M_get_Tp_allocator());
 570               _M_deallocate(this->_M_impl._M_start,
 571                             this->_M_impl._M_end_of_storage
 572                             - this->_M_impl._M_start);
 573               this->_M_impl._M_start = __new_start;
 574               this->_M_impl._M_finish = __new_finish;
 575               this->_M_impl._M_end_of_storage = __new_start + __len;
 576             }
 577         }
 578     }
 579
 580   template<typename _Tp, typename _Alloc>
 581     bool
 582     vector<_Tp, _Alloc>::
 583     _M_shrink_to_fit()
 584     {
 585       if (capacity() == size())
 586         return false;
 587       return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
 588     }
 589 #endif
 590
 591   template<typename _Tp, typename _Alloc>
 592     template<typename _InputIterator>
 593       void
 594       vector<_Tp, _Alloc>::
 595       _M_range_insert(iterator __pos, _InputIterator __first,
 596                       _InputIterator __last, std::input_iterator_tag)
 597       {
 598         for (; __first != __last; ++__first)
 599           {
 600             __pos = insert(__pos, *__first);
 601             ++__pos;
 602           }
 603       }
 604
 605   template<typename _Tp, typename _Alloc>
 606     template<typename _ForwardIterator>
 607       void
 608       vector<_Tp, _Alloc>::
 609       _M_range_insert(iterator __position, _ForwardIterator __first,
 610                       _ForwardIterator __last, std::forward_iterator_tag)
 611       {
 612         if (__first != __last)
 613           {
 614             const size_type __n = std::distance(__first, __last);
 615             if (size_type(this->_M_impl._M_end_of_storage
 616                           - this->_M_impl._M_finish) >= __n)
 617               {
 618                 const size_type __elems_after = end() - __position;
 619                 pointer __old_finish(this->_M_impl._M_finish);
 620                 if (__elems_after > __n)
 621                   {
 622                     std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
 623                                                 this->_M_impl._M_finish,
 624                                                 this->_M_impl._M_finish,
 625                                                 _M_get_Tp_allocator());
 626                     this->_M_impl._M_finish += __n;
 627                     _GLIBCXX_MOVE_BACKWARD3(__position.base(),
 628                                             __old_finish - __n, __old_finish);
 629                     std::copy(__first, __last, __position);
 630                   }
 631                 else
 632                   {
 633                     _ForwardIterator __mid = __first;
 634                     std::advance(__mid, __elems_after);
 635                     std::__uninitialized_copy_a(__mid, __last,
 636                                                 this->_M_impl._M_finish,
 637                                                 _M_get_Tp_allocator());
 638                     this->_M_impl._M_finish += __n - __elems_after;
 639                     std::__uninitialized_move_a(__position.base(),
 640                                                 __old_finish,
 641                                                 this->_M_impl._M_finish,
 642                                                 _M_get_Tp_allocator());
 643                     this->_M_impl._M_finish += __elems_after;
 644                     std::copy(__first, __mid, __position);
 645                   }
 646               }
 647             else
 648               {
 649                 const size_type __len =
 650                   _M_check_len(__n, "vector::_M_range_insert");
 651                 pointer __new_start(this->_M_allocate(__len));
 652                 pointer __new_finish(__new_start);
 653                 __try
 654                   {
 655                     __new_finish
 656                       = std::__uninitialized_move_if_noexcept_a
 657                       (this->_M_impl._M_start, __position.base(),
 658                        __new_start, _M_get_Tp_allocator());
 659                     __new_finish
 660                       = std::__uninitialized_copy_a(__first, __last,
 661                                                     __new_finish,
 662                                                     _M_get_Tp_allocator());
 663                     __new_finish
 664                       = std::__uninitialized_move_if_noexcept_a
 665                       (__position.base(), this->_M_impl._M_finish,
 666                        __new_finish, _M_get_Tp_allocator());
 667                   }
 668                 __catch(...)
 669                   {
 670                     std::_Destroy(__new_start, __new_finish,
 671                                   _M_get_Tp_allocator());
 672                     _M_deallocate(__new_start, __len);
 673                     __throw_exception_again;
 674                   }
 675                 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 676                               _M_get_Tp_allocator());
 677                 _M_deallocate(this->_M_impl._M_start,
 678                               this->_M_impl._M_end_of_storage
 679                               - this->_M_impl._M_start);
 680                 this->_M_impl._M_start = __new_start;
 681                 this->_M_impl._M_finish = __new_finish;
 682                 this->_M_impl._M_end_of_storage = __new_start + __len;
 683               }
 684           }
 685       }
 686
 687
 688   // vector<bool>
 689   template<typename _Alloc>
 690     void
 691     vector<bool, _Alloc>::
 692     _M_reallocate(size_type __n)
 693     {
 694       _Bit_type* __q = this->_M_allocate(__n);
 695       this->_M_impl._M_finish = _M_copy_aligned(begin(), end(),
 696                                                 iterator(__q, 0));
 697       this->_M_deallocate();
 698       this->_M_impl._M_start = iterator(__q, 0);
 699       this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
 700     }
 701
 702   template<typename _Alloc>
 703     void
 704     vector<bool, _Alloc>::
 705     _M_fill_insert(iterator __position, size_type __n, bool __x)
 706     {
 707       if (__n == 0)
 708         return;
 709       if (capacity() - size() >= __n)
 710         {
 711           std::copy_backward(__position, end(),
 712                              this->_M_impl._M_finish + difference_type(__n));
 713           std::fill(__position, __position + difference_type(__n), __x);
 714           this->_M_impl._M_finish += difference_type(__n);
 715         }
 716       else
 717         {
 718           const size_type __len =
 719             _M_check_len(__n, "vector<bool>::_M_fill_insert");
 720           _Bit_type * __q = this->_M_allocate(__len);
 721           iterator __i = _M_copy_aligned(begin(), __position,
 722                                          iterator(__q, 0));
 723           std::fill(__i, __i + difference_type(__n), __x);
 724           this->_M_impl._M_finish = std::copy(__position, end(),
 725                                               __i + difference_type(__n));
 726           this->_M_deallocate();
 727           this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
 728           this->_M_impl._M_start = iterator(__q, 0);
 729         }
 730     }
 731
 732   template<typename _Alloc>
 733     template<typename _ForwardIterator>
 734       void
 735       vector<bool, _Alloc>::
 736       _M_insert_range(iterator __position, _ForwardIterator __first,
 737                       _ForwardIterator __last, std::forward_iterator_tag)
 738       {
 739         if (__first != __last)
 740           {
 741             size_type __n = std::distance(__first, __last);
 742             if (capacity() - size() >= __n)
 743               {
 744                 std::copy_backward(__position, end(),
 745                                    this->_M_impl._M_finish
 746                                    + difference_type(__n));
 747                 std::copy(__first, __last, __position);
 748                 this->_M_impl._M_finish += difference_type(__n);
 749               }
 750             else
 751               {
 752                 const size_type __len =
 753                   _M_check_len(__n, "vector<bool>::_M_insert_range");
 754                 _Bit_type * __q = this->_M_allocate(__len);
 755                 iterator __i = _M_copy_aligned(begin(), __position,
 756                                                iterator(__q, 0));
 757                 __i = std::copy(__first, __last, __i);
 758                 this->_M_impl._M_finish = std::copy(__position, end(), __i);
 759                 this->_M_deallocate();
 760                 this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
 761                 this->_M_impl._M_start = iterator(__q, 0);
 762               }
 763           }
 764       }
 765
 766   template<typename _Alloc>
 767     void
 768     vector<bool, _Alloc>::
 769     _M_insert_aux(iterator __position, bool __x)
 770     {
 771       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
 772         {
 773           std::copy_backward(__position, this->_M_impl._M_finish,
 774                              this->_M_impl._M_finish + 1);
 775           *__position = __x;
 776           ++this->_M_impl._M_finish;
 777         }
 778       else
 779         {
 780           const size_type __len =
 781             _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
 782           _Bit_type * __q = this->_M_allocate(__len);
 783           iterator __i = _M_copy_aligned(begin(), __position,
 784                                          iterator(__q, 0));
 785           *__i++ = __x;
 786           this->_M_impl._M_finish = std::copy(__position, end(), __i);
 787           this->_M_deallocate();
 788           this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
 789           this->_M_impl._M_start = iterator(__q, 0);
 790         }
 791     }
 792
 793 #if __cplusplus >= 201103L
 794   template<typename _Alloc>
 795     bool
 796     vector<bool, _Alloc>::
 797     _M_shrink_to_fit()
 798     {
 799       if (capacity() - size() < int(_S_word_bit))
 800         return false;
 801       __try
 802         {
 803           _M_reallocate(size());
 804           return true;
 805         }
 806       __catch(...)
 807         { return false; }
 808     }
 809 #endif
 810
 811 _GLIBCXX_END_NAMESPACE_CONTAINER
 812 } // namespace std
 813
 814 #if __cplusplus >= 201103L
 815
 816 namespace std _GLIBCXX_VISIBILITY(default)
 817 {
 818 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 819
 820   template<typename _Alloc>
 821     size_t
 822     hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>::
 823     operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept
 824     {
 825       size_t __hash = 0;
 826       using _GLIBCXX_STD_C::_S_word_bit;
 827       using _GLIBCXX_STD_C::_Bit_type;
 828
 829       const size_t __words = __b.size() / _S_word_bit;
 830       if (__words)
 831         {
 832           const size_t __clength = __words * sizeof(_Bit_type);
 833           __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength);
 834         }
 835
 836       const size_t __extrabits = __b.size() % _S_word_bit;
 837       if (__extrabits)
 838         {
 839           _Bit_type __hiword = *__b._M_impl._M_finish._M_p;
 840           __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits);
 841
 842           const size_t __clength
 843             = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__;
 844           if (__words)
 845             __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash);
 846           else
 847             __hash = std::_Hash_impl::hash(&__hiword, __clength);
 848         }
 849
 850       return __hash;
 851     }
 852
 853 _GLIBCXX_END_NAMESPACE_VERSION
 854 } // namespace std
 855
 856 #endif // C++11
 857
 858 #endif /* _VECTOR_TCC */