libstdc++-v3/include/bits/deque.tcc

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