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

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