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,
   4 // 2009, 2010
   5 // Free Software Foundation, Inc.
   6 //
   7 // This file is part of the GNU ISO C++ Library.  This library is free
   8 // software; you can redistribute it and/or modify it under the
   9 // terms of the GNU General Public License as published by the
  10 // Free Software Foundation; either version 3, or (at your option)
  11 // any later version.
  12
  13 // This library is distributed in the hope that it will be useful,
  14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 // GNU General Public License for more details.
  17
  18 // Under Section 7 of GPL version 3, you are granted additional
  19 // permissions described in the GCC Runtime Library Exception, version
  20 // 3.1, as published by the Free Software Foundation.
  21
  22 // You should have received a copy of the GNU General Public License and
  23 // a copy of the GCC Runtime Library Exception along with this program;
  24 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  25 // <http://www.gnu.org/licenses/>.
  26
  27 /*
  28  *
  29  * Copyright (c) 1994
  30  * Hewlett-Packard Company
  31  *
  32  * Permission to use, copy, modify, distribute and sell this software
  33  * and its documentation for any purpose is hereby granted without fee,
  34  * provided that the above copyright notice appear in all copies and
  35  * that both that copyright notice and this permission notice appear
  36  * in supporting documentation.  Hewlett-Packard Company makes no
  37  * representations about the suitability of this software for any
  38  * purpose.  It is provided "as is" without express or implied warranty.
  39  *
  40  *
  41  * Copyright (c) 1997
  42  * Silicon Graphics Computer Systems, Inc.
  43  *
  44  * Permission to use, copy, modify, distribute and sell this software
  45  * and its documentation for any purpose is hereby granted without fee,
  46  * provided that the above copyright notice appear in all copies and
  47  * that both that copyright notice and this permission notice appear
  48  * in supporting documentation.  Silicon Graphics makes no
  49  * representations about the suitability of this software for any
  50  * purpose.  It is provided "as is" without express or implied warranty.
  51  */
  52
  53 /** @file deque.tcc
  54  *  This is an internal header file, included by other library headers.
  55  *  You should not attempt to use it directly.
  56  */
  57
  58 #ifndef _DEQUE_TCC
  59 #define _DEQUE_TCC 1
  60
  61 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
  62
  63 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  64   template <typename _Tp, typename _Alloc>
  65     void
  66     deque<_Tp, _Alloc>::
  67     _M_default_initialize()
  68     {
  69       _Map_pointer __cur;
  70       __try
  71         {
  72           for (__cur = this->_M_impl._M_start._M_node;
  73                __cur < this->_M_impl._M_finish._M_node;
  74                ++__cur)
  75             std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(),
  76                                            _M_get_Tp_allocator());
  77           std::__uninitialized_default_a(this->_M_impl._M_finish._M_first,
  78                                          this->_M_impl._M_finish._M_cur,
  79                                          _M_get_Tp_allocator());
  80         }
  81       __catch(...)
  82         {
  83           std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
  84                         _M_get_Tp_allocator());
  85           __throw_exception_again;
  86         }
  87     }
  88 #endif
  89
  90   template <typename _Tp, typename _Alloc>
  91     deque<_Tp, _Alloc>&
  92     deque<_Tp, _Alloc>::
  93     operator=(const deque& __x)
  94     {
  95       const size_type __len = size();
  96       if (&__x != this)
  97         {
  98           if (__len >= __x.size())
  99             _M_erase_at_end(std::copy(__x.begin(), __x.end(),
 100                                       this->_M_impl._M_start));
 101           else
 102             {
 103               const_iterator __mid = __x.begin() + difference_type(__len);
 104               std::copy(__x.begin(), __mid, this->_M_impl._M_start);
 105               insert(this->_M_impl._M_finish, __mid, __x.end());
 106             }
 107         }
 108       return *this;
 109     }
 110
 111 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 112   template<typename _Tp, typename _Alloc>
 113     template<typename... _Args>
 114       void
 115       deque<_Tp, _Alloc>::
 116       emplace_front(_Args&&... __args)
 117       {
 118         if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
 119           {
 120             this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1,
 121                                     std::forward<_Args>(__args)...);
 122             --this->_M_impl._M_start._M_cur;
 123           }
 124         else
 125           _M_push_front_aux(std::forward<_Args>(__args)...);
 126       }
 127
 128   template<typename _Tp, typename _Alloc>
 129     template<typename... _Args>
 130       void
 131       deque<_Tp, _Alloc>::
 132       emplace_back(_Args&&... __args)
 133       {
 134         if (this->_M_impl._M_finish._M_cur
 135             != this->_M_impl._M_finish._M_last - 1)
 136           {
 137             this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
 138                                     std::forward<_Args>(__args)...);
 139             ++this->_M_impl._M_finish._M_cur;
 140           }
 141         else
 142           _M_push_back_aux(std::forward<_Args>(__args)...);
 143       }
 144 #endif
 145
 146   template <typename _Tp, typename _Alloc>
 147     typename deque<_Tp, _Alloc>::iterator
 148     deque<_Tp, _Alloc>::
 149     insert(iterator __position, const value_type& __x)
 150     {
 151       if (__position._M_cur == this->_M_impl._M_start._M_cur)
 152         {
 153           push_front(__x);
 154           return this->_M_impl._M_start;
 155         }
 156       else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
 157         {
 158           push_back(__x);
 159           iterator __tmp = this->_M_impl._M_finish;
 160           --__tmp;
 161           return __tmp;
 162         }
 163       else
 164         return _M_insert_aux(__position, __x);
 165     }
 166
 167 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 168   template<typename _Tp, typename _Alloc>
 169     template<typename... _Args>
 170       typename deque<_Tp, _Alloc>::iterator
 171       deque<_Tp, _Alloc>::
 172       emplace(iterator __position, _Args&&... __args)
 173       {
 174         if (__position._M_cur == this->_M_impl._M_start._M_cur)
 175           {
 176             push_front(std::forward<_Args>(__args)...);
 177             return this->_M_impl._M_start;
 178           }
 179         else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
 180           {
 181             push_back(std::forward<_Args>(__args)...);
 182             iterator __tmp = this->_M_impl._M_finish;
 183             --__tmp;
 184             return __tmp;
 185           }
 186         else
 187           return _M_insert_aux(__position, std::forward<_Args>(__args)...);
 188       }
 189 #endif
 190
 191   template <typename _Tp, typename _Alloc>
 192     typename deque<_Tp, _Alloc>::iterator
 193     deque<_Tp, _Alloc>::
 194     erase(iterator __position)
 195     {
 196       iterator __next = __position;
 197       ++__next;
 198       const difference_type __index = __position - begin();
 199       if (static_cast<size_type>(__index) < (size() >> 1))
 200         {
 201           if (__position != begin())
 202             _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
 203           pop_front();
 204         }
 205       else
 206         {
 207           if (__next != end())
 208             _GLIBCXX_MOVE3(__next, end(), __position);
 209           pop_back();
 210         }
 211       return begin() + __index;
 212     }
 213
 214   template <typename _Tp, typename _Alloc>
 215     typename deque<_Tp, _Alloc>::iterator
 216     deque<_Tp, _Alloc>::
 217     erase(iterator __first, iterator __last)
 218     {
 219       if (__first == begin() && __last == end())
 220         {
 221           clear();
 222           return end();
 223         }
 224       else
 225         {
 226           const difference_type __n = __last - __first;
 227           const difference_type __elems_before = __first - begin();
 228           if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
 229             {
 230               if (__first != begin())
 231                 _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
 232               _M_erase_at_begin(begin() + __n);
 233             }
 234           else
 235             {
 236               if (__last != end())
 237                 _GLIBCXX_MOVE3(__last, end(), __first);
 238               _M_erase_at_end(end() - __n);
 239             }
 240           return begin() + __elems_before;
 241         }
 242     }
 243
 244   template <typename _Tp, class _Alloc>
 245     template <typename _InputIterator>
 246       void
 247       deque<_Tp, _Alloc>::
 248       _M_assign_aux(_InputIterator __first, _InputIterator __last,
 249                     std::input_iterator_tag)
 250       {
 251         iterator __cur = begin();
 252         for (; __first != __last && __cur != end(); ++__cur, ++__first)
 253           *__cur = *__first;
 254         if (__first == __last)
 255           _M_erase_at_end(__cur);
 256         else
 257           insert(end(), __first, __last);
 258       }
 259
 260   template <typename _Tp, typename _Alloc>
 261     void
 262     deque<_Tp, _Alloc>::
 263     _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
 264     {
 265       if (__pos._M_cur == this->_M_impl._M_start._M_cur)
 266         {
 267           iterator __new_start = _M_reserve_elements_at_front(__n);
 268           __try
 269             {
 270               std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
 271                                           __x, _M_get_Tp_allocator());
 272               this->_M_impl._M_start = __new_start;
 273             }
 274           __catch(...)
 275             {
 276               _M_destroy_nodes(__new_start._M_node,
 277                                this->_M_impl._M_start._M_node);
 278               __throw_exception_again;
 279             }
 280         }
 281       else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
 282         {
 283           iterator __new_finish = _M_reserve_elements_at_back(__n);
 284           __try
 285             {
 286               std::__uninitialized_fill_a(this->_M_impl._M_finish,
 287                                           __new_finish, __x,
 288                                           _M_get_Tp_allocator());
 289               this->_M_impl._M_finish = __new_finish;
 290             }
 291           __catch(...)
 292             {
 293               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 294                                __new_finish._M_node + 1);
 295               __throw_exception_again;
 296             }
 297         }
 298       else
 299         _M_insert_aux(__pos, __n, __x);
 300     }
 301
 302 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 303   template <typename _Tp, typename _Alloc>
 304     void
 305     deque<_Tp, _Alloc>::
 306     _M_default_append(size_type __n)
 307     {
 308       if (__n)
 309         {
 310           iterator __new_finish = _M_reserve_elements_at_back(__n);
 311           __try
 312             {
 313               std::__uninitialized_default_a(this->_M_impl._M_finish,
 314                                              __new_finish,
 315                                              _M_get_Tp_allocator());
 316               this->_M_impl._M_finish = __new_finish;
 317             }
 318           __catch(...)
 319             {
 320               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 321                                __new_finish._M_node + 1);
 322               __throw_exception_again;
 323             }
 324         }
 325     }
 326 #endif
 327
 328   template <typename _Tp, typename _Alloc>
 329     void
 330     deque<_Tp, _Alloc>::
 331     _M_fill_initialize(const value_type& __value)
 332     {
 333       _Map_pointer __cur;
 334       __try
 335         {
 336           for (__cur = this->_M_impl._M_start._M_node;
 337                __cur < this->_M_impl._M_finish._M_node;
 338                ++__cur)
 339             std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
 340                                         __value, _M_get_Tp_allocator());
 341           std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
 342                                       this->_M_impl._M_finish._M_cur,
 343                                       __value, _M_get_Tp_allocator());
 344         }
 345       __catch(...)
 346         {
 347           std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
 348                         _M_get_Tp_allocator());
 349           __throw_exception_again;
 350         }
 351     }
 352
 353   template <typename _Tp, typename _Alloc>
 354     template <typename _InputIterator>
 355       void
 356       deque<_Tp, _Alloc>::
 357       _M_range_initialize(_InputIterator __first, _InputIterator __last,
 358                           std::input_iterator_tag)
 359       {
 360         this->_M_initialize_map(0);
 361         __try
 362           {
 363             for (; __first != __last; ++__first)
 364               push_back(*__first);
 365           }
 366         __catch(...)
 367           {
 368             clear();
 369             __throw_exception_again;
 370           }
 371       }
 372
 373   template <typename _Tp, typename _Alloc>
 374     template <typename _ForwardIterator>
 375       void
 376       deque<_Tp, _Alloc>::
 377       _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
 378                           std::forward_iterator_tag)
 379       {
 380         const size_type __n = std::distance(__first, __last);
 381         this->_M_initialize_map(__n);
 382
 383         _Map_pointer __cur_node;
 384         __try
 385           {
 386             for (__cur_node = this->_M_impl._M_start._M_node;
 387                  __cur_node < this->_M_impl._M_finish._M_node;
 388                  ++__cur_node)
 389               {
 390                 _ForwardIterator __mid = __first;
 391                 std::advance(__mid, _S_buffer_size());
 392                 std::__uninitialized_copy_a(__first, __mid, *__cur_node,
 393                                             _M_get_Tp_allocator());
 394                 __first = __mid;
 395               }
 396             std::__uninitialized_copy_a(__first, __last,
 397                                         this->_M_impl._M_finish._M_first,
 398                                         _M_get_Tp_allocator());
 399           }
 400         __catch(...)
 401           {
 402             std::_Destroy(this->_M_impl._M_start,
 403                           iterator(*__cur_node, __cur_node),
 404                           _M_get_Tp_allocator());
 405             __throw_exception_again;
 406           }
 407       }
 408
 409   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
 410   template<typename _Tp, typename _Alloc>
 411 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 412     template<typename... _Args>
 413       void
 414       deque<_Tp, _Alloc>::
 415       _M_push_back_aux(_Args&&... __args)
 416 #else
 417       void
 418       deque<_Tp, _Alloc>::
 419       _M_push_back_aux(const value_type& __t)
 420 #endif
 421       {
 422         _M_reserve_map_at_back();
 423         *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
 424         __try
 425           {
 426 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 427             this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
 428                                     std::forward<_Args>(__args)...);
 429 #else
 430             this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
 431 #endif
 432             this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
 433                                                 + 1);
 434             this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
 435           }
 436         __catch(...)
 437           {
 438             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
 439             __throw_exception_again;
 440           }
 441       }
 442
 443   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
 444   template<typename _Tp, typename _Alloc>
 445 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 446     template<typename... _Args>
 447       void
 448       deque<_Tp, _Alloc>::
 449       _M_push_front_aux(_Args&&... __args)
 450 #else
 451       void
 452       deque<_Tp, _Alloc>::
 453       _M_push_front_aux(const value_type& __t)
 454 #endif
 455       {
 456         _M_reserve_map_at_front();
 457         *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
 458         __try
 459           {
 460             this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
 461                                                - 1);
 462             this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
 463 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 464             this->_M_impl.construct(this->_M_impl._M_start._M_cur,
 465                                     std::forward<_Args>(__args)...);
 466 #else
 467             this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
 468 #endif
 469           }
 470         __catch(...)
 471           {
 472             ++this->_M_impl._M_start;
 473             _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
 474             __throw_exception_again;
 475           }
 476       }
 477
 478   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
 479   template <typename _Tp, typename _Alloc>
 480     void deque<_Tp, _Alloc>::
 481     _M_pop_back_aux()
 482     {
 483       _M_deallocate_node(this->_M_impl._M_finish._M_first);
 484       this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
 485       this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
 486       this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
 487     }
 488
 489   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
 490   // Note that if the deque has at least one element (a precondition for this
 491   // member function), and if
 492   //   _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
 493   // then the deque must have at least two nodes.
 494   template <typename _Tp, typename _Alloc>
 495     void deque<_Tp, _Alloc>::
 496     _M_pop_front_aux()
 497     {
 498       this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
 499       _M_deallocate_node(this->_M_impl._M_start._M_first);
 500       this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
 501       this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
 502     }
 503
 504   template <typename _Tp, typename _Alloc>
 505     template <typename _InputIterator>
 506       void
 507       deque<_Tp, _Alloc>::
 508       _M_range_insert_aux(iterator __pos,
 509                           _InputIterator __first, _InputIterator __last,
 510                           std::input_iterator_tag)
 511       { std::copy(__first, __last, std::inserter(*this, __pos)); }
 512
 513   template <typename _Tp, typename _Alloc>
 514     template <typename _ForwardIterator>
 515       void
 516       deque<_Tp, _Alloc>::
 517       _M_range_insert_aux(iterator __pos,
 518                           _ForwardIterator __first, _ForwardIterator __last,
 519                           std::forward_iterator_tag)
 520       {
 521         const size_type __n = std::distance(__first, __last);
 522         if (__pos._M_cur == this->_M_impl._M_start._M_cur)
 523           {
 524             iterator __new_start = _M_reserve_elements_at_front(__n);
 525             __try
 526               {
 527                 std::__uninitialized_copy_a(__first, __last, __new_start,
 528                                             _M_get_Tp_allocator());
 529                 this->_M_impl._M_start = __new_start;
 530               }
 531             __catch(...)
 532               {
 533                 _M_destroy_nodes(__new_start._M_node,
 534                                  this->_M_impl._M_start._M_node);
 535                 __throw_exception_again;
 536               }
 537           }
 538         else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
 539           {
 540             iterator __new_finish = _M_reserve_elements_at_back(__n);
 541             __try
 542               {
 543                 std::__uninitialized_copy_a(__first, __last,
 544                                             this->_M_impl._M_finish,
 545                                             _M_get_Tp_allocator());
 546                 this->_M_impl._M_finish = __new_finish;
 547               }
 548             __catch(...)
 549               {
 550                 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 551                                  __new_finish._M_node + 1);
 552                 __throw_exception_again;
 553               }
 554           }
 555         else
 556           _M_insert_aux(__pos, __first, __last, __n);
 557       }
 558
 559   template<typename _Tp, typename _Alloc>
 560 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 561     template<typename... _Args>
 562       typename deque<_Tp, _Alloc>::iterator
 563       deque<_Tp, _Alloc>::
 564       _M_insert_aux(iterator __pos, _Args&&... __args)
 565       {
 566         value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
 567 #else
 568     typename deque<_Tp, _Alloc>::iterator
 569       deque<_Tp, _Alloc>::
 570       _M_insert_aux(iterator __pos, const value_type& __x)
 571       {
 572         value_type __x_copy = __x; // XXX copy
 573 #endif
 574         difference_type __index = __pos - this->_M_impl._M_start;
 575         if (static_cast<size_type>(__index) < size() / 2)
 576           {
 577             push_front(_GLIBCXX_MOVE(front()));
 578             iterator __front1 = this->_M_impl._M_start;
 579             ++__front1;
 580             iterator __front2 = __front1;
 581             ++__front2;
 582             __pos = this->_M_impl._M_start + __index;
 583             iterator __pos1 = __pos;
 584             ++__pos1;
 585             _GLIBCXX_MOVE3(__front2, __pos1, __front1);
 586           }
 587         else
 588           {
 589             push_back(_GLIBCXX_MOVE(back()));
 590             iterator __back1 = this->_M_impl._M_finish;
 591             --__back1;
 592             iterator __back2 = __back1;
 593             --__back2;
 594             __pos = this->_M_impl._M_start + __index;
 595             _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
 596           }
 597         *__pos = _GLIBCXX_MOVE(__x_copy);
 598         return __pos;
 599       }
 600
 601   template <typename _Tp, typename _Alloc>
 602     void
 603     deque<_Tp, _Alloc>::
 604     _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
 605     {
 606       const difference_type __elems_before = __pos - this->_M_impl._M_start;
 607       const size_type __length = this->size();
 608       value_type __x_copy = __x;
 609       if (__elems_before < difference_type(__length / 2))
 610         {
 611           iterator __new_start = _M_reserve_elements_at_front(__n);
 612           iterator __old_start = this->_M_impl._M_start;
 613           __pos = this->_M_impl._M_start + __elems_before;
 614           __try
 615             {
 616               if (__elems_before >= difference_type(__n))
 617                 {
 618                   iterator __start_n = (this->_M_impl._M_start
 619                                         + difference_type(__n));
 620                   std::__uninitialized_move_a(this->_M_impl._M_start,
 621                                               __start_n, __new_start,
 622                                               _M_get_Tp_allocator());
 623                   this->_M_impl._M_start = __new_start;
 624                   _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
 625                   std::fill(__pos - difference_type(__n), __pos, __x_copy);
 626                 }
 627               else
 628                 {
 629                   std::__uninitialized_move_fill(this->_M_impl._M_start,
 630                                                  __pos, __new_start,
 631                                                  this->_M_impl._M_start,
 632                                                  __x_copy,
 633                                                  _M_get_Tp_allocator());
 634                   this->_M_impl._M_start = __new_start;
 635                   std::fill(__old_start, __pos, __x_copy);
 636                 }
 637             }
 638           __catch(...)
 639             {
 640               _M_destroy_nodes(__new_start._M_node,
 641                                this->_M_impl._M_start._M_node);
 642               __throw_exception_again;
 643             }
 644         }
 645       else
 646         {
 647           iterator __new_finish = _M_reserve_elements_at_back(__n);
 648           iterator __old_finish = this->_M_impl._M_finish;
 649           const difference_type __elems_after =
 650             difference_type(__length) - __elems_before;
 651           __pos = this->_M_impl._M_finish - __elems_after;
 652           __try
 653             {
 654               if (__elems_after > difference_type(__n))
 655                 {
 656                   iterator __finish_n = (this->_M_impl._M_finish
 657                                          - difference_type(__n));
 658                   std::__uninitialized_move_a(__finish_n,
 659                                               this->_M_impl._M_finish,
 660                                               this->_M_impl._M_finish,
 661                                               _M_get_Tp_allocator());
 662                   this->_M_impl._M_finish = __new_finish;
 663                   _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
 664                   std::fill(__pos, __pos + difference_type(__n), __x_copy);
 665                 }
 666               else
 667                 {
 668                   std::__uninitialized_fill_move(this->_M_impl._M_finish,
 669                                                  __pos + difference_type(__n),
 670                                                  __x_copy, __pos,
 671                                                  this->_M_impl._M_finish,
 672                                                  _M_get_Tp_allocator());
 673                   this->_M_impl._M_finish = __new_finish;
 674                   std::fill(__pos, __old_finish, __x_copy);
 675                 }
 676             }
 677           __catch(...)
 678             {
 679               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 680                                __new_finish._M_node + 1);
 681               __throw_exception_again;
 682             }
 683         }
 684     }
 685
 686   template <typename _Tp, typename _Alloc>
 687     template <typename _ForwardIterator>
 688       void
 689       deque<_Tp, _Alloc>::
 690       _M_insert_aux(iterator __pos,
 691                     _ForwardIterator __first, _ForwardIterator __last,
 692                     size_type __n)
 693       {
 694         const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
 695         const size_type __length = size();
 696         if (static_cast<size_type>(__elemsbefore) < __length / 2)
 697           {
 698             iterator __new_start = _M_reserve_elements_at_front(__n);
 699             iterator __old_start = this->_M_impl._M_start;
 700             __pos = this->_M_impl._M_start + __elemsbefore;
 701             __try
 702               {
 703                 if (__elemsbefore >= difference_type(__n))
 704                   {
 705                     iterator __start_n = (this->_M_impl._M_start
 706                                           + difference_type(__n));
 707                     std::__uninitialized_move_a(this->_M_impl._M_start,
 708                                                 __start_n, __new_start,
 709                                                 _M_get_Tp_allocator());
 710                     this->_M_impl._M_start = __new_start;
 711                     _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
 712                     std::copy(__first, __last, __pos - difference_type(__n));
 713                   }
 714                 else
 715                   {
 716                     _ForwardIterator __mid = __first;
 717                     std::advance(__mid, difference_type(__n) - __elemsbefore);
 718                     std::__uninitialized_move_copy(this->_M_impl._M_start,
 719                                                    __pos, __first, __mid,
 720                                                    __new_start,
 721                                                    _M_get_Tp_allocator());
 722                     this->_M_impl._M_start = __new_start;
 723                     std::copy(__mid, __last, __old_start);
 724                   }
 725               }
 726             __catch(...)
 727               {
 728                 _M_destroy_nodes(__new_start._M_node,
 729                                  this->_M_impl._M_start._M_node);
 730                 __throw_exception_again;
 731               }
 732           }
 733         else
 734         {
 735           iterator __new_finish = _M_reserve_elements_at_back(__n);
 736           iterator __old_finish = this->_M_impl._M_finish;
 737           const difference_type __elemsafter =
 738             difference_type(__length) - __elemsbefore;
 739           __pos = this->_M_impl._M_finish - __elemsafter;
 740           __try
 741             {
 742               if (__elemsafter > difference_type(__n))
 743                 {
 744                   iterator __finish_n = (this->_M_impl._M_finish
 745                                          - difference_type(__n));
 746                   std::__uninitialized_move_a(__finish_n,
 747                                               this->_M_impl._M_finish,
 748                                               this->_M_impl._M_finish,
 749                                               _M_get_Tp_allocator());
 750                   this->_M_impl._M_finish = __new_finish;
 751                   _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
 752                   std::copy(__first, __last, __pos);
 753                 }
 754               else
 755                 {
 756                   _ForwardIterator __mid = __first;
 757                   std::advance(__mid, __elemsafter);
 758                   std::__uninitialized_copy_move(__mid, __last, __pos,
 759                                                  this->_M_impl._M_finish,
 760                                                  this->_M_impl._M_finish,
 761                                                  _M_get_Tp_allocator());
 762                   this->_M_impl._M_finish = __new_finish;
 763                   std::copy(__first, __mid, __pos);
 764                 }
 765             }
 766           __catch(...)
 767             {
 768               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 769                                __new_finish._M_node + 1);
 770               __throw_exception_again;
 771             }
 772         }
 773       }
 774
 775    template<typename _Tp, typename _Alloc>
 776      void
 777      deque<_Tp, _Alloc>::
 778      _M_destroy_data_aux(iterator __first, iterator __last)
 779      {
 780        for (_Map_pointer __node = __first._M_node + 1;
 781             __node < __last._M_node; ++__node)
 782          std::_Destroy(*__node, *__node + _S_buffer_size(),
 783                        _M_get_Tp_allocator());
 784
 785        if (__first._M_node != __last._M_node)
 786          {
 787            std::_Destroy(__first._M_cur, __first._M_last,
 788                          _M_get_Tp_allocator());
 789            std::_Destroy(__last._M_first, __last._M_cur,
 790                          _M_get_Tp_allocator());
 791          }
 792        else
 793          std::_Destroy(__first._M_cur, __last._M_cur,
 794                        _M_get_Tp_allocator());
 795      }
 796
 797   template <typename _Tp, typename _Alloc>
 798     void
 799     deque<_Tp, _Alloc>::
 800     _M_new_elements_at_front(size_type __new_elems)
 801     {
 802       if (this->max_size() - this->size() < __new_elems)
 803         __throw_length_error(__N("deque::_M_new_elements_at_front"));
 804
 805       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
 806                                      / _S_buffer_size());
 807       _M_reserve_map_at_front(__new_nodes);
 808       size_type __i;
 809       __try
 810         {
 811           for (__i = 1; __i <= __new_nodes; ++__i)
 812             *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
 813         }
 814       __catch(...)
 815         {
 816           for (size_type __j = 1; __j < __i; ++__j)
 817             _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
 818           __throw_exception_again;
 819         }
 820     }
 821
 822   template <typename _Tp, typename _Alloc>
 823     void
 824     deque<_Tp, _Alloc>::
 825     _M_new_elements_at_back(size_type __new_elems)
 826     {
 827       if (this->max_size() - this->size() < __new_elems)
 828         __throw_length_error(__N("deque::_M_new_elements_at_back"));
 829
 830       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
 831                                      / _S_buffer_size());
 832       _M_reserve_map_at_back(__new_nodes);
 833       size_type __i;
 834       __try
 835         {
 836           for (__i = 1; __i <= __new_nodes; ++__i)
 837             *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
 838         }
 839       __catch(...)
 840         {
 841           for (size_type __j = 1; __j < __i; ++__j)
 842             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
 843           __throw_exception_again;
 844         }
 845     }
 846
 847   template <typename _Tp, typename _Alloc>
 848     void
 849     deque<_Tp, _Alloc>::
 850     _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
 851     {
 852       const size_type __old_num_nodes
 853         = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
 854       const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
 855
 856       _Map_pointer __new_nstart;
 857       if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
 858         {
 859           __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
 860                                          - __new_num_nodes) / 2
 861                          + (__add_at_front ? __nodes_to_add : 0);
 862           if (__new_nstart < this->_M_impl._M_start._M_node)
 863             std::copy(this->_M_impl._M_start._M_node,
 864                       this->_M_impl._M_finish._M_node + 1,
 865                       __new_nstart);
 866           else
 867             std::copy_backward(this->_M_impl._M_start._M_node,
 868                                this->_M_impl._M_finish._M_node + 1,
 869                                __new_nstart + __old_num_nodes);
 870         }
 871       else
 872         {
 873           size_type __new_map_size = this->_M_impl._M_map_size
 874                                      + std::max(this->_M_impl._M_map_size,
 875                                                 __nodes_to_add) + 2;
 876
 877           _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
 878           __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
 879                          + (__add_at_front ? __nodes_to_add : 0);
 880           std::copy(this->_M_impl._M_start._M_node,
 881                     this->_M_impl._M_finish._M_node + 1,
 882                     __new_nstart);
 883           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
 884
 885           this->_M_impl._M_map = __new_map;
 886           this->_M_impl._M_map_size = __new_map_size;
 887         }
 888
 889       this->_M_impl._M_start._M_set_node(__new_nstart);
 890       this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
 891     }
 892
 893   // Overload for deque::iterators, exploiting the "segmented-iterator
 894   // optimization".
 895   template<typename _Tp>
 896     void
 897     fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
 898          const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
 899     {
 900       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
 901
 902       for (typename _Self::_Map_pointer __node = __first._M_node + 1;
 903            __node < __last._M_node; ++__node)
 904         std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
 905
 906       if (__first._M_node != __last._M_node)
 907         {
 908           std::fill(__first._M_cur, __first._M_last, __value);
 909           std::fill(__last._M_first, __last._M_cur, __value);
 910         }
 911       else
 912         std::fill(__first._M_cur, __last._M_cur, __value);
 913     }
 914
 915   template<typename _Tp>
 916     _Deque_iterator<_Tp, _Tp&, _Tp*>
 917     copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
 918          _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
 919          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
 920     {
 921       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
 922       typedef typename _Self::difference_type difference_type;
 923
 924       difference_type __len = __last - __first;
 925       while (__len > 0)
 926         {
 927           const difference_type __clen
 928             = std::min(__len, std::min(__first._M_last - __first._M_cur,
 929                                        __result._M_last - __result._M_cur));
 930           std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
 931           __first += __clen;
 932           __result += __clen;
 933           __len -= __clen;
 934         }
 935       return __result;
 936     }
 937
 938   template<typename _Tp>
 939     _Deque_iterator<_Tp, _Tp&, _Tp*>
 940     copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
 941                   _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
 942                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
 943     {
 944       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
 945       typedef typename _Self::difference_type difference_type;
 946
 947       difference_type __len = __last - __first;
 948       while (__len > 0)
 949         {
 950           difference_type __llen = __last._M_cur - __last._M_first;
 951           _Tp* __lend = __last._M_cur;
 952
 953           difference_type __rlen = __result._M_cur - __result._M_first;
 954           _Tp* __rend = __result._M_cur;
 955
 956           if (!__llen)
 957             {
 958               __llen = _Self::_S_buffer_size();
 959               __lend = *(__last._M_node - 1) + __llen;
 960             }
 961           if (!__rlen)
 962             {
 963               __rlen = _Self::_S_buffer_size();
 964               __rend = *(__result._M_node - 1) + __rlen;
 965             }
 966
 967           const difference_type __clen = std::min(__len,
 968                                                   std::min(__llen, __rlen));
 969           std::copy_backward(__lend - __clen, __lend, __rend);
 970           __last -= __clen;
 971           __result -= __clen;
 972           __len -= __clen;
 973         }
 974       return __result;
 975     }
 976
 977 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 978   template<typename _Tp>
 979     _Deque_iterator<_Tp, _Tp&, _Tp*>
 980     move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
 981          _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
 982          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
 983     {
 984       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
 985       typedef typename _Self::difference_type difference_type;
 986
 987       difference_type __len = __last - __first;
 988       while (__len > 0)
 989         {
 990           const difference_type __clen
 991             = std::min(__len, std::min(__first._M_last - __first._M_cur,
 992                                        __result._M_last - __result._M_cur));
 993           std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
 994           __first += __clen;
 995           __result += __clen;
 996           __len -= __clen;
 997         }
 998       return __result;
 999     }
