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

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