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