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

   1 // Vector implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
   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 2, 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 // You should have received a copy of the GNU General Public License along
  18 // with this library; see the file COPYING.  If not, write to the Free
  19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  20 // USA.
  21
  22 // As a special exception, you may use this file as part of a free software
  23 // library without restriction.  Specifically, if other files instantiate
  24 // templates or use macros or inline functions from this file, or you compile
  25 // this file and link it with other files to produce an executable, this
  26 // file does not by itself cause the resulting executable to be covered by
  27 // the GNU General Public License.  This exception does not however
  28 // invalidate any other reasons why the executable file might be covered by
  29 // the GNU General Public License.
  30
  31 /*
  32  *
  33  * Copyright (c) 1994
  34  * Hewlett-Packard Company
  35  *
  36  * Permission to use, copy, modify, distribute and sell this software
  37  * and its documentation for any purpose is hereby granted without fee,
  38  * provided that the above copyright notice appear in all copies and
  39  * that both that copyright notice and this permission notice appear
  40  * in supporting documentation.  Hewlett-Packard Company makes no
  41  * representations about the suitability of this software for any
  42  * purpose.  It is provided "as is" without express or implied warranty.
  43  *
  44  *
  45  * Copyright (c) 1996
  46  * Silicon Graphics Computer Systems, Inc.
  47  *
  48  * Permission to use, copy, modify, distribute and sell this software
  49  * and its documentation for any purpose is hereby granted without fee,
  50  * provided that the above copyright notice appear in all copies and
  51  * that both that copyright notice and this permission notice appear
  52  * in supporting documentation.  Silicon Graphics makes no
  53  * representations about the suitability of this  software for any
  54  * purpose.  It is provided "as is" without express or implied warranty.
  55  */
  56
  57 /** @file vector.tcc
  58  *  This is an internal header file, included by other library headers.
  59  *  You should not attempt to use it directly.
  60  */
  61
  62 #ifndef _VECTOR_TCC
  63 #define _VECTOR_TCC 1
  64
  65 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
  66
  67   template<typename _Tp, typename _Alloc>
  68     void
  69     vector<_Tp, _Alloc>::
  70     reserve(size_type __n)
  71     {
  72       if (__n > this->max_size())
  73         __throw_length_error(__N("vector::reserve"));
  74       if (this->capacity() < __n)
  75         {
  76           const size_type __old_size = size();
  77           pointer __tmp = _M_allocate_and_copy(__n,
  78                  _GLIBCXX_MAKE_MOVE_ITERATOR(this->_M_impl._M_start),
  79                  _GLIBCXX_MAKE_MOVE_ITERATOR(this->_M_impl._M_finish));
  80           std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
  81                         _M_get_Tp_allocator());
  82           _M_deallocate(this->_M_impl._M_start,
  83                         this->_M_impl._M_end_of_storage
  84                         - this->_M_impl._M_start);
  85           this->_M_impl._M_start = __tmp;
  86           this->_M_impl._M_finish = __tmp + __old_size;
  87           this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
  88         }
  89     }
  90
  91   template<typename _Tp, typename _Alloc>
  92     typename vector<_Tp, _Alloc>::iterator
  93     vector<_Tp, _Alloc>::
  94     insert(iterator __position, const value_type& __x)
  95     {
  96       const size_type __n = __position - begin();
  97       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
  98           && __position == end())
  99         {
 100           this->_M_impl.construct(this->_M_impl._M_finish, __x);
 101           ++this->_M_impl._M_finish;
 102         }
 103       else
 104         _M_insert_aux(__position, __x);
 105       return iterator(this->_M_impl._M_start + __n);
 106     }
 107
 108 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 109   template<typename _Tp, typename _Alloc>
 110     typename vector<_Tp, _Alloc>::iterator
 111     vector<_Tp, _Alloc>::
 112     insert(iterator __position, value_type&& __x)
 113     {
 114       const size_type __n = __position - begin();
 115       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
 116           && __position == end())
 117         {
 118           this->_M_impl.construct(this->_M_impl._M_finish,
 119                                   std::forward<value_type>(__x));
 120           ++this->_M_impl._M_finish;
 121         }
 122       else
 123         _M_insert_aux(__position, std::forward<value_type>(__x));
 124       return iterator(this->_M_impl._M_start + __n);
 125     }
 126 #endif
 127
 128   template<typename _Tp, typename _Alloc>
 129     typename vector<_Tp, _Alloc>::iterator
 130     vector<_Tp, _Alloc>::
 131     erase(iterator __position)
 132     {
 133       if (__position + 1 != end())
 134         _GLIBCXX_MOVE3(__position + 1, end(), __position);
 135       --this->_M_impl._M_finish;
 136       this->_M_impl.destroy(this->_M_impl._M_finish);
 137       return __position;
 138     }
 139
 140   template<typename _Tp, typename _Alloc>
 141     typename vector<_Tp, _Alloc>::iterator
 142     vector<_Tp, _Alloc>::
 143     erase(iterator __first, iterator __last)
 144     {
 145       if (__last != end())
 146         _GLIBCXX_MOVE3(__last, end(), __first);
 147       _M_erase_at_end(__first.base() + (end() - __last));
 148       return __first;
 149     }
 150
 151   template<typename _Tp, typename _Alloc>
 152     vector<_Tp, _Alloc>&
 153     vector<_Tp, _Alloc>::
 154     operator=(const vector<_Tp, _Alloc>& __x)
 155     {
 156       if (&__x != this)
 157         {
 158           const size_type __xlen = __x.size();
 159           if (__xlen > capacity())
 160             {
 161               pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
 162                                                    __x.end());
 163               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 164                             _M_get_Tp_allocator());
 165               _M_deallocate(this->_M_impl._M_start,
 166                             this->_M_impl._M_end_of_storage
 167                             - this->_M_impl._M_start);
 168               this->_M_impl._M_start = __tmp;
 169               this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
 170             }
 171           else if (size() >= __xlen)
 172             {
 173               std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
 174                             end(), _M_get_Tp_allocator());
 175             }
 176           else
 177             {
 178               std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
 179                         this->_M_impl._M_start);
 180               std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
 181                                           __x._M_impl._M_finish,
 182                                           this->_M_impl._M_finish,
 183                                           _M_get_Tp_allocator());
 184             }
 185           this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
 186         }
 187       return *this;
 188     }
 189
 190   template<typename _Tp, typename _Alloc>
 191     void
 192     vector<_Tp, _Alloc>::
 193     _M_fill_assign(size_t __n, const value_type& __val)
 194     {
 195       if (__n > capacity())
 196         {
 197           vector __tmp(__n, __val, _M_get_Tp_allocator());
 198           __tmp.swap(*this);
 199         }
 200       else if (__n > size())
 201         {
 202           std::fill(begin(), end(), __val);
 203           std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
 204                                         __n - size(), __val,
 205                                         _M_get_Tp_allocator());
 206           this->_M_impl._M_finish += __n - size();
 207         }
 208       else
 209         _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
 210     }
 211
 212   template<typename _Tp, typename _Alloc>
 213     template<typename _InputIterator>
 214       void
 215       vector<_Tp, _Alloc>::
 216       _M_assign_aux(_InputIterator __first, _InputIterator __last,
 217                     std::input_iterator_tag)
 218       {
 219         pointer __cur(this->_M_impl._M_start);
 220         for (; __first != __last && __cur != this->_M_impl._M_finish;
 221              ++__cur, ++__first)
 222           *__cur = *__first;
 223         if (__first == __last)
 224           _M_erase_at_end(__cur);
 225         else
 226           insert(end(), __first, __last);
 227       }
 228
 229   template<typename _Tp, typename _Alloc>
 230     template<typename _ForwardIterator>
 231       void
 232       vector<_Tp, _Alloc>::
 233       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
 234                     std::forward_iterator_tag)
 235       {
 236         const size_type __len = std::distance(__first, __last);
 237
 238         if (__len > capacity())
 239           {
 240             pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
 241             std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 242                           _M_get_Tp_allocator());
 243             _M_deallocate(this->_M_impl._M_start,
 244                           this->_M_impl._M_end_of_storage
 245                           - this->_M_impl._M_start);
 246             this->_M_impl._M_start = __tmp;
 247             this->_M_impl._M_finish = this->_M_impl._M_start + __len;
 248             this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
 249           }
 250         else if (size() >= __len)
 251           _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
 252         else
 253           {
 254             _ForwardIterator __mid = __first;
 255             std::advance(__mid, size());
 256             std::copy(__first, __mid, this->_M_impl._M_start);
 257             this->_M_impl._M_finish =
 258               std::__uninitialized_copy_a(__mid, __last,
 259                                           this->_M_impl._M_finish,
 260                                           _M_get_Tp_allocator());
 261           }
 262       }
 263
 264 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 265   template<typename _Tp, typename _Alloc>
 266     template<typename... _Args>
 267       typename vector<_Tp, _Alloc>::iterator
 268       vector<_Tp, _Alloc>::
 269       emplace(iterator __position, _Args&&... __args)
 270       {
 271         const size_type __n = __position - begin();
 272         if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
 273             && __position == end())
 274           {
 275             this->_M_impl.construct(this->_M_impl._M_finish,
 276                                     std::forward<_Args>(__args)...);
 277             ++this->_M_impl._M_finish;
 278           }
 279         else
 280           _M_insert_aux(__position, std::forward<_Args>(__args)...);
 281         return iterator(this->_M_impl._M_start + __n);
 282       }
 283
 284   template<typename _Tp, typename _Alloc>
 285     template<typename... _Args>
 286       void
 287       vector<_Tp, _Alloc>::
 288       _M_insert_aux(iterator __position, _Args&&... __args)
 289       {
 290         _Tp __x_copy(std::forward<_Args>(__args)...);
 291 #else
 292   template<typename _Tp, typename _Alloc>
 293     void
 294     vector<_Tp, _Alloc>::
 295     _M_insert_aux(iterator __position, const _Tp& __x)
 296     {
 297 #endif
 298       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
 299         {
 300           this->_M_impl.construct(this->_M_impl._M_finish,
 301                                   _GLIBCXX_MOVE(*(this->_M_impl._M_finish
 302                                                   - 1)));
 303           ++this->_M_impl._M_finish;
 304 #ifndef __GXX_EXPERIMENTAL_CXX0X__
 305           _Tp __x_copy = __x;
 306 #endif
 307           _GLIBCXX_MOVE_BACKWARD3(__position.base(),
 308                                   this->_M_impl._M_finish - 2,
 309                                   this->_M_impl._M_finish - 1);
 310           *__position = _GLIBCXX_MOVE(__x_copy);
 311         }
 312       else
 313         {
 314           const size_type __len =
 315             _M_check_len(size_type(1), "vector::_M_insert_aux");
 316           pointer __new_start(this->_M_allocate(__len));
 317           pointer __new_finish(__new_start);
 318           try
 319             {
 320               __new_finish =
 321                 std::__uninitialized_move_a(this->_M_impl._M_start,
 322                                             __position.base(), __new_start,
 323                                             _M_get_Tp_allocator());
 324 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 325               this->_M_impl.construct(__new_finish, std::move(__x_copy));
 326 #else
 327               this->_M_impl.construct(__new_finish, __x);
 328 #endif
 329               ++__new_finish;
 330               __new_finish =
 331                 std::__uninitialized_move_a(__position.base(),
 332                                             this->_M_impl._M_finish,
 333                                             __new_finish,
 334                                             _M_get_Tp_allocator());
 335             }
 336           catch(...)
 337             {
 338               std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
 339               _M_deallocate(__new_start, __len);
 340               __throw_exception_again;
 341             }
 342           std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 343                         _M_get_Tp_allocator());
 344           _M_deallocate(this->_M_impl._M_start,
 345                         this->_M_impl._M_end_of_storage
 346                         - this->_M_impl._M_start);
 347           this->_M_impl._M_start = __new_start;
 348           this->_M_impl._M_finish = __new_finish;
 349           this->_M_impl._M_end_of_storage = __new_start + __len;
 350         }
 351     }
 352
 353   template<typename _Tp, typename _Alloc>
 354     void
 355     vector<_Tp, _Alloc>::
 356     _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
 357     {
 358       if (__n != 0)
 359         {
 360 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 361           value_type __x_copy = __x;
 362 #endif
 363           if (size_type(this->_M_impl._M_end_of_storage
 364                         - this->_M_impl._M_finish) >= __n)
 365             {
 366 #ifndef __GXX_EXPERIMENTAL_CXX0X__
 367               value_type __x_copy = __x;
 368 #endif
 369               const size_type __elems_after = end() - __position;
 370               pointer __old_finish(this->_M_impl._M_finish);
 371               if (__elems_after > __n)
 372                 {
 373                   std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
 374                                               this->_M_impl._M_finish,
 375                                               this->_M_impl._M_finish,
 376                                               _M_get_Tp_allocator());
 377                   this->_M_impl._M_finish += __n;
 378                   _GLIBCXX_MOVE_BACKWARD3(__position.base(),
 379                                           __old_finish - __n, __old_finish);
 380                   std::fill(__position.base(), __position.base() + __n,
 381                             __x_copy);
 382                 }
 383               else
 384                 {
 385                   std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
 386                                                 __n - __elems_after,
 387                                                 __x_copy,
 388                                                 _M_get_Tp_allocator());
 389                   this->_M_impl._M_finish += __n - __elems_after;
 390                   std::__uninitialized_move_a(__position.base(), __old_finish,
 391                                               this->_M_impl._M_finish,
 392                                               _M_get_Tp_allocator());
 393                   this->_M_impl._M_finish += __elems_after;
 394                   std::fill(__position.base(), __old_finish, __x_copy);
 395                 }
 396             }
 397           else
 398             {
 399               const size_type __len =
 400                 _M_check_len(__n, "vector::_M_fill_insert");
 401               pointer __new_start(this->_M_allocate(__len));
 402               pointer __new_finish(__new_start);
 403               try
 404                 {
 405                   __new_finish =
 406                     std::__uninitialized_move_a(this->_M_impl._M_start,
 407                                                 __position.base(),
 408                                                 __new_start,
 409                                                 _M_get_Tp_allocator());
 410 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 411                   std::__uninitialized_fill_n_a(__new_finish, __n, __x_copy,
 412 #else
 413                   std::__uninitialized_fill_n_a(__new_finish, __n, __x,
 414 #endif
 415                                                 _M_get_Tp_allocator());
 416                   __new_finish += __n;
 417                   __new_finish =
 418                     std::__uninitialized_move_a(__position.base(),
 419                                                 this->_M_impl._M_finish,
 420                                                 __new_finish,
 421                                                 _M_get_Tp_allocator());
 422                 }
 423               catch(...)
 424                 {
 425                   std::_Destroy(__new_start, __new_finish,
 426                                 _M_get_Tp_allocator());
 427                   _M_deallocate(__new_start, __len);
 428                   __throw_exception_again;
 429                 }
 430               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 431                             _M_get_Tp_allocator());
 432               _M_deallocate(this->_M_impl._M_start,
 433                             this->_M_impl._M_end_of_storage
 434                             - this->_M_impl._M_start);
 435               this->_M_impl._M_start = __new_start;
 436               this->_M_impl._M_finish = __new_finish;
 437               this->_M_impl._M_end_of_storage = __new_start + __len;
 438             }
 439         }
 440     }
 441
 442   template<typename _Tp, typename _Alloc>
 443     template<typename _InputIterator>
 444       void
 445       vector<_Tp, _Alloc>::
 446       _M_range_insert(iterator __pos, _InputIterator __first,
 447                       _InputIterator __last, std::input_iterator_tag)
 448       {
 449         for (; __first != __last; ++__first)
 450           {
 451             __pos = insert(__pos, *__first);
 452             ++__pos;
 453           }
 454       }
 455
 456   template<typename _Tp, typename _Alloc>
 457     template<typename _ForwardIterator>
 458       void
 459       vector<_Tp, _Alloc>::
 460       _M_range_insert(iterator __position, _ForwardIterator __first,
 461                       _ForwardIterator __last, std::forward_iterator_tag)
 462       {
 463         if (__first != __last)
 464           {
 465             const size_type __n = std::distance(__first, __last);
 466             if (size_type(this->_M_impl._M_end_of_storage
 467                           - this->_M_impl._M_finish) >= __n)
 468               {
 469                 const size_type __elems_after = end() - __position;
 470                 pointer __old_finish(this->_M_impl._M_finish);
 471                 if (__elems_after > __n)
 472                   {
 473                     std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
 474                                                 this->_M_impl._M_finish,
 475                                                 this->_M_impl._M_finish,
 476                                                 _M_get_Tp_allocator());
 477                     this->_M_impl._M_finish += __n;
 478                     _GLIBCXX_MOVE_BACKWARD3(__position.base(),
 479                                             __old_finish - __n, __old_finish);
 480                     std::copy(__first, __last, __position);
 481                   }
 482                 else
 483                   {
 484                     _ForwardIterator __mid = __first;
 485                     std::advance(__mid, __elems_after);
 486                     std::__uninitialized_copy_a(__mid, __last,
 487                                                 this->_M_impl._M_finish,
 488                                                 _M_get_Tp_allocator());
 489                     this->_M_impl._M_finish += __n - __elems_after;
 490                     std::__uninitialized_move_a(__position.base(),
 491                                                 __old_finish,
 492                                                 this->_M_impl._M_finish,
 493                                                 _M_get_Tp_allocator());
 494                     this->_M_impl._M_finish += __elems_after;
 495                     std::copy(__first, __mid, __position);
 496                   }
 497               }
 498             else
 499               {
 500                 const size_type __len =
 501                   _M_check_len(__n, "vector::_M_range_insert");
 502                 pointer __new_start(this->_M_allocate(__len));
 503                 pointer __new_finish(__new_start);
 504                 try
 505                   {
 506                     __new_finish =
 507                       std::__uninitialized_move_a(this->_M_impl._M_start,
 508                                                   __position.base(),
 509                                                   __new_start,
 510                                                   _M_get_Tp_allocator());
 511                     __new_finish =
 512                       std::__uninitialized_copy_a(__first, __last,
 513                                                   __new_finish,
 514                                                   _M_get_Tp_allocator());
 515                     __new_finish =
 516                       std::__uninitialized_move_a(__position.base(),
 517                                                   this->_M_impl._M_finish,
 518                                                   __new_finish,
 519                                                   _M_get_Tp_allocator());
 520                   }
 521                 catch(...)
 522                   {
 523                     std::_Destroy(__new_start, __new_finish,
 524                                   _M_get_Tp_allocator());
 525                     _M_deallocate(__new_start, __len);
 526                     __throw_exception_again;
 527                   }
 528                 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
 529                               _M_get_Tp_allocator());
 530                 _M_deallocate(this->_M_impl._M_start,
 531                               this->_M_impl._M_end_of_storage
 532                               - this->_M_impl._M_start);
 533                 this->_M_impl._M_start = __new_start;
 534                 this->_M_impl._M_finish = __new_finish;
 535                 this->_M_impl._M_end_of_storage = __new_start + __len;
 536               }
 537           }
 538       }
 539
 540
 541   // vector<bool>
 542
 543   template<typename _Alloc>
 544     void
 545     vector<bool, _Alloc>::
 546     _M_fill_insert(iterator __position, size_type __n, bool __x)
 547     {
 548       if (__n == 0)
 549         return;
 550       if (capacity() - size() >= __n)
 551         {
 552           std::copy_backward(__position, end(),
 553                              this->_M_impl._M_finish + difference_type(__n));
 554           std::fill(__position, __position + difference_type(__n), __x);
 555           this->_M_impl._M_finish += difference_type(__n);
 556         }
 557       else
 558         {
 559           const size_type __len =
 560             _M_check_len(__n, "vector<bool>::_M_fill_insert");
 561           _Bit_type * __q = this->_M_allocate(__len);
 562           iterator __i = _M_copy_aligned(begin(), __position,
 563                                          iterator(__q, 0));
 564           std::fill(__i, __i + difference_type(__n), __x);
 565           this->_M_impl._M_finish = std::copy(__position, end(),
 566                                               __i + difference_type(__n));
 567           this->_M_deallocate();
 568           this->_M_impl._M_end_of_storage = (__q + ((__len
 569                                                      + int(_S_word_bit) - 1)
 570                                                     / int(_S_word_bit)));
 571           this->_M_impl._M_start = iterator(__q, 0);
 572         }
 573     }
 574
 575   template<typename _Alloc>
 576     template<typename _ForwardIterator>
 577       void
 578       vector<bool, _Alloc>::
 579       _M_insert_range(iterator __position, _ForwardIterator __first,
 580                       _ForwardIterator __last, std::forward_iterator_tag)
 581       {
 582         if (__first != __last)
 583           {
 584             size_type __n = std::distance(__first, __last);
 585             if (capacity() - size() >= __n)
 586               {
 587                 std::copy_backward(__position, end(),
 588                                    this->_M_impl._M_finish
 589                                    + difference_type(__n));
 590                 std::copy(__first, __last, __position);
 591                 this->_M_impl._M_finish += difference_type(__n);
 592               }
 593             else
 594               {
 595                 const size_type __len =
 596                   _M_check_len(__n, "vector<bool>::_M_insert_range");
 597                 _Bit_type * __q = this->_M_allocate(__len);
 598                 iterator __i = _M_copy_aligned(begin(), __position,
 599                                                iterator(__q, 0));
 600                 __i = std::copy(__first, __last, __i);
 601                 this->_M_impl._M_finish = std::copy(__position, end(), __i);
 602                 this->_M_deallocate();
 603                 this->_M_impl._M_end_of_storage = (__q
 604                                                    + ((__len
 605                                                        + int(_S_word_bit) - 1)
 606                                                       / int(_S_word_bit)));
 607                 this->_M_impl._M_start = iterator(__q, 0);
 608               }
 609           }
 610       }
 611
 612   template<typename _Alloc>
 613     void
 614     vector<bool, _Alloc>::
 615     _M_insert_aux(iterator __position, bool __x)
 616     {
 617       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
 618         {
 619           std::copy_backward(__position, this->_M_impl._M_finish,
 620                              this->_M_impl._M_finish + 1);
 621           *__position = __x;
 622           ++this->_M_impl._M_finish;
 623         }
 624       else
 625         {
 626           const size_type __len =
 627             _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
 628           _Bit_type * __q = this->_M_allocate(__len);
 629           iterator __i = _M_copy_aligned(begin(), __position,
 630                                          iterator(__q, 0));
 631           *__i++ = __x;
 632           this->_M_impl._M_finish = std::copy(__position, end(), __i);
 633           this->_M_deallocate();
 634           this->_M_impl._M_end_of_storage = (__q + ((__len
 635                                                      + int(_S_word_bit) - 1)
 636                                                     / int(_S_word_bit)));
 637           this->_M_impl._M_start = iterator(__q, 0);
 638         }
 639     }
 640
 641 _GLIBCXX_END_NESTED_NAMESPACE
 642
 643 #endif /* _VECTOR_TCC */