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