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