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