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

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