1000
1001   template<typename _Tp>
1002     _Deque_iterator<_Tp, _Tp&, _Tp*>
1003     move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1004                   _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1005                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1006     {
1007       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1008       typedef typename _Self::difference_type difference_type;
1009
1010       difference_type __len = __last - __first;
1011       while (__len > 0)
1012         {
1013           difference_type __llen = __last._M_cur - __last._M_first;
1014           _Tp* __lend = __last._M_cur;
1015
1016           difference_type __rlen = __result._M_cur - __result._M_first;
1017           _Tp* __rend = __result._M_cur;
1018
1019           if (!__llen)
1020             {
1021               __llen = _Self::_S_buffer_size();
1022               __lend = *(__last._M_node - 1) + __llen;
1023             }
1024           if (!__rlen)
1025             {
1026               __rlen = _Self::_S_buffer_size();
1027               __rend = *(__result._M_node - 1) + __rlen;
1028             }
1029
1030           const difference_type __clen = std::min(__len,
1031                                                   std::min(__llen, __rlen));
1032           std::move_backward(__lend - __clen, __lend, __rend);
1033           __last -= __clen;
1034           __result -= __clen;
1035           __len -= __clen;
1036         }
1037       return __result;
1038     }
1039 #endif
1040
1041 _GLIBCXX_END_NESTED_NAMESPACE
1042
1043 #endif