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