l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.9/include/bits/deque.tcc

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