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

   1 // Deque implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005 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 2, 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 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  *
  32  * Copyright (c) 1994
  33  * Hewlett-Packard Company
  34  *
  35  * Permission to use, copy, modify, distribute and sell this software
  36  * and its documentation for any purpose is hereby granted without fee,
  37  * provided that the above copyright notice appear in all copies and
  38  * that both that copyright notice and this permission notice appear
  39  * in supporting documentation.  Hewlett-Packard Company makes no
  40  * representations about the suitability of this software for any
  41  * purpose.  It is provided "as is" without express or implied warranty.
  42  *
  43  *
  44  * Copyright (c) 1997
  45  * Silicon Graphics Computer Systems, Inc.
  46  *
  47  * Permission to use, copy, modify, distribute and sell this software
  48  * and its documentation for any purpose is hereby granted without fee,
  49  * provided that the above copyright notice appear in all copies and
  50  * that both that copyright notice and this permission notice appear
  51  * in supporting documentation.  Silicon Graphics makes no
  52  * representations about the suitability of this software for any
  53  * purpose.  It is provided "as is" without express or implied warranty.
  54  */
  55
  56 /** @file deque.tcc
  57  *  This is an internal header file, included by other library headers.
  58  *  You should not attempt to use it directly.
  59  */
  60
  61 #ifndef _DEQUE_TCC
  62 #define _DEQUE_TCC 1
  63
  64 namespace _GLIBCXX_STD
  65 {
  66   template <typename _Tp, typename _Alloc>
  67     deque<_Tp, _Alloc>&
  68     deque<_Tp, _Alloc>::
  69     operator=(const deque& __x)
  70     {
  71       const size_type __len = size();
  72       if (&__x != this)
  73         {
  74           if (__len >= __x.size())
  75             _M_erase_at_end(std::copy(__x.begin(), __x.end(),
  76                                       this->_M_impl._M_start));
  77           else
  78             {
  79               const_iterator __mid = __x.begin() + difference_type(__len);
  80               std::copy(__x.begin(), __mid, this->_M_impl._M_start);
  81               insert(this->_M_impl._M_finish, __mid, __x.end());
  82             }
  83         }
  84       return *this;
  85     }
  86
  87   template <typename _Tp, typename _Alloc>
  88     typename deque<_Tp, _Alloc>::iterator
  89     deque<_Tp, _Alloc>::
  90     insert(iterator position, const value_type& __x)
  91     {
  92       if (position._M_cur == this->_M_impl._M_start._M_cur)
  93         {
  94           push_front(__x);
  95           return this->_M_impl._M_start;
  96         }
  97       else if (position._M_cur == this->_M_impl._M_finish._M_cur)
  98         {
  99           push_back(__x);
 100           iterator __tmp = this->_M_impl._M_finish;
 101           --__tmp;
 102           return __tmp;
 103         }
 104       else
 105         return _M_insert_aux(position, __x);
 106     }
 107
 108   template <typename _Tp, typename _Alloc>
 109     typename deque<_Tp, _Alloc>::iterator
 110     deque<_Tp, _Alloc>::
 111     erase(iterator __position)
 112     {
 113       iterator __next = __position;
 114       ++__next;
 115       const size_type __index = __position - begin();
 116       if (__index < (size() >> 1))
 117         {
 118           if (__position != begin())
 119             std::copy_backward(begin(), __position, __next);
 120           pop_front();
 121         }
 122       else
 123         {
 124           if (__next != end())
 125             std::copy(__next, end(), __position);
 126           pop_back();
 127         }
 128       return begin() + __index;
 129     }
 130
 131   template <typename _Tp, typename _Alloc>
 132     typename deque<_Tp, _Alloc>::iterator
 133     deque<_Tp, _Alloc>::
 134     erase(iterator __first, iterator __last)
 135     {
 136       if (__first == begin() && __last == end())
 137         {
 138           clear();
 139           return end();
 140         }
 141       else
 142         {
 143           const difference_type __n = __last - __first;
 144           const difference_type __elems_before = __first - begin();
 145           if (static_cast<size_type>(__elems_before) < (size() - __n) / 2)
 146             {
 147               if (__first != begin())
 148                 std::copy_backward(begin(), __first, __last);
 149               _M_erase_at_begin(begin() + __n);
 150             }
 151           else
 152             {
 153               if (__last != end())
 154                 std::copy(__last, end(), __first);
 155               _M_erase_at_end(end() - __n);
 156             }
 157           return begin() + __elems_before;
 158         }
 159     }
 160
 161   template <typename _Tp, class _Alloc>
 162     template <typename _InputIterator>
 163       void
 164       deque<_Tp, _Alloc>::
 165       _M_assign_aux(_InputIterator __first, _InputIterator __last,
 166                     std::input_iterator_tag)
 167       {
 168         iterator __cur = begin();
 169         for (; __first != __last && __cur != end(); ++__cur, ++__first)
 170           *__cur = *__first;
 171         if (__first == __last)
 172           _M_erase_at_end(__cur);
 173         else
 174           insert(end(), __first, __last);
 175       }
 176
 177   template <typename _Tp, typename _Alloc>
 178     void
 179     deque<_Tp, _Alloc>::
 180     _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
 181     {
 182       if (__pos._M_cur == this->_M_impl._M_start._M_cur)
 183         {
 184           iterator __new_start = _M_reserve_elements_at_front(__n);
 185           try
 186             {
 187               std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
 188                                           __x,
 189                                           _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                   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       const size_type __new_nodes
 664         = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
 665       _M_reserve_map_at_front(__new_nodes);
 666       size_type __i;
 667       try
 668         {
 669           for (__i = 1; __i <= __new_nodes; ++__i)
 670             *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
 671         }
 672       catch(...)
 673         {
 674           for (size_type __j = 1; __j < __i; ++__j)
 675             _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
 676           __throw_exception_again;
 677         }
 678     }
 679
 680   template <typename _Tp, typename _Alloc>
 681     void
 682     deque<_Tp, _Alloc>::
 683     _M_new_elements_at_back(size_type __new_elems)
 684     {
 685       const size_type __new_nodes
 686         = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
 687       _M_reserve_map_at_back(__new_nodes);
 688       size_type __i;
 689       try
 690         {
 691           for (__i = 1; __i <= __new_nodes; ++__i)
 692             *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
 693         }
 694       catch(...)
 695         {
 696           for (size_type __j = 1; __j < __i; ++__j)
 697             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
 698           __throw_exception_again;
 699         }
 700     }
 701
 702   template <typename _Tp, typename _Alloc>
 703     void
 704     deque<_Tp, _Alloc>::
 705     _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
 706     {
 707       const size_type __old_num_nodes
 708         = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
 709       const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
 710
 711       _Map_pointer __new_nstart;
 712       if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
 713         {
 714           __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
 715                                          - __new_num_nodes) / 2
 716                          + (__add_at_front ? __nodes_to_add : 0);
 717           if (__new_nstart < this->_M_impl._M_start._M_node)
 718             std::copy(this->_M_impl._M_start._M_node,
 719                     this->_M_impl._M_finish._M_node + 1,
 720                     __new_nstart);
 721           else
 722             std::copy_backward(this->_M_impl._M_start._M_node,
 723                                this->_M_impl._M_finish._M_node + 1,
 724                                __new_nstart + __old_num_nodes);
 725         }
 726       else
 727         {
 728           size_type __new_map_size = this->_M_impl._M_map_size
 729                                      + std::max(this->_M_impl._M_map_size,
 730                                                 __nodes_to_add) + 2;
 731
 732           _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
 733           __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
 734                          + (__add_at_front ? __nodes_to_add : 0);
 735           std::copy(this->_M_impl._M_start._M_node,
 736                     this->_M_impl._M_finish._M_node + 1,
 737                     __new_nstart);
 738           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
 739
 740           this->_M_impl._M_map = __new_map;
 741           this->_M_impl._M_map_size = __new_map_size;
 742         }
 743
 744       this->_M_impl._M_start._M_set_node(__new_nstart);
 745       this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
 746     }
 747 } // namespace std
 748
 749 #endif