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 // 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 vector.tcc
  53  *  This is an internal header file, included by other library headers.
  54  *  You should not attempt to use it directly.
  55  */
  56
  57 #ifndef _VECTOR_TCC
  58 #define _VECTOR_TCC 1
  59
  60 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
  61
  62   template<typename _Tp, typename _Alloc>
  63     void
  64     vector<_Tp, _Alloc>::
  65     reserve(size_type __n)
  66     {
  67       if (__n > this->max_size())
  68         __throw_length_error(__N("vector::reserve"));
  69       if (this->capacity() < __n)
  70         {
  71           const size_type __old_size = size();
  72           pointer __tmp = _M_allocate_and_copy(__n,
  73                  _GLIBCXX_MAKE_MOVE_ITERATOR(this->_M_impl._M_start),
  74                  _GLIBCXX_MAKE_MOVE_ITERATOR(this->_M_impl._M_finish));
  75           std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
  76                         _M_get_Tp_allocator());
  77           _M_deallocate(this->_M_impl._M_start,
  78                         this->_M_impl._M_end_of_storage
  79                         - this->_M_impl._M_start);
  80           this->_M_impl._M_start = __tmp;
  81           this->_M_impl._M_finish = __tmp + __old_size;
  82           this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
  83         }
  84     }
  85
  86 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  87   template<typename _Tp, typename _Alloc>
  88     template<typename... _Args>
  89       void
  90       vector<_Tp, _Alloc>::
  91       emplace_back(_Args&&... __args)
  92       {
  93         if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
  94           {
  95             this->_M_impl.construct(this->_M_impl._M_finish,
  96                                     std::forward<_Args>(__args)...);
  97             ++this->_M_impl._M_finish;
  98           }
  99         else
 100           _M_insert_aux(end(), std::forward<_Args>(__args)...);
 101       }
 102 #endif
 103
 104   template<typename _Tp, typename _Alloc>
 105     typename vector<_Tp, _Alloc>::iterator
 106     vector<_Tp, _Alloc>::
 107     insert(iterator __position, const value_type& __x)
 108     {
 109       const size_type __n = __position - begin();
 110       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
 111           && __position == end())
 112         {
 113           this->_M_impl.construct(this->_M_impl._M_finish, __x);
 114           ++this->_M_impl._M_finish;
 115         }
 116       else
 117         {
 118 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 119           if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
 120             {
 121               _Tp __x_copy = __x;
 122               _M_insert_aux(__position, std::move(__x_copy));
 123             }
 124           else
 125 #endif
 126             _M_insert_aux(__position, __x);
 127         }
 128       return iterator(this->_M_impl._M_start + __n);
 129     }
 130
 131   template<typename _Tp, typename _Alloc>
 132     typename vector<_Tp, _Alloc>::iterator
 133     vector<_Tp, _Alloc>::
 134     erase(iterator __position)
 135     {
 136       if (__position + 1 != end())
 137         _GLIBCXX_MOVE3(__position + 1, end(), __position);
 138       --this->_M_impl._M_finish;
 139       this->_M_impl.destroy(this->_M_impl._M_finish);
 140       return __position;
 141     }
 142
 143   template<typename _Tp, typename _Alloc>
 144     typename vector<_Tp, _Alloc>::iterator
 145     vector<_Tp, _Alloc>::
 146     erase(iterator __first, iterator __last)
 147     {
 148       if (__last != end())
 149         _GLIBCXX_MOVE3(__last, end(), __first);
 150       _M_erase_at_end(__first.base() + (end() - __last));
 151       return __first;
 152     }
 153
 154   template<typename _Tp, typename _Alloc>
 155     vector<_Tp, _Alloc>&
 156     vector<_Tp, _Alloc>::
 157     operator=(const vector<_Tp, _Alloc>& __x)
 158     {
 159       if (&__x != this)
 160         {
 161           const size_type __xlen = __x.size();
 162           if (__xlen > capacity())
 163             {
 164               pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
 165                                                    __x.end());
 166               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 167                             _M_get_Tp_allocator());
 168               _M_deallocate(this->_M_impl._M_start,
 169                             this->_M_impl._M_end_of_storage
 170                             - this->_M_impl._M_start);
 171               this->_M_impl._M_start = __tmp;
 172               this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
 173             }
 174           else if (size() >= __xlen)
 175             {
 176               std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
 177                             end(), _M_get_Tp_allocator());
 178             }
 179           else
 180             {
 181               std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
 182                         this->_M_impl._M_start);
 183               std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
 184                                           __x._M_impl._M_finish,
 185                                           this->_M_impl._M_finish,
 186                                           _M_get_Tp_allocator());
 187             }
 188           this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
 189         }
 190       return *this;
 191     }
 192
 193   template<typename _Tp, typename _Alloc>
 194     void
 195     vector<_Tp, _Alloc>::
 196     _M_fill_assign(size_t __n, const value_type& __val)
 197     {
 198       if (__n > capacity())
 199         {
 200           vector __tmp(__n, __val, _M_get_Tp_allocator());
 201           __tmp.swap(*this);
 202         }
 203       else if (__n > size())
 204         {
 205           std::fill(begin(), end(), __val);
 206           std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
 207                                         __n - size(), __val,
 208                                         _M_get_Tp_allocator());
 209           this->_M_impl._M_finish += __n - size();
 210         }
 211       else
 212         _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
 213     }
 214
 215   template<typename _Tp, typename _Alloc>
 216     template<typename _InputIterator>
 217       void
 218       vector<_Tp, _Alloc>::
 219       _M_assign_aux(_InputIterator __first, _InputIterator __last,
 220                     std::input_iterator_tag)
 221       {
 222         pointer __cur(this->_M_impl._M_start);
 223         for (; __first != __last && __cur != this->_M_impl._M_finish;
 224              ++__cur, ++__first)
 225           *__cur = *__first;
 226         if (__first == __last)
 227           _M_erase_at_end(__cur);
 228         else
 229           insert(end(), __first, __last);
 230       }
 231
 232   template<typename _Tp, typename _Alloc>
 233     template<typename _ForwardIterator>
 234       void
 235       vector<_Tp, _Alloc>::
 236       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
 237                     std::forward_iterator_tag)
 238       {
 239         const size_type __len = std::distance(__first, __last);
 240
 241         if (__len > capacity())
 242           {
 243             pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
 244             std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 245                           _M_get_Tp_allocator());
 246             _M_deallocate(this->_M_impl._M_start,
 247                           this->_M_impl._M_end_of_storage
 248                           - this->_M_impl._M_start);
 249             this->_M_impl._M_start = __tmp;
 250             this->_M_impl._M_finish = this->_M_impl._M_start + __len;
 251             this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
 252           }
 253         else if (size() >= __len)
 254           _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
 255         else
 256           {
 257             _ForwardIterator __mid = __first;
 258             std::advance(__mid, size());
 259             std::copy(__first, __mid, this->_M_impl._M_start);
 260             this->_M_impl._M_finish =
 261               std::__uninitialized_copy_a(__mid, __last,
 262                                           this->_M_impl._M_finish,
 263                                           _M_get_Tp_allocator());
 264           }
 265       }
 266
 267 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 268   template<typename _Tp, typename _Alloc>
 269     template<typename... _Args>
 270       typename vector<_Tp, _Alloc>::iterator
 271       vector<_Tp, _Alloc>::
 272       emplace(iterator __position, _Args&&... __args)
 273       {
 274         const size_type __n = __position - begin();
 275         if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
 276             && __position == end())
 277           {
 278             this->_M_impl.construct(this->_M_impl._M_finish,
 279                                     std::forward<_Args>(__args)...);
 280             ++this->_M_impl._M_finish;
 281           }
 282         else
 283           _M_insert_aux(__position, std::forward<_Args>(__args)...);
 284         return iterator(this->_M_impl._M_start + __n);
 285       }
 286
 287   template<typename _Tp, typename _Alloc>
 288     template<typename... _Args>
 289       void
 290       vector<_Tp, _Alloc>::
 291       _M_insert_aux(iterator __position, _Args&&... __args)
 292 #else
 293   template<typename _Tp, typename _Alloc>
 294     void
 295     vector<_Tp, _Alloc>::
 296     _M_insert_aux(iterator __position, const _Tp& __x)
 297 #endif
 298     {
 299       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
 300         {
 301           this->_M_impl.construct(this->_M_impl._M_finish,
 302                                   _GLIBCXX_MOVE(*(this->_M_impl._M_finish
 303                                                   - 1)));
 304           ++this->_M_impl._M_finish;
 305 #ifndef __GXX_EXPERIMENTAL_CXX0X__
 306           _Tp __x_copy = __x;
 307 #endif
 308           _GLIBCXX_MOVE_BACKWARD3(__position.base(),
 309                                   this->_M_impl._M_finish - 2,
 310                                   this->_M_impl._M_finish - 1);
 311 #ifndef __GXX_EXPERIMENTAL_CXX0X__
 312           *__position = __x_copy;
 313 #else
 314           *__position = _Tp(std::forward<_Args>(__args)...);
 315 #endif
 316         }
 317       else
 318         {
 319           const size_type __len =
 320             _M_check_len(size_type(1), "vector::_M_insert_aux");
 321           const size_type __elems_before = __position - begin();
 322           pointer __new_start(this->_M_allocate(__len));
 323           pointer __new_finish(__new_start);
 324           __try
 325             {
 326               // The order of the three operations is dictated by the C++0x
 327               // case, where the moves could alter a new element belonging
 328               // to the existing vector.  This is an issue only for callers
 329               // taking the element by const lvalue ref (see 23.1/13).
 330               this->_M_impl.construct(__new_start + __elems_before,
 331 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 332                                       std::forward<_Args>(__args)...);
 333 #else
 334                                       __x);
 335 #endif
 336               __new_finish = 0;
 337
 338               __new_finish =
 339                 std::__uninitialized_move_a(this->_M_impl._M_start,
 340                                             __position.base(), __new_start,
 341                                             _M_get_Tp_allocator());
 342               ++__new_finish;
 343
 344               __new_finish =
 345                 std::__uninitialized_move_a(__position.base(),
 346                                             this->_M_impl._M_finish,
 347                                             __new_finish,
 348                                             _M_get_Tp_allocator());
 349             }
 350           __catch(...)
 351             {
 352               if (!__new_finish)
 353                 this->_M_impl.destroy(__new_start + __elems_before);
 354               else
 355                 std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
 356               _M_deallocate(__new_start, __len);
 357               __throw_exception_again;
 358             }
 359           std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 360                         _M_get_Tp_allocator());
 361           _M_deallocate(this->_M_impl._M_start,
 362                         this->_M_impl._M_end_of_storage
 363                         - this->_M_impl._M_start);
 364           this->_M_impl._M_start = __new_start;
 365           this->_M_impl._M_finish = __new_finish;
 366           this->_M_impl._M_end_of_storage = __new_start + __len;
 367         }
 368     }
 369
 370   template<typename _Tp, typename _Alloc>
 371     void
 372     vector<_Tp, _Alloc>::
 373     _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
 374     {
 375       if (__n != 0)
 376         {
 377           if (size_type(this->_M_impl._M_end_of_storage
 378                         - this->_M_impl._M_finish) >= __n)
 379             {
 380               value_type __x_copy = __x;
 381               const size_type __elems_after = end() - __position;
 382               pointer __old_finish(this->_M_impl._M_finish);
 383               if (__elems_after > __n)
 384                 {
 385                   std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
 386                                               this->_M_impl._M_finish,
 387                                               this->_M_impl._M_finish,
 388                                               _M_get_Tp_allocator());
 389                   this->_M_impl._M_finish += __n;
 390                   _GLIBCXX_MOVE_BACKWARD3(__position.base(),
 391                                           __old_finish - __n, __old_finish);
 392                   std::fill(__position.base(), __position.base() + __n,
 393                             __x_copy);
 394                 }
 395               else
 396                 {
 397                   std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
 398                                                 __n - __elems_after,
 399                                                 __x_copy,
 400                                                 _M_get_Tp_allocator());
 401                   this->_M_impl._M_finish += __n - __elems_after;
 402                   std::__uninitialized_move_a(__position.base(), __old_finish,
 403                                               this->_M_impl._M_finish,
 404                                               _M_get_Tp_allocator());
 405                   this->_M_impl._M_finish += __elems_after;
 406                   std::fill(__position.base(), __old_finish, __x_copy);
 407                 }
 408             }
 409           else
 410             {
 411               const size_type __len =
 412                 _M_check_len(__n, "vector::_M_fill_insert");
 413               const size_type __elems_before = __position - begin();
 414               pointer __new_start(this->_M_allocate(__len));
 415               pointer __new_finish(__new_start);
 416               __try
 417                 {
 418                   // See _M_insert_aux above.
 419                   std::__uninitialized_fill_n_a(__new_start + __elems_before,
 420                                                 __n, __x,
 421                                                 _M_get_Tp_allocator());
 422                   __new_finish = 0;
 423
 424                   __new_finish =
 425                     std::__uninitialized_move_a(this->_M_impl._M_start,
 426                                                 __position.base(),
 427                                                 __new_start,
 428                                                 _M_get_Tp_allocator());
 429                   __new_finish += __n;
 430
 431                   __new_finish =
 432                     std::__uninitialized_move_a(__position.base(),
 433                                                 this->_M_impl._M_finish,
 434                                                 __new_finish,
 435                                                 _M_get_Tp_allocator());
 436                 }
 437               __catch(...)
 438                 {
 439                   if (!__new_finish)
 440                     std::_Destroy(__new_start + __elems_before,
 441                                   __new_start + __elems_before + __n,
 442                                   _M_get_Tp_allocator());
 443                   else
 444                     std::_Destroy(__new_start, __new_finish,
 445                                   _M_get_Tp_allocator());
 446                   _M_deallocate(__new_start, __len);
 447                   __throw_exception_again;
 448                 }
 449               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 450                             _M_get_Tp_allocator());
 451               _M_deallocate(this->_M_impl._M_start,
 452                             this->_M_impl._M_end_of_storage
 453                             - this->_M_impl._M_start);
 454               this->_M_impl._M_start = __new_start;
 455               this->_M_impl._M_finish = __new_finish;
 456               this->_M_impl._M_end_of_storage = __new_start + __len;
 457             }
 458         }
 459     }
 460
 461 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 462   template<typename _Tp, typename _Alloc>
 463     void
 464     vector<_Tp, _Alloc>::
 465     _M_default_append(size_type __n)
 466     {
 467       if (__n != 0)
 468         {
 469           if (size_type(this->_M_impl._M_end_of_storage
 470                         - this->_M_impl._M_finish) >= __n)
 471             {
 472               std::__uninitialized_default_n_a(this->_M_impl._M_finish,
 473                                                __n, _M_get_Tp_allocator());
 474               this->_M_impl._M_finish += __n;
 475             }
 476           else
 477             {
 478               const size_type __len =
 479                 _M_check_len(__n, "vector::_M_default_append");
 480               const size_type __old_size = this->size();
 481               pointer __new_start(this->_M_allocate(__len));
 482               pointer __new_finish(__new_start);
 483               __try
 484                 {
 485                   __new_finish =
 486                     std::__uninitialized_move_a(this->_M_impl._M_start,
 487                                                 this->_M_impl._M_finish,
 488                                                 __new_start,
 489                                                 _M_get_Tp_allocator());
 490                   std::__uninitialized_default_n_a(__new_finish, __n,
 491                                                    _M_get_Tp_allocator());
 492                   __new_finish += __n;
 493                 }
 494               __catch(...)
 495                 {
 496                   std::_Destroy(__new_start, __new_finish,
 497                                 _M_get_Tp_allocator());
 498                   _M_deallocate(__new_start, __len);
 499                   __throw_exception_again;
 500                 }
 501               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 502                             _M_get_Tp_allocator());
 503               _M_deallocate(this->_M_impl._M_start,
 504                             this->_M_impl._M_end_of_storage
 505                             - this->_M_impl._M_start);
 506               this->_M_impl._M_start = __new_start;
 507               this->_M_impl._M_finish = __new_finish;
 508               this->_M_impl._M_end_of_storage = __new_start + __len;
 509             }
 510         }
 511     }
 512 #endif
 513
 514   template<typename _Tp, typename _Alloc>
 515     template<typename _InputIterator>
 516       void
 517       vector<_Tp, _Alloc>::
 518       _M_range_insert(iterator __pos, _InputIterator __first,
 519                       _InputIterator __last, std::input_iterator_tag)
 520       {
 521         for (; __first != __last; ++__first)
 522           {
 523             __pos = insert(__pos, *__first);
 524             ++__pos;
 525           }
 526       }
 527
 528   template<typename _Tp, typename _Alloc>
 529     template<typename _ForwardIterator>
 530       void
 531       vector<_Tp, _Alloc>::
 532       _M_range_insert(iterator __position, _ForwardIterator __first,
 533                       _ForwardIterator __last, std::forward_iterator_tag)
 534       {
 535         if (__first != __last)
 536           {
 537             const size_type __n = std::distance(__first, __last);
 538             if (size_type(this->_M_impl._M_end_of_storage
 539                           - this->_M_impl._M_finish) >= __n)
 540               {
 541                 const size_type __elems_after = end() - __position;
 542                 pointer __old_finish(this->_M_impl._M_finish);
 543                 if (__elems_after > __n)
 544                   {
 545                     std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
 546                                                 this->_M_impl._M_finish,
 547                                                 this->_M_impl._M_finish,
 548                                                 _M_get_Tp_allocator());
 549                     this->_M_impl._M_finish += __n;
 550                     _GLIBCXX_MOVE_BACKWARD3(__position.base(),
 551                                             __old_finish - __n, __old_finish);
 552                     std::copy(__first, __last, __position);
 553                   }
 554                 else
 555                   {
 556                     _ForwardIterator __mid = __first;
 557                     std::advance(__mid, __elems_after);
 558                     std::__uninitialized_copy_a(__mid, __last,
 559                                                 this->_M_impl._M_finish,
 560                                                 _M_get_Tp_allocator());
 561                     this->_M_impl._M_finish += __n - __elems_after;
 562                     std::__uninitialized_move_a(__position.base(),
 563                                                 __old_finish,
 564                                                 this->_M_impl._M_finish,
 565                                                 _M_get_Tp_allocator());
 566                     this->_M_impl._M_finish += __elems_after;
 567                     std::copy(__first, __mid, __position);
 568                   }
 569               }
 570             else
 571               {
 572                 const size_type __len =
 573                   _M_check_len(__n, "vector::_M_range_insert");
 574                 pointer __new_start(this->_M_allocate(__len));
 575                 pointer __new_finish(__new_start);
 576                 __try
 577                   {
 578                     __new_finish =
 579                       std::__uninitialized_move_a(this->_M_impl._M_start,
 580                                                   __position.base(),
 581                                                   __new_start,
 582                                                   _M_get_Tp_allocator());
 583                     __new_finish =
 584                       std::__uninitialized_copy_a(__first, __last,
 585                                                   __new_finish,
 586                                                   _M_get_Tp_allocator());
 587                     __new_finish =
 588                       std::__uninitialized_move_a(__position.base(),
 589                                                   this->_M_impl._M_finish,
 590                                                   __new_finish,
 591                                                   _M_get_Tp_allocator());
 592                   }
 593                 __catch(...)
 594                   {
 595                     std::_Destroy(__new_start, __new_finish,
 596                                   _M_get_Tp_allocator());
 597                     _M_deallocate(__new_start, __len);
 598                     __throw_exception_again;
 599                   }
 600                 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 601                               _M_get_Tp_allocator());
 602                 _M_deallocate(this->_M_impl._M_start,
 603                               this->_M_impl._M_end_of_storage
 604                               - this->_M_impl._M_start);
 605                 this->_M_impl._M_start = __new_start;
 606                 this->_M_impl._M_finish = __new_finish;
 607                 this->_M_impl._M_end_of_storage = __new_start + __len;
 608               }
 609           }
 610       }
 611
 612
 613   // vector<bool>
 614
 615   template<typename _Alloc>
 616     void
 617     vector<bool, _Alloc>::
 618     reserve(size_type __n)
 619     {
 620       if (__n > this->max_size())
 621         __throw_length_error(__N("vector::reserve"));
 622       if (this->capacity() < __n)
 623         {
 624           _Bit_type* __q = this->_M_allocate(__n);
 625           this->_M_impl._M_finish = _M_copy_aligned(begin(), end(),
 626                                                     iterator(__q, 0));
 627           this->_M_deallocate();
 628           this->_M_impl._M_start = iterator(__q, 0);
 629           this->_M_impl._M_end_of_storage = (__q + (__n + int(_S_word_bit) - 1)
 630                                              / int(_S_word_bit));
 631         }
 632     }
 633
 634   template<typename _Alloc>
 635     void
 636     vector<bool, _Alloc>::
 637     _M_fill_insert(iterator __position, size_type __n, bool __x)
 638     {
 639       if (__n == 0)
 640         return;
 641       if (capacity() - size() >= __n)
 642         {
 643           std::copy_backward(__position, end(),
 644                              this->_M_impl._M_finish + difference_type(__n));
 645           std::fill(__position, __position + difference_type(__n), __x);
 646           this->_M_impl._M_finish += difference_type(__n);
 647         }
 648       else
 649         {
 650           const size_type __len =
 651             _M_check_len(__n, "vector<bool>::_M_fill_insert");
 652           _Bit_type * __q = this->_M_allocate(__len);
 653           iterator __i = _M_copy_aligned(begin(), __position,
 654                                          iterator(__q, 0));
 655           std::fill(__i, __i + difference_type(__n), __x);
 656           this->_M_impl._M_finish = std::copy(__position, end(),
 657                                               __i + difference_type(__n));
 658           this->_M_deallocate();
 659           this->_M_impl._M_end_of_storage = (__q + ((__len
 660                                                      + int(_S_word_bit) - 1)
 661                                                     / int(_S_word_bit)));
 662           this->_M_impl._M_start = iterator(__q, 0);
 663         }
 664     }
 665
 666   template<typename _Alloc>
 667     template<typename _ForwardIterator>
 668       void
 669       vector<bool, _Alloc>::
 670       _M_insert_range(iterator __position, _ForwardIterator __first,
 671                       _ForwardIterator __last, std::forward_iterator_tag)
 672       {
 673         if (__first != __last)
 674           {
 675             size_type __n = std::distance(__first, __last);
 676             if (capacity() - size() >= __n)
 677               {
 678                 std::copy_backward(__position, end(),
 679                                    this->_M_impl._M_finish
 680                                    + difference_type(__n));
 681                 std::copy(__first, __last, __position);
 682                 this->_M_impl._M_finish += difference_type(__n);
 683               }
 684             else
 685               {
 686                 const size_type __len =
 687                   _M_check_len(__n, "vector<bool>::_M_insert_range");
 688                 _Bit_type * __q = this->_M_allocate(__len);
 689                 iterator __i = _M_copy_aligned(begin(), __position,
 690                                                iterator(__q, 0));
 691                 __i = std::copy(__first, __last, __i);
 692                 this->_M_impl._M_finish = std::copy(__position, end(), __i);
 693                 this->_M_deallocate();
 694                 this->_M_impl._M_end_of_storage = (__q
 695                                                    + ((__len
 696                                                        + int(_S_word_bit) - 1)
 697                                                       / int(_S_word_bit)));
 698                 this->_M_impl._M_start = iterator(__q, 0);
 699               }
 700           }
 701       }
 702
 703   template<typename _Alloc>
 704     void
 705     vector<bool, _Alloc>::
 706     _M_insert_aux(iterator __position, bool __x)
 707     {
 708       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
 709         {
 710           std::copy_backward(__position, this->_M_impl._M_finish,
 711                              this->_M_impl._M_finish + 1);
 712           *__position = __x;
 713           ++this->_M_impl._M_finish;
 714         }
 715       else
 716         {
 717           const size_type __len =
 718             _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
 719           _Bit_type * __q = this->_M_allocate(__len);
 720           iterator __i = _M_copy_aligned(begin(), __position,
 721                                          iterator(__q, 0));
 722           *__i++ = __x;
 723           this->_M_impl._M_finish = std::copy(__position, end(), __i);
 724           this->_M_deallocate();
 725           this->_M_impl._M_end_of_storage = (__q + ((__len
 726                                                      + int(_S_word_bit) - 1)
 727                                                     / int(_S_word_bit)));
 728           this->_M_impl._M_start = iterator(__q, 0);
 729         }
 730     }
 731
 732 _GLIBCXX_END_NESTED_NAMESPACE
 733
 734 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 735
 736 _GLIBCXX_BEGIN_NAMESPACE(std)
 737
 738   template<typename _Alloc>
 739     size_t
 740     hash<_GLIBCXX_STD_D::vector<bool, _Alloc>>::
 741     operator()(const _GLIBCXX_STD_D::vector<bool, _Alloc>& __b) const
 742     {
 743       size_t __hash = 0;
 744       using _GLIBCXX_STD_D::_S_word_bit;
 745       using _GLIBCXX_STD_D::_Bit_type;
 746
 747       const size_t __words = __b.size() / _S_word_bit;
 748       if (__words)
 749         {
 750           const size_t __clength = __words * sizeof(_Bit_type);
 751           __hash = std::_Fnv_hash::hash(__b._M_impl._M_start._M_p, __clength);
 752         }
 753
 754       const size_t __extrabits = __b.size() % _S_word_bit;
 755       if (__extrabits)
 756         {
 757           _Bit_type __hiword = *__b._M_impl._M_finish._M_p;
 758           __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits);
 759
 760           const size_t __clength
 761             = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__;
 762           if (__words)
 763             __hash = std::_Fnv_hash::hash(&__hiword, __clength, __hash);
 764           else
 765             __hash = std::_Fnv_hash::hash(&__hiword, __clength);
 766         }
 767
 768       return __hash;
 769     }
 770
 771 _GLIBCXX_END_NAMESPACE
 772
 773 #endif // __GXX_EXPERIMENTAL_CXX0X__
 774
 775 #endif /* _VECTOR_TCC */