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

   1 // Deque implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
   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   template <typename _Tp, typename _Alloc>
  89     typename deque<_Tp, _Alloc>::iterator
  90     deque<_Tp, _Alloc>::
  91     insert(iterator __position, const value_type& __x)
  92     {
  93       if (__position._M_cur == this->_M_impl._M_start._M_cur)
  94         {
  95           push_front(__x);
  96           return this->_M_impl._M_start;
  97         }
  98       else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
  99         {
 100           push_back(__x);
 101           iterator __tmp = this->_M_impl._M_finish;
 102           --__tmp;
 103           return __tmp;
 104         }
 105       else
 106         return _M_insert_aux(__position, __x);
 107     }
 108
 109   template <typename _Tp, typename _Alloc>
 110     typename deque<_Tp, _Alloc>::iterator
 111     deque<_Tp, _Alloc>::
 112     erase(iterator __position)
 113     {
 114       iterator __next = __position;
 115       ++__next;
 116       const difference_type __index = __position - begin();
 117       if (static_cast<size_type>(__index) < (size() >> 1))
 118         {
 119           if (__position != begin())
 120             _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
 121           pop_front();
 122         }
 123       else
 124         {
 125           if (__next != end())
 126             _GLIBCXX_MOVE3(__next, end(), __position);
 127           pop_back();
 128         }
 129       return begin() + __index;
 130     }
 131
 132   template <typename _Tp, typename _Alloc>
 133     typename deque<_Tp, _Alloc>::iterator
 134     deque<_Tp, _Alloc>::
 135     erase(iterator __first, iterator __last)
 136     {
 137       if (__first == begin() && __last == end())
 138         {
 139           clear();
 140           return end();
 141         }
 142       else
 143         {
 144           const difference_type __n = __last - __first;
 145           const difference_type __elems_before = __first - begin();
 146           if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
 147             {
 148               if (__first != begin())
 149                 _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
 150               _M_erase_at_begin(begin() + __n);
 151             }
 152           else
 153             {
 154               if (__last != end())
 155                 _GLIBCXX_MOVE3(__last, end(), __first);
 156               _M_erase_at_end(end() - __n);
 157             }
 158           return begin() + __elems_before;
 159         }
 160     }
 161
 162   template <typename _Tp, class _Alloc>
 163     template <typename _InputIterator>
 164       void
 165       deque<_Tp, _Alloc>::
 166       _M_assign_aux(_InputIterator __first, _InputIterator __last,
 167                     std::input_iterator_tag)
 168       {
 169         iterator __cur = begin();
 170         for (; __first != __last && __cur != end(); ++__cur, ++__first)
 171           *__cur = *__first;
 172         if (__first == __last)
 173           _M_erase_at_end(__cur);
 174         else
 175           insert(end(), __first, __last);
 176       }
 177
 178   template <typename _Tp, typename _Alloc>
 179     void
 180     deque<_Tp, _Alloc>::
 181     _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
 182     {
 183       if (__pos._M_cur == this->_M_impl._M_start._M_cur)
 184         {
 185           iterator __new_start = _M_reserve_elements_at_front(__n);
 186           try
 187             {
 188               std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
 189                                           __x, _M_get_Tp_allocator());
 190               this->_M_impl._M_start = __new_start;
 191             }
 192           catch(...)
 193             {
 194               _M_destroy_nodes(__new_start._M_node,
 195                                this->_M_impl._M_start._M_node);
 196               __throw_exception_again;
 197             }
 198         }
 199       else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
 200         {
 201           iterator __new_finish = _M_reserve_elements_at_back(__n);
 202           try
 203             {
 204               std::__uninitialized_fill_a(this->_M_impl._M_finish,
 205                                           __new_finish, __x,
 206                                           _M_get_Tp_allocator());
 207               this->_M_impl._M_finish = __new_finish;
 208             }
 209           catch(...)
 210             {
 211               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 212                                __new_finish._M_node + 1);
 213               __throw_exception_again;
 214             }
 215         }
 216       else
 217         _M_insert_aux(__pos, __n, __x);
 218     }
 219
 220   template <typename _Tp, typename _Alloc>
 221     void
 222     deque<_Tp, _Alloc>::
 223     _M_fill_initialize(const value_type& __value)
 224     {
 225       _Map_pointer __cur;
 226       try
 227         {
 228           for (__cur = this->_M_impl._M_start._M_node;
 229                __cur < this->_M_impl._M_finish._M_node;
 230                ++__cur)
 231             std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
 232                                         __value, _M_get_Tp_allocator());
 233           std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
 234                                       this->_M_impl._M_finish._M_cur,
 235                                       __value, _M_get_Tp_allocator());
 236         }
 237       catch(...)
 238         {
 239           std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
 240                         _M_get_Tp_allocator());
 241           __throw_exception_again;
 242         }
 243     }
 244
 245   template <typename _Tp, typename _Alloc>
 246     template <typename _InputIterator>
 247       void
 248       deque<_Tp, _Alloc>::
 249       _M_range_initialize(_InputIterator __first, _InputIterator __last,
 250                           std::input_iterator_tag)
 251       {
 252         this->_M_initialize_map(0);
 253         try
 254           {
 255             for (; __first != __last; ++__first)
 256               push_back(*__first);
 257           }
 258         catch(...)
 259           {
 260             clear();
 261             __throw_exception_again;
 262           }
 263       }
 264
 265   template <typename _Tp, typename _Alloc>
 266     template <typename _ForwardIterator>
 267       void
 268       deque<_Tp, _Alloc>::
 269       _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
 270                           std::forward_iterator_tag)
 271       {
 272         const size_type __n = std::distance(__first, __last);
 273         this->_M_initialize_map(__n);
 274
 275         _Map_pointer __cur_node;
 276         try
 277           {
 278             for (__cur_node = this->_M_impl._M_start._M_node;
 279                  __cur_node < this->_M_impl._M_finish._M_node;
 280                  ++__cur_node)
 281               {
 282                 _ForwardIterator __mid = __first;
 283                 std::advance(__mid, _S_buffer_size());
 284                 std::__uninitialized_copy_a(__first, __mid, *__cur_node,
 285                                             _M_get_Tp_allocator());
 286                 __first = __mid;
 287               }
 288             std::__uninitialized_copy_a(__first, __last,
 289                                         this->_M_impl._M_finish._M_first,
 290                                         _M_get_Tp_allocator());
 291           }
 292         catch(...)
 293           {
 294             std::_Destroy(this->_M_impl._M_start,
 295                           iterator(*__cur_node, __cur_node),
 296                           _M_get_Tp_allocator());
 297             __throw_exception_again;
 298           }
 299       }
 300
 301   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
 302   template <typename _Tp, typename _Alloc>
 303     void
 304     deque<_Tp, _Alloc>::
 305     _M_push_back_aux(const value_type& __t)
 306     {
 307       value_type __t_copy = __t;
 308       _M_reserve_map_at_back();
 309       *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
 310       try
 311         {
 312           this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t_copy);
 313           this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
 314                                               + 1);
 315           this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
 316         }
 317       catch(...)
 318         {
 319           _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
 320           __throw_exception_again;
 321         }
 322     }
 323
 324   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
 325   template <typename _Tp, typename _Alloc>
 326     void
 327     deque<_Tp, _Alloc>::
 328     _M_push_front_aux(const value_type& __t)
 329     {
 330       value_type __t_copy = __t;
 331       _M_reserve_map_at_front();
 332       *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
 333       try
 334         {
 335           this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
 336                                              - 1);
 337           this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
 338           this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t_copy);
 339         }
 340       catch(...)
 341         {
 342           ++this->_M_impl._M_start;
 343           _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
 344           __throw_exception_again;
 345         }
 346     }
 347
 348   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
 349   template <typename _Tp, typename _Alloc>
 350     void deque<_Tp, _Alloc>::
 351     _M_pop_back_aux()
 352     {
 353       _M_deallocate_node(this->_M_impl._M_finish._M_first);
 354       this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
 355       this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
 356       this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
 357     }
 358
 359   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
 360   // Note that if the deque has at least one element (a precondition for this
 361   // member function), and if
 362   //   _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
 363   // then the deque must have at least two nodes.
 364   template <typename _Tp, typename _Alloc>
 365     void deque<_Tp, _Alloc>::
 366     _M_pop_front_aux()
 367     {
 368       this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
 369       _M_deallocate_node(this->_M_impl._M_start._M_first);
 370       this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
 371       this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
 372     }
 373
 374   template <typename _Tp, typename _Alloc>
 375     template <typename _InputIterator>
 376       void
 377       deque<_Tp, _Alloc>::
 378       _M_range_insert_aux(iterator __pos,
 379                           _InputIterator __first, _InputIterator __last,
 380                           std::input_iterator_tag)
 381       { std::copy(__first, __last, std::inserter(*this, __pos)); }
 382
 383   template <typename _Tp, typename _Alloc>
 384     template <typename _ForwardIterator>
 385       void
 386       deque<_Tp, _Alloc>::
 387       _M_range_insert_aux(iterator __pos,
 388                           _ForwardIterator __first, _ForwardIterator __last,
 389                           std::forward_iterator_tag)
 390       {
 391         const size_type __n = std::distance(__first, __last);
 392         if (__pos._M_cur == this->_M_impl._M_start._M_cur)
 393           {
 394             iterator __new_start = _M_reserve_elements_at_front(__n);
 395             try
 396               {
 397                 std::__uninitialized_copy_a(__first, __last, __new_start,
 398                                             _M_get_Tp_allocator());
 399                 this->_M_impl._M_start = __new_start;
 400               }
 401             catch(...)
 402               {
 403                 _M_destroy_nodes(__new_start._M_node,
 404                                  this->_M_impl._M_start._M_node);
 405                 __throw_exception_again;
 406               }
 407           }
 408         else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
 409           {
 410             iterator __new_finish = _M_reserve_elements_at_back(__n);
 411             try
 412               {
 413                 std::__uninitialized_copy_a(__first, __last,
 414                                             this->_M_impl._M_finish,
 415                                             _M_get_Tp_allocator());
 416                 this->_M_impl._M_finish = __new_finish;
 417               }
 418             catch(...)
 419               {
 420                 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 421                                  __new_finish._M_node + 1);
 422                 __throw_exception_again;
 423               }
 424           }
 425         else
 426           _M_insert_aux(__pos, __first, __last, __n);
 427       }
 428
 429   template <typename _Tp, typename _Alloc>
 430     typename deque<_Tp, _Alloc>::iterator
 431     deque<_Tp, _Alloc>::
 432     _M_insert_aux(iterator __pos, const value_type& __x)
 433     {
 434       difference_type __index = __pos - this->_M_impl._M_start;
 435       value_type __x_copy = __x; // XXX copy
 436       if (static_cast<size_type>(__index) < size() / 2)
 437         {
 438           push_front(front());
 439           iterator __front1 = this->_M_impl._M_start;
 440           ++__front1;
 441           iterator __front2 = __front1;
 442           ++__front2;
 443           __pos = this->_M_impl._M_start + __index;
 444           iterator __pos1 = __pos;
 445           ++__pos1;
 446           std::copy(__front2, __pos1, __front1);
 447         }
 448       else
 449         {
 450           push_back(back());
 451           iterator __back1 = this->_M_impl._M_finish;
 452           --__back1;
 453           iterator __back2 = __back1;
 454           --__back2;
 455           __pos = this->_M_impl._M_start + __index;
 456           std::copy_backward(__pos, __back2, __back1);
 457         }
 458       *__pos = __x_copy;
 459       return __pos;
 460     }
 461
 462   template <typename _Tp, typename _Alloc>
 463     void
 464     deque<_Tp, _Alloc>::
 465     _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
 466     {
 467       const difference_type __elems_before = __pos - this->_M_impl._M_start;
 468       const size_type __length = this->size();
 469       value_type __x_copy = __x;
 470       if (__elems_before < difference_type(__length / 2))
 471         {
 472           iterator __new_start = _M_reserve_elements_at_front(__n);
 473           iterator __old_start = this->_M_impl._M_start;
 474           __pos = this->_M_impl._M_start + __elems_before;
 475           try
 476             {
 477               if (__elems_before >= difference_type(__n))
 478                 {
 479                   iterator __start_n = (this->_M_impl._M_start
 480                                         + difference_type(__n));
 481                   std::__uninitialized_copy_a(this->_M_impl._M_start,
 482                                               __start_n, __new_start,
 483                                               _M_get_Tp_allocator());
 484                   this->_M_impl._M_start = __new_start;
 485                   std::copy(__start_n, __pos, __old_start);
 486                   std::fill(__pos - difference_type(__n), __pos, __x_copy);
 487                 }
 488               else
 489                 {
 490                   std::__uninitialized_copy_fill(this->_M_impl._M_start,
 491                                                  __pos, __new_start,
 492                                                  this->_M_impl._M_start,
 493                                                  __x_copy,
 494                                                  _M_get_Tp_allocator());
 495                   this->_M_impl._M_start = __new_start;
 496                   std::fill(__old_start, __pos, __x_copy);
 497                 }
 498             }
 499           catch(...)
 500             {
 501               _M_destroy_nodes(__new_start._M_node,
 502                                this->_M_impl._M_start._M_node);
 503               __throw_exception_again;
 504             }
 505         }
 506       else
 507         {
 508           iterator __new_finish = _M_reserve_elements_at_back(__n);
 509           iterator __old_finish = this->_M_impl._M_finish;
 510           const difference_type __elems_after =
 511             difference_type(__length) - __elems_before;
 512           __pos = this->_M_impl._M_finish - __elems_after;
 513           try
 514             {
 515               if (__elems_after > difference_type(__n))
 516                 {
 517                   iterator __finish_n = (this->_M_impl._M_finish
 518                                          - difference_type(__n));
 519                   std::__uninitialized_copy_a(__finish_n,
 520                                               this->_M_impl._M_finish,
 521                                               this->_M_impl._M_finish,
 522                                               _M_get_Tp_allocator());
 523                   this->_M_impl._M_finish = __new_finish;
 524                   std::copy_backward(__pos, __finish_n, __old_finish);
 525                   std::fill(__pos, __pos + difference_type(__n), __x_copy);
 526                 }
 527               else
 528                 {
 529                   std::__uninitialized_fill_copy(this->_M_impl._M_finish,
 530                                                  __pos + difference_type(__n),
 531                                                  __x_copy, __pos,
 532                                                  this->_M_impl._M_finish,
 533                                                  _M_get_Tp_allocator());
 534                   this->_M_impl._M_finish = __new_finish;
 535                   std::fill(__pos, __old_finish, __x_copy);
 536                 }
 537             }
 538           catch(...)
 539             {
 540               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 541                                __new_finish._M_node + 1);
 542               __throw_exception_again;
 543             }
 544         }
 545     }
 546
 547   template <typename _Tp, typename _Alloc>
 548     template <typename _ForwardIterator>
 549       void
 550       deque<_Tp, _Alloc>::
 551       _M_insert_aux(iterator __pos,
 552                     _ForwardIterator __first, _ForwardIterator __last,
 553                     size_type __n)
 554       {
 555         const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
 556         const size_type __length = size();
 557         if (static_cast<size_type>(__elemsbefore) < __length / 2)
 558           {
 559             iterator __new_start = _M_reserve_elements_at_front(__n);
 560             iterator __old_start = this->_M_impl._M_start;
 561             __pos = this->_M_impl._M_start + __elemsbefore;
 562             try
 563               {
 564                 if (__elemsbefore >= difference_type(__n))
 565                   {
 566                     iterator __start_n = (this->_M_impl._M_start
 567                                           + difference_type(__n));
 568                     std::__uninitialized_copy_a(this->_M_impl._M_start,
 569                                                 __start_n, __new_start,
 570                                                 _M_get_Tp_allocator());
 571                     this->_M_impl._M_start = __new_start;
 572                     std::copy(__start_n, __pos, __old_start);
 573                     std::copy(__first, __last, __pos - difference_type(__n));
 574                   }
 575                 else
 576                   {
 577                     _ForwardIterator __mid = __first;
 578                     std::advance(__mid, difference_type(__n) - __elemsbefore);
 579                     std::__uninitialized_copy_copy(this->_M_impl._M_start,
 580                                                    __pos, __first, __mid,
 581                                                    __new_start,
 582                                                    _M_get_Tp_allocator());
 583                     this->_M_impl._M_start = __new_start;
 584                     std::copy(__mid, __last, __old_start);
 585                   }
 586               }
 587             catch(...)
 588               {
 589                 _M_destroy_nodes(__new_start._M_node,
 590                                  this->_M_impl._M_start._M_node);
 591                 __throw_exception_again;
 592               }
 593           }
 594         else
 595         {
 596           iterator __new_finish = _M_reserve_elements_at_back(__n);
 597           iterator __old_finish = this->_M_impl._M_finish;
 598           const difference_type __elemsafter =
 599             difference_type(__length) - __elemsbefore;
 600           __pos = this->_M_impl._M_finish - __elemsafter;
 601           try
 602             {
 603               if (__elemsafter > difference_type(__n))
 604                 {
 605                   iterator __finish_n = (this->_M_impl._M_finish
 606                                          - difference_type(__n));
 607                   std::__uninitialized_copy_a(__finish_n,
 608                                               this->_M_impl._M_finish,
 609                                               this->_M_impl._M_finish,
 610                                               _M_get_Tp_allocator());
 611                   this->_M_impl._M_finish = __new_finish;
 612                   std::copy_backward(__pos, __finish_n, __old_finish);
 613                   std::copy(__first, __last, __pos);
 614                 }
 615               else
 616                 {
 617                   _ForwardIterator __mid = __first;
 618                   std::advance(__mid, __elemsafter);
 619                   std::__uninitialized_copy_copy(__mid, __last, __pos,
 620                                                  this->_M_impl._M_finish,
 621                                                  this->_M_impl._M_finish,
 622                                                  _M_get_Tp_allocator());
 623                   this->_M_impl._M_finish = __new_finish;
 624                   std::copy(__first, __mid, __pos);
 625                 }
 626             }
 627           catch(...)
 628             {
 629               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 630                                __new_finish._M_node + 1);
 631               __throw_exception_again;
 632             }
 633         }
 634       }
 635
 636    template<typename _Tp, typename _Alloc>
 637      void
 638      deque<_Tp, _Alloc>::
 639      _M_destroy_data_aux(iterator __first, iterator __last)
 640      {
 641        for (_Map_pointer __node = __first._M_node + 1;
 642             __node < __last._M_node; ++__node)
 643          std::_Destroy(*__node, *__node + _S_buffer_size(),
 644                        _M_get_Tp_allocator());
 645
 646        if (__first._M_node != __last._M_node)
 647          {
 648            std::_Destroy(__first._M_cur, __first._M_last,
 649                          _M_get_Tp_allocator());
 650            std::_Destroy(__last._M_first, __last._M_cur,
 651                          _M_get_Tp_allocator());
 652          }
 653        else
 654          std::_Destroy(__first._M_cur, __last._M_cur,
 655                        _M_get_Tp_allocator());
 656      }
 657
 658   template <typename _Tp, typename _Alloc>
 659     void
 660     deque<_Tp, _Alloc>::
 661     _M_new_elements_at_front(size_type __new_elems)
 662     {
 663       if (this->max_size() - this->size() < __new_elems)
 664         __throw_length_error(__N("deque::_M_new_elements_at_front"));
 665
 666       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
 667                                      / _S_buffer_size());
 668       _M_reserve_map_at_front(__new_nodes);
 669       size_type __i;
 670       try
 671         {
 672           for (__i = 1; __i <= __new_nodes; ++__i)
 673             *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
 674         }
 675       catch(...)
 676         {
 677           for (size_type __j = 1; __j < __i; ++__j)
 678             _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
 679           __throw_exception_again;
 680         }
 681     }
 682
 683   template <typename _Tp, typename _Alloc>
 684     void
 685     deque<_Tp, _Alloc>::
 686     _M_new_elements_at_back(size_type __new_elems)
 687     {
 688       if (this->max_size() - this->size() < __new_elems)
 689         __throw_length_error(__N("deque::_M_new_elements_at_back"));
 690
 691       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
 692                                      / _S_buffer_size());
 693       _M_reserve_map_at_back(__new_nodes);
 694       size_type __i;
 695       try
 696         {
 697           for (__i = 1; __i <= __new_nodes; ++__i)
 698             *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
 699         }
 700       catch(...)
 701         {
 702           for (size_type __j = 1; __j < __i; ++__j)
 703             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
 704           __throw_exception_again;
 705         }
 706     }
 707
 708   template <typename _Tp, typename _Alloc>
 709     void
 710     deque<_Tp, _Alloc>::
 711     _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
 712     {
 713       const size_type __old_num_nodes
 714         = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
 715       const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
 716
 717       _Map_pointer __new_nstart;
 718       if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
 719         {
 720           __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
 721                                          - __new_num_nodes) / 2
 722                          + (__add_at_front ? __nodes_to_add : 0);
 723           if (__new_nstart < this->_M_impl._M_start._M_node)
 724             std::copy(this->_M_impl._M_start._M_node,
 725                       this->_M_impl._M_finish._M_node + 1,
 726                       __new_nstart);
 727           else
 728             std::copy_backward(this->_M_impl._M_start._M_node,
 729                                this->_M_impl._M_finish._M_node + 1,
 730                                __new_nstart + __old_num_nodes);
 731         }
 732       else
 733         {
 734           size_type __new_map_size = this->_M_impl._M_map_size
 735                                      + std::max(this->_M_impl._M_map_size,
 736                                                 __nodes_to_add) + 2;
 737
 738           _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
 739           __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
 740                          + (__add_at_front ? __nodes_to_add : 0);
 741           std::copy(this->_M_impl._M_start._M_node,
 742                     this->_M_impl._M_finish._M_node + 1,
 743                     __new_nstart);
 744           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
 745
 746           this->_M_impl._M_map = __new_map;
 747           this->_M_impl._M_map_size = __new_map_size;
 748         }
 749
 750       this->_M_impl._M_start._M_set_node(__new_nstart);
 751       this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
 752     }
 753
 754   // Overload for deque::iterators, exploiting the "segmented-iterator
 755   // optimization".  NB: leave const_iterators alone!
 756   template<typename _Tp>
 757     void
 758     fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
 759          const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
 760     {
 761       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
 762
 763       for (typename _Self::_Map_pointer __node = __first._M_node + 1;
 764            __node < __last._M_node; ++__node)
 765         std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
 766
 767       if (__first._M_node != __last._M_node)
 768         {
 769           std::fill(__first._M_cur, __first._M_last, __value);
 770           std::fill(__last._M_first, __last._M_cur, __value);
 771         }
 772       else
 773         std::fill(__first._M_cur, __last._M_cur, __value);
 774     }
 775
 776 _GLIBCXX_END_NESTED_NAMESPACE
 777
 778 #endif