contrib/gcc-4.4/libstdc++-v3/include/bits/deque.tcc

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