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

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