mingw/lib/gcc/mingw32/4.3.3/include/c++/bits/deque.tcc

   1 // Deque 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) 1997
  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 deque.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 _DEQUE_TCC
  63 #define _DEQUE_TCC 1
  64
  65 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
  66
  67   template <typename _Tp, typename _Alloc>
  68     deque<_Tp, _Alloc>&
  69     deque<_Tp, _Alloc>::
  70     operator=(const deque& __x)
  71     {
  72       const size_type __len = size();
  73       if (&__x != this)
  74         {
  75           if (__len >= __x.size())
  76             _M_erase_at_end(std::copy(__x.begin(), __x.end(),
  77                                       this->_M_impl._M_start));
  78           else
  79             {
  80               const_iterator __mid = __x.begin() + difference_type(__len);
  81               std::copy(__x.begin(), __mid, this->_M_impl._M_start);
  82               insert(this->_M_impl._M_finish, __mid, __x.end());
  83             }
  84         }
  85       return *this;
  86     }
  87
  88   template <typename _Tp, typename _Alloc>
  89     typename deque<_Tp, _Alloc>::iterator
  90     deque<_Tp, _Alloc>::
  91     insert(iterator __position, const value_type& __x)
  92     {
  93       if (__position._M_cur == this->_M_impl._M_start._M_cur)
  94         {
  95           push_front(__x);
  96           return this->_M_impl._M_start;
  97         }
  98       else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
  99         {
 100           push_back(__x);
 101           iterator __tmp = this->_M_impl._M_finish;
 102           --__tmp;
 103           return __tmp;
 104         }
 105       else
 106         return _M_insert_aux(__position, __x);
 107     }
 108
 109 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 110   template<typename _Tp, typename _Alloc>
 111     template<typename... _Args>
 112       typename deque<_Tp, _Alloc>::iterator
 113       deque<_Tp, _Alloc>::
 114       emplace(iterator __position, _Args&&... __args)
 115       {
 116         if (__position._M_cur == this->_M_impl._M_start._M_cur)
 117           {
 118             push_front(std::forward<_Args>(__args)...);
 119             return this->_M_impl._M_start;
 120           }
 121         else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
 122           {
 123             push_back(std::forward<_Args>(__args)...);
 124             iterator __tmp = this->_M_impl._M_finish;
 125             --__tmp;
 126             return __tmp;
 127           }
 128         else
 129           return _M_insert_aux(__position, std::forward<_Args>(__args)...);
 130       }
 131 #endif
 132
 133   template <typename _Tp, typename _Alloc>
 134     typename deque<_Tp, _Alloc>::iterator
 135     deque<_Tp, _Alloc>::
 136     erase(iterator __position)
 137     {
 138       iterator __next = __position;
 139       ++__next;
 140       const difference_type __index = __position - begin();
 141       if (static_cast<size_type>(__index) < (size() >> 1))
 142         {
 143           if (__position != begin())
 144             _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
 145           pop_front();
 146         }
 147       else
 148         {
 149           if (__next != end())
 150             _GLIBCXX_MOVE3(__next, end(), __position);
 151           pop_back();
 152         }
 153       return begin() + __index;
 154     }
 155
 156   template <typename _Tp, typename _Alloc>
 157     typename deque<_Tp, _Alloc>::iterator
 158     deque<_Tp, _Alloc>::
 159     erase(iterator __first, iterator __last)
 160     {
 161       if (__first == begin() && __last == end())
 162         {
 163           clear();
 164           return end();
 165         }
 166       else
 167         {
 168           const difference_type __n = __last - __first;
 169           const difference_type __elems_before = __first - begin();
 170           if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
 171             {
 172               if (__first != begin())
 173                 _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
 174               _M_erase_at_begin(begin() + __n);
 175             }
 176           else
 177             {
 178               if (__last != end())
 179                 _GLIBCXX_MOVE3(__last, end(), __first);
 180               _M_erase_at_end(end() - __n);
 181             }
 182           return begin() + __elems_before;
 183         }
 184     }
 185
 186   template <typename _Tp, class _Alloc>
 187     template <typename _InputIterator>
 188       void
 189       deque<_Tp, _Alloc>::
 190       _M_assign_aux(_InputIterator __first, _InputIterator __last,
 191                     std::input_iterator_tag)
 192       {
 193         iterator __cur = begin();
 194         for (; __first != __last && __cur != end(); ++__cur, ++__first)
 195           *__cur = *__first;
 196         if (__first == __last)
 197           _M_erase_at_end(__cur);
 198         else
 199           insert(end(), __first, __last);
 200       }
 201
 202   template <typename _Tp, typename _Alloc>
 203     void
 204     deque<_Tp, _Alloc>::
 205     _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
 206     {
 207       if (__pos._M_cur == this->_M_impl._M_start._M_cur)
 208         {
 209           iterator __new_start = _M_reserve_elements_at_front(__n);
 210           try
 211             {
 212               std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
 213                                           __x, _M_get_Tp_allocator());
 214               this->_M_impl._M_start = __new_start;
 215             }
 216           catch(...)
 217             {
 218               _M_destroy_nodes(__new_start._M_node,
 219                                this->_M_impl._M_start._M_node);
 220               __throw_exception_again;
 221             }
 222         }
 223       else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
 224         {
 225           iterator __new_finish = _M_reserve_elements_at_back(__n);
 226           try
 227             {
 228               std::__uninitialized_fill_a(this->_M_impl._M_finish,
 229                                           __new_finish, __x,
 230                                           _M_get_Tp_allocator());
 231               this->_M_impl._M_finish = __new_finish;
 232             }
 233           catch(...)
 234             {
 235               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 236                                __new_finish._M_node + 1);
 237               __throw_exception_again;
 238             }
 239         }
 240       else
 241         _M_insert_aux(__pos, __n, __x);
 242     }
 243
 244   template <typename _Tp, typename _Alloc>
 245     void
 246     deque<_Tp, _Alloc>::
 247     _M_fill_initialize(const value_type& __value)
 248     {
 249       _Map_pointer __cur;
 250       try
 251         {
 252           for (__cur = this->_M_impl._M_start._M_node;
 253                __cur < this->_M_impl._M_finish._M_node;
 254                ++__cur)
 255             std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
 256                                         __value, _M_get_Tp_allocator());
 257           std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
 258                                       this->_M_impl._M_finish._M_cur,
 259                                       __value, _M_get_Tp_allocator());
 260         }
 261       catch(...)
 262         {
 263           std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
 264                         _M_get_Tp_allocator());
 265           __throw_exception_again;
 266         }
 267     }
 268
 269   template <typename _Tp, typename _Alloc>
 270     template <typename _InputIterator>
 271       void
 272       deque<_Tp, _Alloc>::
 273       _M_range_initialize(_InputIterator __first, _InputIterator __last,
 274                           std::input_iterator_tag)
 275       {
 276         this->_M_initialize_map(0);
 277         try
 278           {
 279             for (; __first != __last; ++__first)
 280               push_back(*__first);
 281           }
 282         catch(...)
 283           {
 284             clear();
 285             __throw_exception_again;
 286           }
 287       }
 288
 289   template <typename _Tp, typename _Alloc>
 290     template <typename _ForwardIterator>
 291       void
 292       deque<_Tp, _Alloc>::
 293       _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
 294                           std::forward_iterator_tag)
 295       {
 296         const size_type __n = std::distance(__first, __last);
 297         this->_M_initialize_map(__n);
 298
 299         _Map_pointer __cur_node;
 300         try
 301           {
 302             for (__cur_node = this->_M_impl._M_start._M_node;
 303                  __cur_node < this->_M_impl._M_finish._M_node;
 304                  ++__cur_node)
 305               {
 306                 _ForwardIterator __mid = __first;
 307                 std::advance(__mid, _S_buffer_size());
 308                 std::__uninitialized_copy_a(__first, __mid, *__cur_node,
 309                                             _M_get_Tp_allocator());
 310                 __first = __mid;
 311               }
 312             std::__uninitialized_copy_a(__first, __last,
 313                                         this->_M_impl._M_finish._M_first,
 314                                         _M_get_Tp_allocator());
 315           }
 316         catch(...)
 317           {
 318             std::_Destroy(this->_M_impl._M_start,
 319                           iterator(*__cur_node, __cur_node),
 320                           _M_get_Tp_allocator());
 321             __throw_exception_again;
 322           }
 323       }
 324
 325   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
 326   template<typename _Tp, typename _Alloc>
 327 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 328     template<typename... _Args>
 329       void
 330       deque<_Tp, _Alloc>::
 331       _M_push_back_aux(_Args&&... __args)
 332 #else
 333       void
 334       deque<_Tp, _Alloc>::
 335       _M_push_back_aux(const value_type& __t)
 336 #endif
 337       {
 338         _M_reserve_map_at_back();
 339         *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
 340         try
 341           {
 342 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 343             this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
 344                                     std::forward<_Args>(__args)...);
 345 #else
 346             this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
 347 #endif
 348             this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
 349                                                 + 1);
 350             this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
 351           }
 352         catch(...)
 353           {
 354             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
 355             __throw_exception_again;
 356           }
 357       }
 358
 359   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
 360   template<typename _Tp, typename _Alloc>
 361 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 362     template<typename... _Args>
 363       void
 364       deque<_Tp, _Alloc>::
 365       _M_push_front_aux(_Args&&... __args)
 366 #else
 367       void
 368       deque<_Tp, _Alloc>::
 369       _M_push_front_aux(const value_type& __t)
 370 #endif
 371       {
 372         _M_reserve_map_at_front();
 373         *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
 374         try
 375           {
 376             this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
 377                                                - 1);
 378             this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
 379 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 380             this->_M_impl.construct(this->_M_impl._M_start._M_cur,
 381                                     std::forward<_Args>(__args)...);
 382 #else
 383             this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
 384 #endif
 385           }
 386         catch(...)
 387           {
 388             ++this->_M_impl._M_start;
 389             _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
 390             __throw_exception_again;
 391           }
 392       }
 393
 394   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
 395   template <typename _Tp, typename _Alloc>
 396     void deque<_Tp, _Alloc>::
 397     _M_pop_back_aux()
 398     {
 399       _M_deallocate_node(this->_M_impl._M_finish._M_first);
 400       this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
 401       this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
 402       this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
 403     }
 404
 405   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
 406   // Note that if the deque has at least one element (a precondition for this
 407   // member function), and if
 408   //   _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
 409   // then the deque must have at least two nodes.
 410   template <typename _Tp, typename _Alloc>
 411     void deque<_Tp, _Alloc>::
 412     _M_pop_front_aux()
 413     {
 414       this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
 415       _M_deallocate_node(this->_M_impl._M_start._M_first);
 416       this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
 417       this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
 418     }
 419
 420   template <typename _Tp, typename _Alloc>
 421     template <typename _InputIterator>
 422       void
 423       deque<_Tp, _Alloc>::
 424       _M_range_insert_aux(iterator __pos,
 425                           _InputIterator __first, _InputIterator __last,
 426                           std::input_iterator_tag)
 427       { std::copy(__first, __last, std::inserter(*this, __pos)); }
 428
 429   template <typename _Tp, typename _Alloc>
 430     template <typename _ForwardIterator>
 431       void
 432       deque<_Tp, _Alloc>::
 433       _M_range_insert_aux(iterator __pos,
 434                           _ForwardIterator __first, _ForwardIterator __last,
 435                           std::forward_iterator_tag)
 436       {
 437         const size_type __n = std::distance(__first, __last);
 438         if (__pos._M_cur == this->_M_impl._M_start._M_cur)
 439           {
 440             iterator __new_start = _M_reserve_elements_at_front(__n);
 441             try
 442               {
 443                 std::__uninitialized_copy_a(__first, __last, __new_start,
 444                                             _M_get_Tp_allocator());
 445                 this->_M_impl._M_start = __new_start;
 446               }
 447             catch(...)
 448               {
 449                 _M_destroy_nodes(__new_start._M_node,
 450                                  this->_M_impl._M_start._M_node);
 451                 __throw_exception_again;
 452               }
 453           }
 454         else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
 455           {
 456             iterator __new_finish = _M_reserve_elements_at_back(__n);
 457             try
 458               {
 459                 std::__uninitialized_copy_a(__first, __last,
 460                                             this->_M_impl._M_finish,
 461                                             _M_get_Tp_allocator());
 462                 this->_M_impl._M_finish = __new_finish;
 463               }
 464             catch(...)
 465               {
 466                 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 467                                  __new_finish._M_node + 1);
 468                 __throw_exception_again;
 469               }
 470           }
 471         else
 472           _M_insert_aux(__pos, __first, __last, __n);
 473       }
 474
 475   template<typename _Tp, typename _Alloc>
 476 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 477     template<typename... _Args>
 478       typename deque<_Tp, _Alloc>::iterator
 479       deque<_Tp, _Alloc>::
 480       _M_insert_aux(iterator __pos, _Args&&... __args)
 481       {
 482         value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
 483 #else
 484     typename deque<_Tp, _Alloc>::iterator
 485       deque<_Tp, _Alloc>::
 486       _M_insert_aux(iterator __pos, const value_type& __x)
 487       {
 488         value_type __x_copy = __x; // XXX copy
 489 #endif
 490         difference_type __index = __pos - this->_M_impl._M_start;
 491         if (static_cast<size_type>(__index) < size() / 2)
 492           {
 493             push_front(_GLIBCXX_MOVE(front()));
 494             iterator __front1 = this->_M_impl._M_start;
 495             ++__front1;
 496             iterator __front2 = __front1;
 497             ++__front2;
 498             __pos = this->_M_impl._M_start + __index;
 499             iterator __pos1 = __pos;
 500             ++__pos1;
 501             _GLIBCXX_MOVE3(__front2, __pos1, __front1);
 502           }
 503         else
 504           {
 505             push_back(_GLIBCXX_MOVE(back()));
 506             iterator __back1 = this->_M_impl._M_finish;
 507             --__back1;
 508             iterator __back2 = __back1;
 509             --__back2;
 510             __pos = this->_M_impl._M_start + __index;
 511             _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
 512           }
 513         *__pos = _GLIBCXX_MOVE(__x_copy);
 514         return __pos;
 515       }
 516
 517   template <typename _Tp, typename _Alloc>
 518     void
 519     deque<_Tp, _Alloc>::
 520     _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
 521     {
 522       const difference_type __elems_before = __pos - this->_M_impl._M_start;
 523       const size_type __length = this->size();
 524       value_type __x_copy = __x;
 525       if (__elems_before < difference_type(__length / 2))
 526         {
 527           iterator __new_start = _M_reserve_elements_at_front(__n);
 528           iterator __old_start = this->_M_impl._M_start;
 529           __pos = this->_M_impl._M_start + __elems_before;
 530           try
 531             {
 532               if (__elems_before >= difference_type(__n))
 533                 {
 534                   iterator __start_n = (this->_M_impl._M_start
 535                                         + difference_type(__n));
 536                   std::__uninitialized_move_a(this->_M_impl._M_start,
 537                                               __start_n, __new_start,
 538                                               _M_get_Tp_allocator());
 539                   this->_M_impl._M_start = __new_start;
 540                   _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
 541                   std::fill(__pos - difference_type(__n), __pos, __x_copy);
 542                 }
 543               else
 544                 {
 545                   std::__uninitialized_move_fill(this->_M_impl._M_start,
 546                                                  __pos, __new_start,
 547                                                  this->_M_impl._M_start,
 548                                                  __x_copy,
 549                                                  _M_get_Tp_allocator());
 550                   this->_M_impl._M_start = __new_start;
 551                   std::fill(__old_start, __pos, __x_copy);
 552                 }
 553             }
 554           catch(...)
 555             {
 556               _M_destroy_nodes(__new_start._M_node,
 557                                this->_M_impl._M_start._M_node);
 558               __throw_exception_again;
 559             }
 560         }
 561       else
 562         {
 563           iterator __new_finish = _M_reserve_elements_at_back(__n);
 564           iterator __old_finish = this->_M_impl._M_finish;
 565           const difference_type __elems_after =
 566             difference_type(__length) - __elems_before;
 567           __pos = this->_M_impl._M_finish - __elems_after;
 568           try
 569             {
 570               if (__elems_after > difference_type(__n))
 571                 {
 572                   iterator __finish_n = (this->_M_impl._M_finish
 573                                          - difference_type(__n));
 574                   std::__uninitialized_move_a(__finish_n,
 575                                               this->_M_impl._M_finish,
 576                                               this->_M_impl._M_finish,
 577                                               _M_get_Tp_allocator());
 578                   this->_M_impl._M_finish = __new_finish;
 579                   _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
 580                   std::fill(__pos, __pos + difference_type(__n), __x_copy);
 581                 }
 582               else
 583                 {
 584                   std::__uninitialized_fill_move(this->_M_impl._M_finish,
 585                                                  __pos + difference_type(__n),
 586                                                  __x_copy, __pos,
 587                                                  this->_M_impl._M_finish,
 588                                                  _M_get_Tp_allocator());
 589                   this->_M_impl._M_finish = __new_finish;
 590                   std::fill(__pos, __old_finish, __x_copy);
 591                 }
 592             }
 593           catch(...)
 594             {
 595               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 596                                __new_finish._M_node + 1);
 597               __throw_exception_again;
 598             }
 599         }
 600     }
 601
 602   template <typename _Tp, typename _Alloc>
 603     template <typename _ForwardIterator>
 604       void
 605       deque<_Tp, _Alloc>::
 606       _M_insert_aux(iterator __pos,
 607                     _ForwardIterator __first, _ForwardIterator __last,
 608                     size_type __n)
 609       {
 610         const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
 611         const size_type __length = size();
 612         if (static_cast<size_type>(__elemsbefore) < __length / 2)
 613           {
 614             iterator __new_start = _M_reserve_elements_at_front(__n);
 615             iterator __old_start = this->_M_impl._M_start;
 616             __pos = this->_M_impl._M_start + __elemsbefore;
 617             try
 618               {
 619                 if (__elemsbefore >= difference_type(__n))
 620                   {
 621                     iterator __start_n = (this->_M_impl._M_start
 622                                           + difference_type(__n));
 623                     std::__uninitialized_move_a(this->_M_impl._M_start,
 624                                                 __start_n, __new_start,
 625                                                 _M_get_Tp_allocator());
 626                     this->_M_impl._M_start = __new_start;
 627                     _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
 628                     std::copy(__first, __last, __pos - difference_type(__n));
 629                   }
 630                 else
 631                   {
 632                     _ForwardIterator __mid = __first;
 633                     std::advance(__mid, difference_type(__n) - __elemsbefore);
 634                     std::__uninitialized_move_copy(this->_M_impl._M_start,
 635                                                    __pos, __first, __mid,
 636                                                    __new_start,
 637                                                    _M_get_Tp_allocator());
 638                     this->_M_impl._M_start = __new_start;
 639                     std::copy(__mid, __last, __old_start);
 640                   }
 641               }
 642             catch(...)
 643               {
 644                 _M_destroy_nodes(__new_start._M_node,
 645                                  this->_M_impl._M_start._M_node);
 646                 __throw_exception_again;
 647               }
 648           }
 649         else
 650         {
 651           iterator __new_finish = _M_reserve_elements_at_back(__n);
 652           iterator __old_finish = this->_M_impl._M_finish;
 653           const difference_type __elemsafter =
 654             difference_type(__length) - __elemsbefore;
 655           __pos = this->_M_impl._M_finish - __elemsafter;
 656           try
 657             {
 658               if (__elemsafter > difference_type(__n))
 659                 {
 660                   iterator __finish_n = (this->_M_impl._M_finish
 661                                          - difference_type(__n));
 662                   std::__uninitialized_move_a(__finish_n,
 663                                               this->_M_impl._M_finish,
 664                                               this->_M_impl._M_finish,
 665                                               _M_get_Tp_allocator());
 666                   this->_M_impl._M_finish = __new_finish;
 667                   _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
 668                   std::copy(__first, __last, __pos);
 669                 }
 670               else
 671                 {
 672                   _ForwardIterator __mid = __first;
 673                   std::advance(__mid, __elemsafter);
 674                   std::__uninitialized_copy_move(__mid, __last, __pos,
 675                                                  this->_M_impl._M_finish,
 676                                                  this->_M_impl._M_finish,
 677                                                  _M_get_Tp_allocator());
 678                   this->_M_impl._M_finish = __new_finish;
 679                   std::copy(__first, __mid, __pos);
 680                 }
 681             }
 682           catch(...)
 683             {
 684               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 685                                __new_finish._M_node + 1);
 686               __throw_exception_again;
 687             }
 688         }
 689       }
 690
 691    template<typename _Tp, typename _Alloc>
 692      void
 693      deque<_Tp, _Alloc>::
 694      _M_destroy_data_aux(iterator __first, iterator __last)
 695      {
 696        for (_Map_pointer __node = __first._M_node + 1;
 697             __node < __last._M_node; ++__node)
 698          std::_Destroy(*__node, *__node + _S_buffer_size(),
 699                        _M_get_Tp_allocator());
 700
 701        if (__first._M_node != __last._M_node)
 702          {
 703            std::_Destroy(__first._M_cur, __first._M_last,
 704                          _M_get_Tp_allocator());
 705            std::_Destroy(__last._M_first, __last._M_cur,
 706                          _M_get_Tp_allocator());
 707          }
 708        else
 709          std::_Destroy(__first._M_cur, __last._M_cur,
 710                        _M_get_Tp_allocator());
 711      }
 712
 713   template <typename _Tp, typename _Alloc>
 714     void
 715     deque<_Tp, _Alloc>::
 716     _M_new_elements_at_front(size_type __new_elems)
 717     {
 718       if (this->max_size() - this->size() < __new_elems)
 719         __throw_length_error(__N("deque::_M_new_elements_at_front"));
 720
 721       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
 722                                      / _S_buffer_size());
 723       _M_reserve_map_at_front(__new_nodes);
 724       size_type __i;
 725       try
 726         {
 727           for (__i = 1; __i <= __new_nodes; ++__i)
 728             *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
 729         }
 730       catch(...)
 731         {
 732           for (size_type __j = 1; __j < __i; ++__j)
 733             _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
 734           __throw_exception_again;
 735         }
 736     }
 737
 738   template <typename _Tp, typename _Alloc>
 739     void
 740     deque<_Tp, _Alloc>::
 741     _M_new_elements_at_back(size_type __new_elems)
 742     {
 743       if (this->max_size() - this->size() < __new_elems)
 744         __throw_length_error(__N("deque::_M_new_elements_at_back"));
 745
 746       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
 747                                      / _S_buffer_size());
 748       _M_reserve_map_at_back(__new_nodes);
 749       size_type __i;
 750       try
 751         {
 752           for (__i = 1; __i <= __new_nodes; ++__i)
 753             *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
 754         }
 755       catch(...)
 756         {
 757           for (size_type __j = 1; __j < __i; ++__j)
 758             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
 759           __throw_exception_again;
 760         }
 761     }
 762
 763   template <typename _Tp, typename _Alloc>
 764     void
 765     deque<_Tp, _Alloc>::
 766     _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
 767     {
 768       const size_type __old_num_nodes
 769         = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
 770       const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
 771
 772       _Map_pointer __new_nstart;
 773       if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
 774         {
 775           __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
 776                                          - __new_num_nodes) / 2
 777                          + (__add_at_front ? __nodes_to_add : 0);
 778           if (__new_nstart < this->_M_impl._M_start._M_node)
 779             std::copy(this->_M_impl._M_start._M_node,
 780                       this->_M_impl._M_finish._M_node + 1,
 781                       __new_nstart);
 782           else
 783             std::copy_backward(this->_M_impl._M_start._M_node,
 784                                this->_M_impl._M_finish._M_node + 1,
 785                                __new_nstart + __old_num_nodes);
 786         }
 787       else
 788         {
 789           size_type __new_map_size = this->_M_impl._M_map_size
 790                                      + std::max(this->_M_impl._M_map_size,
 791                                                 __nodes_to_add) + 2;
 792
 793           _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
 794           __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
 795                          + (__add_at_front ? __nodes_to_add : 0);
 796           std::copy(this->_M_impl._M_start._M_node,
 797                     this->_M_impl._M_finish._M_node + 1,
 798                     __new_nstart);
 799           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
 800
 801           this->_M_impl._M_map = __new_map;
 802           this->_M_impl._M_map_size = __new_map_size;
 803         }
 804
 805       this->_M_impl._M_start._M_set_node(__new_nstart);
 806       this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
 807     }
 808
 809   // Overload for deque::iterators, exploiting the "segmented-iterator
 810   // optimization".  NB: leave const_iterators alone!
 811   template<typename _Tp>
 812     void
 813     fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
 814          const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
 815     {
 816       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
 817
 818       for (typename _Self::_Map_pointer __node = __first._M_node + 1;
 819            __node < __last._M_node; ++__node)
 820         std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
 821
 822       if (__first._M_node != __last._M_node)
 823         {
 824           std::fill(__first._M_cur, __first._M_last, __value);
 825           std::fill(__last._M_first, __last._M_cur, __value);
 826         }
 827       else
 828         std::fill(__first._M_cur, __last._M_cur, __value);
 829     }
 830
 831 _GLIBCXX_END_NESTED_NAMESPACE
 832
 833 #endif