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

   1 // Deque implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 2, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // You should have received a copy of the GNU General Public License along
  18 // with this library; see the file COPYING.  If not, write to the Free
  19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  20 // USA.
  21
  22 // As a special exception, you may use this file as part of a free software
  23 // library without restriction.  Specifically, if other files instantiate
  24 // templates or use macros or inline functions from this file, or you compile
  25 // this file and link it with other files to produce an executable, this
  26 // file does not by itself cause the resulting executable to be covered by
  27 // the GNU General Public License.  This exception does not however
  28 // invalidate any other reasons why the executable file might be covered by
  29 // the GNU General Public License.
  30
  31 /*
  32  *
  33  * Copyright (c) 1994
  34  * Hewlett-Packard Company
  35  *
  36  * Permission to use, copy, modify, distribute and sell this software
  37  * and its documentation for any purpose is hereby granted without fee,
  38  * provided that the above copyright notice appear in all copies and
  39  * that both that copyright notice and this permission notice appear
  40  * in supporting documentation.  Hewlett-Packard Company makes no
  41  * representations about the suitability of this software for any
  42  * purpose.  It is provided "as is" without express or implied warranty.
  43  *
  44  *
  45  * Copyright (c) 1997
  46  * Silicon Graphics Computer Systems, Inc.
  47  *
  48  * Permission to use, copy, modify, distribute and sell this software
  49  * and its documentation for any purpose is hereby granted without fee,
  50  * provided that the above copyright notice appear in all copies and
  51  * that both that copyright notice and this permission notice appear
  52  * in supporting documentation.  Silicon Graphics makes no
  53  * representations about the suitability of this software for any
  54  * purpose.  It is provided "as is" without express or implied warranty.
  55  */
  56
  57 /** @file deque.tcc
  58  *  This is an internal header file, included by other library headers.
  59  *  You should not attempt to use it directly.
  60  */
  61
  62 #ifndef _DEQUE_TCC
  63 #define _DEQUE_TCC 1
  64
  65 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
  66
  67   template <typename _Tp, typename _Alloc>
  68     deque<_Tp, _Alloc>&
  69     deque<_Tp, _Alloc>::
  70     operator=(const deque& __x)
  71     {
  72       const size_type __len = size();
  73       if (&__x != this)
  74         {
  75           if (__len >= __x.size())
  76             _M_erase_at_end(std::copy(__x.begin(), __x.end(),
  77                                       this->_M_impl._M_start));
  78           else
  79             {
  80               const_iterator __mid = __x.begin() + difference_type(__len);
  81               std::copy(__x.begin(), __mid, this->_M_impl._M_start);
  82               insert(this->_M_impl._M_finish, __mid, __x.end());
  83             }
  84         }
  85       return *this;
  86     }
  87
  88 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  89   template<typename _Tp, typename _Alloc>
  90     template<typename... _Args>
  91       void
  92       deque<_Tp, _Alloc>::
  93       emplace_front(_Args&&... __args)
  94       {
  95         if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
  96           {
  97             this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1,
  98                                     std::forward<_Args>(__args)...);
  99             --this->_M_impl._M_start._M_cur;
 100           }
 101         else
 102           _M_push_front_aux(std::forward<_Args>(__args)...);
 103       }
 104
 105   template<typename _Tp, typename _Alloc>
 106     template<typename... _Args>
 107       void
 108       deque<_Tp, _Alloc>::
 109       emplace_back(_Args&&... __args)
 110       {
 111         if (this->_M_impl._M_finish._M_cur
 112             != this->_M_impl._M_finish._M_last - 1)
 113           {
 114             this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
 115                                     std::forward<_Args>(__args)...);
 116             ++this->_M_impl._M_finish._M_cur;
 117           }
 118         else
 119           _M_push_back_aux(std::forward<_Args>(__args)...);
 120       }
 121 #endif
 122
 123   template <typename _Tp, typename _Alloc>
 124     typename deque<_Tp, _Alloc>::iterator
 125     deque<_Tp, _Alloc>::
 126     insert(iterator __position, const value_type& __x)
 127     {
 128       if (__position._M_cur == this->_M_impl._M_start._M_cur)
 129         {
 130           push_front(__x);
 131           return this->_M_impl._M_start;
 132         }
 133       else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
 134         {
 135           push_back(__x);
 136           iterator __tmp = this->_M_impl._M_finish;
 137           --__tmp;
 138           return __tmp;
 139         }
 140       else
 141         return _M_insert_aux(__position, __x);
 142     }
 143
 144 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 145   template<typename _Tp, typename _Alloc>
 146     template<typename... _Args>
 147       typename deque<_Tp, _Alloc>::iterator
 148       deque<_Tp, _Alloc>::
 149       emplace(iterator __position, _Args&&... __args)
 150       {
 151         if (__position._M_cur == this->_M_impl._M_start._M_cur)
 152           {
 153             push_front(std::forward<_Args>(__args)...);
 154             return this->_M_impl._M_start;
 155           }
 156         else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
 157           {
 158             push_back(std::forward<_Args>(__args)...);
 159             iterator __tmp = this->_M_impl._M_finish;
 160             --__tmp;
 161             return __tmp;
 162           }
 163         else
 164           return _M_insert_aux(__position, std::forward<_Args>(__args)...);
 165       }
 166 #endif
 167
 168   template <typename _Tp, typename _Alloc>
 169     typename deque<_Tp, _Alloc>::iterator
 170     deque<_Tp, _Alloc>::
 171     erase(iterator __position)
 172     {
 173       iterator __next = __position;
 174       ++__next;
 175       const difference_type __index = __position - begin();
 176       if (static_cast<size_type>(__index) < (size() >> 1))
 177         {
 178           if (__position != begin())
 179             _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
 180           pop_front();
 181         }
 182       else
 183         {
 184           if (__next != end())
 185             _GLIBCXX_MOVE3(__next, end(), __position);
 186           pop_back();
 187         }
 188       return begin() + __index;
 189     }
 190
 191   template <typename _Tp, typename _Alloc>
 192     typename deque<_Tp, _Alloc>::iterator
 193     deque<_Tp, _Alloc>::
 194     erase(iterator __first, iterator __last)
 195     {
 196       if (__first == begin() && __last == end())
 197         {
 198           clear();
 199           return end();
 200         }
 201       else
 202         {
 203           const difference_type __n = __last - __first;
 204           const difference_type __elems_before = __first - begin();
 205           if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
 206             {
 207               if (__first != begin())
 208                 _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
 209               _M_erase_at_begin(begin() + __n);
 210             }
 211           else
 212             {
 213               if (__last != end())
 214                 _GLIBCXX_MOVE3(__last, end(), __first);
 215               _M_erase_at_end(end() - __n);
 216             }
 217           return begin() + __elems_before;
 218         }
 219     }
 220
 221   template <typename _Tp, class _Alloc>
 222     template <typename _InputIterator>
 223       void
 224       deque<_Tp, _Alloc>::
 225       _M_assign_aux(_InputIterator __first, _InputIterator __last,
 226                     std::input_iterator_tag)
 227       {
 228         iterator __cur = begin();
 229         for (; __first != __last && __cur != end(); ++__cur, ++__first)
 230           *__cur = *__first;
 231         if (__first == __last)
 232           _M_erase_at_end(__cur);
 233         else
 234           insert(end(), __first, __last);
 235       }
 236
 237   template <typename _Tp, typename _Alloc>
 238     void
 239     deque<_Tp, _Alloc>::
 240     _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
 241     {
 242       if (__pos._M_cur == this->_M_impl._M_start._M_cur)
 243         {
 244           iterator __new_start = _M_reserve_elements_at_front(__n);
 245           try
 246             {
 247               std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
 248                                           __x, _M_get_Tp_allocator());
 249               this->_M_impl._M_start = __new_start;
 250             }
 251           catch(...)
 252             {
 253               _M_destroy_nodes(__new_start._M_node,
 254                                this->_M_impl._M_start._M_node);
 255               __throw_exception_again;
 256             }
 257         }
 258       else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
 259         {
 260           iterator __new_finish = _M_reserve_elements_at_back(__n);
 261           try
 262             {
 263               std::__uninitialized_fill_a(this->_M_impl._M_finish,
 264                                           __new_finish, __x,
 265                                           _M_get_Tp_allocator());
 266               this->_M_impl._M_finish = __new_finish;
 267             }
 268           catch(...)
 269             {
 270               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 271                                __new_finish._M_node + 1);
 272               __throw_exception_again;
 273             }
 274         }
 275       else
 276         _M_insert_aux(__pos, __n, __x);
 277     }
 278
 279   template <typename _Tp, typename _Alloc>
 280     void
 281     deque<_Tp, _Alloc>::
 282     _M_fill_initialize(const value_type& __value)
 283     {
 284       _Map_pointer __cur;
 285       try
 286         {
 287           for (__cur = this->_M_impl._M_start._M_node;
 288                __cur < this->_M_impl._M_finish._M_node;
 289                ++__cur)
 290             std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
 291                                         __value, _M_get_Tp_allocator());
 292           std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
 293                                       this->_M_impl._M_finish._M_cur,
 294                                       __value, _M_get_Tp_allocator());
 295         }
 296       catch(...)
 297         {
 298           std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
 299                         _M_get_Tp_allocator());
 300           __throw_exception_again;
 301         }
 302     }
 303
 304   template <typename _Tp, typename _Alloc>
 305     template <typename _InputIterator>
 306       void
 307       deque<_Tp, _Alloc>::
 308       _M_range_initialize(_InputIterator __first, _InputIterator __last,
 309                           std::input_iterator_tag)
 310       {
 311         this->_M_initialize_map(0);
 312         try
 313           {
 314             for (; __first != __last; ++__first)
 315               push_back(*__first);
 316           }
 317         catch(...)
 318           {
 319             clear();
 320             __throw_exception_again;
 321           }
 322       }
 323
 324   template <typename _Tp, typename _Alloc>
 325     template <typename _ForwardIterator>
 326       void
 327       deque<_Tp, _Alloc>::
 328       _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
 329                           std::forward_iterator_tag)
 330       {
 331         const size_type __n = std::distance(__first, __last);
 332         this->_M_initialize_map(__n);
 333
 334         _Map_pointer __cur_node;
 335         try
 336           {
 337             for (__cur_node = this->_M_impl._M_start._M_node;
 338                  __cur_node < this->_M_impl._M_finish._M_node;
 339                  ++__cur_node)
 340               {
 341                 _ForwardIterator __mid = __first;
 342                 std::advance(__mid, _S_buffer_size());
 343                 std::__uninitialized_copy_a(__first, __mid, *__cur_node,
 344                                             _M_get_Tp_allocator());
 345                 __first = __mid;
 346               }
 347             std::__uninitialized_copy_a(__first, __last,
 348                                         this->_M_impl._M_finish._M_first,
 349                                         _M_get_Tp_allocator());
 350           }
 351         catch(...)
 352           {
 353             std::_Destroy(this->_M_impl._M_start,
 354                           iterator(*__cur_node, __cur_node),
 355                           _M_get_Tp_allocator());
 356             __throw_exception_again;
 357           }
 358       }
 359
 360   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
 361   template<typename _Tp, typename _Alloc>
 362 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 363     template<typename... _Args>
 364       void
 365       deque<_Tp, _Alloc>::
 366       _M_push_back_aux(_Args&&... __args)
 367 #else
 368       void
 369       deque<_Tp, _Alloc>::
 370       _M_push_back_aux(const value_type& __t)
 371 #endif
 372       {
 373         _M_reserve_map_at_back();
 374         *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
 375         try
 376           {
 377 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 378             this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
 379                                     std::forward<_Args>(__args)...);
 380 #else
 381             this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
 382 #endif
 383             this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
 384                                                 + 1);
 385             this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
 386           }
 387         catch(...)
 388           {
 389             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
 390             __throw_exception_again;
 391           }
 392       }
 393
 394   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
 395   template<typename _Tp, typename _Alloc>
 396 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 397     template<typename... _Args>
 398       void
 399       deque<_Tp, _Alloc>::
 400       _M_push_front_aux(_Args&&... __args)
 401 #else
 402       void
 403       deque<_Tp, _Alloc>::
 404       _M_push_front_aux(const value_type& __t)
 405 #endif
 406       {
 407         _M_reserve_map_at_front();
 408         *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
 409         try
 410           {
 411             this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
 412                                                - 1);
 413             this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
 414 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 415             this->_M_impl.construct(this->_M_impl._M_start._M_cur,
 416                                     std::forward<_Args>(__args)...);
 417 #else
 418             this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
 419 #endif
 420           }
 421         catch(...)
 422           {
 423             ++this->_M_impl._M_start;
 424             _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
 425             __throw_exception_again;
 426           }
 427       }
 428
 429   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
 430   template <typename _Tp, typename _Alloc>
 431     void deque<_Tp, _Alloc>::
 432     _M_pop_back_aux()
 433     {
 434       _M_deallocate_node(this->_M_impl._M_finish._M_first);
 435       this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
 436       this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
 437       this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
 438     }
 439
 440   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
 441   // Note that if the deque has at least one element (a precondition for this
 442   // member function), and if
 443   //   _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
 444   // then the deque must have at least two nodes.
 445   template <typename _Tp, typename _Alloc>
 446     void deque<_Tp, _Alloc>::
 447     _M_pop_front_aux()
 448     {
 449       this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
 450       _M_deallocate_node(this->_M_impl._M_start._M_first);
 451       this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
 452       this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
 453     }
 454
 455   template <typename _Tp, typename _Alloc>
 456     template <typename _InputIterator>
 457       void
 458       deque<_Tp, _Alloc>::
 459       _M_range_insert_aux(iterator __pos,
 460                           _InputIterator __first, _InputIterator __last,
 461                           std::input_iterator_tag)
 462       { std::copy(__first, __last, std::inserter(*this, __pos)); }
 463
 464   template <typename _Tp, typename _Alloc>
 465     template <typename _ForwardIterator>
 466       void
 467       deque<_Tp, _Alloc>::
 468       _M_range_insert_aux(iterator __pos,
 469                           _ForwardIterator __first, _ForwardIterator __last,
 470                           std::forward_iterator_tag)
 471       {
 472         const size_type __n = std::distance(__first, __last);
 473         if (__pos._M_cur == this->_M_impl._M_start._M_cur)
 474           {
 475             iterator __new_start = _M_reserve_elements_at_front(__n);
 476             try
 477               {
 478                 std::__uninitialized_copy_a(__first, __last, __new_start,
 479                                             _M_get_Tp_allocator());
 480                 this->_M_impl._M_start = __new_start;
 481               }
 482             catch(...)
 483               {
 484                 _M_destroy_nodes(__new_start._M_node,
 485                                  this->_M_impl._M_start._M_node);
 486                 __throw_exception_again;
 487               }
 488           }
 489         else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
 490           {
 491             iterator __new_finish = _M_reserve_elements_at_back(__n);
 492             try
 493               {
 494                 std::__uninitialized_copy_a(__first, __last,
 495                                             this->_M_impl._M_finish,
 496                                             _M_get_Tp_allocator());
 497                 this->_M_impl._M_finish = __new_finish;
 498               }
 499             catch(...)
 500               {
 501                 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 502                                  __new_finish._M_node + 1);
 503                 __throw_exception_again;
 504               }
 505           }
 506         else
 507           _M_insert_aux(__pos, __first, __last, __n);
 508       }
 509
 510   template<typename _Tp, typename _Alloc>
 511 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 512     template<typename... _Args>
 513       typename deque<_Tp, _Alloc>::iterator
 514       deque<_Tp, _Alloc>::
 515       _M_insert_aux(iterator __pos, _Args&&... __args)
 516       {
 517         value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
 518 #else
 519     typename deque<_Tp, _Alloc>::iterator
 520       deque<_Tp, _Alloc>::
 521       _M_insert_aux(iterator __pos, const value_type& __x)
 522       {
 523         value_type __x_copy = __x; // XXX copy
 524 #endif
 525         difference_type __index = __pos - this->_M_impl._M_start;
 526         if (static_cast<size_type>(__index) < size() / 2)
 527           {
 528             push_front(_GLIBCXX_MOVE(front()));
 529             iterator __front1 = this->_M_impl._M_start;
 530             ++__front1;
 531             iterator __front2 = __front1;
 532             ++__front2;
 533             __pos = this->_M_impl._M_start + __index;
 534             iterator __pos1 = __pos;
 535             ++__pos1;
 536             _GLIBCXX_MOVE3(__front2, __pos1, __front1);
 537           }
 538         else
 539           {
 540             push_back(_GLIBCXX_MOVE(back()));
 541             iterator __back1 = this->_M_impl._M_finish;
 542             --__back1;
 543             iterator __back2 = __back1;
 544             --__back2;
 545             __pos = this->_M_impl._M_start + __index;
 546             _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
 547           }
 548         *__pos = _GLIBCXX_MOVE(__x_copy);
 549         return __pos;
 550       }
 551
 552   template <typename _Tp, typename _Alloc>
 553     void
 554     deque<_Tp, _Alloc>::
 555     _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
 556     {
 557       const difference_type __elems_before = __pos - this->_M_impl._M_start;
 558       const size_type __length = this->size();
 559       value_type __x_copy = __x;
 560       if (__elems_before < difference_type(__length / 2))
 561         {
 562           iterator __new_start = _M_reserve_elements_at_front(__n);
 563           iterator __old_start = this->_M_impl._M_start;
 564           __pos = this->_M_impl._M_start + __elems_before;
 565           try
 566             {
 567               if (__elems_before >= difference_type(__n))
 568                 {
 569                   iterator __start_n = (this->_M_impl._M_start
 570                                         + difference_type(__n));
 571                   std::__uninitialized_move_a(this->_M_impl._M_start,
 572                                               __start_n, __new_start,
 573                                               _M_get_Tp_allocator());
 574                   this->_M_impl._M_start = __new_start;
 575                   _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
 576                   std::fill(__pos - difference_type(__n), __pos, __x_copy);
 577                 }
 578               else
 579                 {
 580                   std::__uninitialized_move_fill(this->_M_impl._M_start,
 581                                                  __pos, __new_start,
 582                                                  this->_M_impl._M_start,
 583                                                  __x_copy,
 584                                                  _M_get_Tp_allocator());
 585                   this->_M_impl._M_start = __new_start;
 586                   std::fill(__old_start, __pos, __x_copy);
 587                 }
 588             }
 589           catch(...)
 590             {
 591               _M_destroy_nodes(__new_start._M_node,
 592                                this->_M_impl._M_start._M_node);
 593               __throw_exception_again;
 594             }
 595         }
 596       else
 597         {
 598           iterator __new_finish = _M_reserve_elements_at_back(__n);
 599           iterator __old_finish = this->_M_impl._M_finish;
 600           const difference_type __elems_after =
 601             difference_type(__length) - __elems_before;
 602           __pos = this->_M_impl._M_finish - __elems_after;
 603           try
 604             {
 605               if (__elems_after > difference_type(__n))
 606                 {
 607                   iterator __finish_n = (this->_M_impl._M_finish
 608                                          - difference_type(__n));
 609                   std::__uninitialized_move_a(__finish_n,
 610                                               this->_M_impl._M_finish,
 611                                               this->_M_impl._M_finish,
 612                                               _M_get_Tp_allocator());
 613                   this->_M_impl._M_finish = __new_finish;
 614                   _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
 615                   std::fill(__pos, __pos + difference_type(__n), __x_copy);
 616                 }
 617               else
 618                 {
 619                   std::__uninitialized_fill_move(this->_M_impl._M_finish,
 620                                                  __pos + difference_type(__n),
 621                                                  __x_copy, __pos,
 622                                                  this->_M_impl._M_finish,
 623                                                  _M_get_Tp_allocator());
 624                   this->_M_impl._M_finish = __new_finish;
 625                   std::fill(__pos, __old_finish, __x_copy);
 626                 }
 627             }
 628           catch(...)
 629             {
 630               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 631                                __new_finish._M_node + 1);
 632               __throw_exception_again;
 633             }
 634         }
 635     }
 636
 637   template <typename _Tp, typename _Alloc>
 638     template <typename _ForwardIterator>
 639       void
 640       deque<_Tp, _Alloc>::
 641       _M_insert_aux(iterator __pos,
 642                     _ForwardIterator __first, _ForwardIterator __last,
 643                     size_type __n)
 644       {
 645         const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
 646         const size_type __length = size();
 647         if (static_cast<size_type>(__elemsbefore) < __length / 2)
 648           {
 649             iterator __new_start = _M_reserve_elements_at_front(__n);
 650             iterator __old_start = this->_M_impl._M_start;
 651             __pos = this->_M_impl._M_start + __elemsbefore;
 652             try
 653               {
 654                 if (__elemsbefore >= difference_type(__n))
 655                   {
 656                     iterator __start_n = (this->_M_impl._M_start
 657                                           + difference_type(__n));
 658                     std::__uninitialized_move_a(this->_M_impl._M_start,
 659                                                 __start_n, __new_start,
 660                                                 _M_get_Tp_allocator());
 661                     this->_M_impl._M_start = __new_start;
 662                     _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
 663                     std::copy(__first, __last, __pos - difference_type(__n));
 664                   }
 665                 else
 666                   {
 667                     _ForwardIterator __mid = __first;
 668                     std::advance(__mid, difference_type(__n) - __elemsbefore);
 669                     std::__uninitialized_move_copy(this->_M_impl._M_start,
 670                                                    __pos, __first, __mid,
 671                                                    __new_start,
 672                                                    _M_get_Tp_allocator());
 673                     this->_M_impl._M_start = __new_start;
 674                     std::copy(__mid, __last, __old_start);
 675                   }
 676               }
 677             catch(...)
 678               {
 679                 _M_destroy_nodes(__new_start._M_node,
 680                                  this->_M_impl._M_start._M_node);
 681                 __throw_exception_again;
 682               }
 683           }
 684         else
 685         {
 686           iterator __new_finish = _M_reserve_elements_at_back(__n);
 687           iterator __old_finish = this->_M_impl._M_finish;
 688           const difference_type __elemsafter =
 689             difference_type(__length) - __elemsbefore;
 690           __pos = this->_M_impl._M_finish - __elemsafter;
 691           try
 692             {
 693               if (__elemsafter > difference_type(__n))
 694                 {
 695                   iterator __finish_n = (this->_M_impl._M_finish
 696                                          - difference_type(__n));
 697                   std::__uninitialized_move_a(__finish_n,
 698                                               this->_M_impl._M_finish,
 699                                               this->_M_impl._M_finish,
 700                                               _M_get_Tp_allocator());
 701                   this->_M_impl._M_finish = __new_finish;
 702                   _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
 703                   std::copy(__first, __last, __pos);
 704                 }
 705               else
 706                 {
 707                   _ForwardIterator __mid = __first;
 708                   std::advance(__mid, __elemsafter);
 709                   std::__uninitialized_copy_move(__mid, __last, __pos,
 710                                                  this->_M_impl._M_finish,
 711                                                  this->_M_impl._M_finish,
 712                                                  _M_get_Tp_allocator());
 713                   this->_M_impl._M_finish = __new_finish;
 714                   std::copy(__first, __mid, __pos);
 715                 }
 716             }
 717           catch(...)
 718             {
 719               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 720                                __new_finish._M_node + 1);
 721               __throw_exception_again;
 722             }
 723         }
 724       }
 725
 726    template<typename _Tp, typename _Alloc>
 727      void
 728      deque<_Tp, _Alloc>::
 729      _M_destroy_data_aux(iterator __first, iterator __last)
 730      {
 731        for (_Map_pointer __node = __first._M_node + 1;
 732             __node < __last._M_node; ++__node)
 733          std::_Destroy(*__node, *__node + _S_buffer_size(),
 734                        _M_get_Tp_allocator());
 735
 736        if (__first._M_node != __last._M_node)
 737          {
 738            std::_Destroy(__first._M_cur, __first._M_last,
 739                          _M_get_Tp_allocator());
 740            std::_Destroy(__last._M_first, __last._M_cur,
 741                          _M_get_Tp_allocator());
 742          }
 743        else
 744          std::_Destroy(__first._M_cur, __last._M_cur,
 745                        _M_get_Tp_allocator());
 746      }
 747
 748   template <typename _Tp, typename _Alloc>
 749     void
 750     deque<_Tp, _Alloc>::
 751     _M_new_elements_at_front(size_type __new_elems)
 752     {
 753       if (this->max_size() - this->size() < __new_elems)
 754         __throw_length_error(__N("deque::_M_new_elements_at_front"));
 755
 756       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
 757                                      / _S_buffer_size());
 758       _M_reserve_map_at_front(__new_nodes);
 759       size_type __i;
 760       try
 761         {
 762           for (__i = 1; __i <= __new_nodes; ++__i)
 763             *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
 764         }
 765       catch(...)
 766         {
 767           for (size_type __j = 1; __j < __i; ++__j)
 768             _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
 769           __throw_exception_again;
 770         }
 771     }
 772
 773   template <typename _Tp, typename _Alloc>
 774     void
 775     deque<_Tp, _Alloc>::
 776     _M_new_elements_at_back(size_type __new_elems)
 777     {
 778       if (this->max_size() - this->size() < __new_elems)
 779         __throw_length_error(__N("deque::_M_new_elements_at_back"));
 780
 781       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
 782                                      / _S_buffer_size());
 783       _M_reserve_map_at_back(__new_nodes);
 784       size_type __i;
 785       try
 786         {
 787           for (__i = 1; __i <= __new_nodes; ++__i)
 788             *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
 789         }
 790       catch(...)
 791         {
 792           for (size_type __j = 1; __j < __i; ++__j)
 793             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
 794           __throw_exception_again;
 795         }
 796     }
 797
 798   template <typename _Tp, typename _Alloc>
 799     void
 800     deque<_Tp, _Alloc>::
 801     _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
 802     {
 803       const size_type __old_num_nodes
 804         = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
 805       const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
 806
 807       _Map_pointer __new_nstart;
 808       if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
 809         {
 810           __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
 811                                          - __new_num_nodes) / 2
 812                          + (__add_at_front ? __nodes_to_add : 0);
 813           if (__new_nstart < this->_M_impl._M_start._M_node)
 814             std::copy(this->_M_impl._M_start._M_node,
 815                       this->_M_impl._M_finish._M_node + 1,
 816                       __new_nstart);
 817           else
 818             std::copy_backward(this->_M_impl._M_start._M_node,
 819                                this->_M_impl._M_finish._M_node + 1,
 820                                __new_nstart + __old_num_nodes);
 821         }
 822       else
 823         {
 824           size_type __new_map_size = this->_M_impl._M_map_size
 825                                      + std::max(this->_M_impl._M_map_size,
 826                                                 __nodes_to_add) + 2;
 827
 828           _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
 829           __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
 830                          + (__add_at_front ? __nodes_to_add : 0);
 831           std::copy(this->_M_impl._M_start._M_node,
 832                     this->_M_impl._M_finish._M_node + 1,
 833                     __new_nstart);
 834           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
 835
 836           this->_M_impl._M_map = __new_map;
 837           this->_M_impl._M_map_size = __new_map_size;
 838         }
 839
 840       this->_M_impl._M_start._M_set_node(__new_nstart);
 841       this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
 842     }
 843
 844   // Overload for deque::iterators, exploiting the "segmented-iterator
 845   // optimization".  NB: leave const_iterators alone!
 846   template<typename _Tp>
 847     void
 848     fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
 849          const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
 850     {
 851       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
 852
 853       for (typename _Self::_Map_pointer __node = __first._M_node + 1;
 854            __node < __last._M_node; ++__node)
 855         std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
 856
 857       if (__first._M_node != __last._M_node)
 858         {
 859           std::fill(__first._M_cur, __first._M_last, __value);
 860           std::fill(__last._M_first, __last._M_cur, __value);
 861         }
 862       else
 863         std::fill(__first._M_cur, __last._M_cur, __value);
 864     }
 865
 866 _GLIBCXX_END_NESTED_NAMESPACE
 867
 868 #endif