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

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