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

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