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                             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                       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(), __value,
 272                                         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,
 276                                       this->get_allocator());
 277         }
 278       catch(...)
 279         {
 280           std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
 281                         this->get_allocator());
 282           __throw_exception_again;
 283         }
 284     }
 285
 286   template <typename _Tp, typename _Alloc>
 287     template <typename _InputIterator>
 288       void
 289       deque<_Tp, _Alloc>::
 290       _M_range_initialize(_InputIterator __first, _InputIterator __last,
 291                           input_iterator_tag)
 292       {
 293         this->_M_initialize_map(0);
 294         try
 295           {
 296             for (; __first != __last; ++__first)
 297               push_back(*__first);
 298           }
 299         catch(...)
 300           {
 301             clear();
 302             __throw_exception_again;
 303           }
 304       }
 305
 306   template <typename _Tp, typename _Alloc>
 307     template <typename _ForwardIterator>
 308       void
 309       deque<_Tp, _Alloc>::
 310       _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
 311                           forward_iterator_tag)
 312       {
 313         const size_type __n = std::distance(__first, __last);
 314         this->_M_initialize_map(__n);
 315
 316         _Map_pointer __cur_node;
 317         try
 318           {
 319             for (__cur_node = this->_M_impl._M_start._M_node;
 320                  __cur_node < this->_M_impl._M_finish._M_node;
 321                  ++__cur_node)
 322             {
 323               _ForwardIterator __mid = __first;
 324               std::advance(__mid, _S_buffer_size());
 325               std::__uninitialized_copy_a(__first, __mid, *__cur_node,
 326                                           this->get_allocator());
 327               __first = __mid;
 328             }
 329             std::__uninitialized_copy_a(__first, __last,
 330                                         this->_M_impl._M_finish._M_first,
 331                                         this->get_allocator());
 332           }
 333         catch(...)
 334           {
 335             std::_Destroy(this->_M_impl._M_start,
 336                           iterator(*__cur_node, __cur_node),
 337                           this->get_allocator());
 338             __throw_exception_again;
 339           }
 340       }
 341
 342   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
 343   template <typename _Tp, typename _Alloc>
 344     void
 345     deque<_Tp, _Alloc>::
 346     _M_push_back_aux(const value_type& __t)
 347     {
 348       value_type __t_copy = __t;
 349       _M_reserve_map_at_back();
 350       *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
 351       try
 352         {
 353           this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t_copy);
 354           this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
 355                                               + 1);
 356           this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
 357         }
 358       catch(...)
 359         {
 360           _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
 361           __throw_exception_again;
 362         }
 363     }
 364
 365   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
 366   template <typename _Tp, typename _Alloc>
 367     void
 368     deque<_Tp, _Alloc>::
 369     _M_push_front_aux(const value_type& __t)
 370     {
 371       value_type __t_copy = __t;
 372       _M_reserve_map_at_front();
 373       *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
 374       try
 375         {
 376           this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
 377                                              - 1);
 378           this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
 379           this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t_copy);
 380         }
 381       catch(...)
 382         {
 383           ++this->_M_impl._M_start;
 384           _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
 385           __throw_exception_again;
 386         }
 387     }
 388
 389   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
 390   template <typename _Tp, typename _Alloc>
 391     void deque<_Tp, _Alloc>::
 392     _M_pop_back_aux()
 393     {
 394       _M_deallocate_node(this->_M_impl._M_finish._M_first);
 395       this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
 396       this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
 397       this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
 398     }
 399
 400   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
 401   // Note that if the deque has at least one element (a precondition for this
 402   // member function), and if
 403   //   _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
 404   // then the deque must have at least two nodes.
 405   template <typename _Tp, typename _Alloc>
 406     void deque<_Tp, _Alloc>::
 407     _M_pop_front_aux()
 408     {
 409       this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
 410       _M_deallocate_node(this->_M_impl._M_start._M_first);
 411       this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
 412       this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
 413     }
 414
 415   template <typename _Tp, typename _Alloc>
 416     template <typename _InputIterator>
 417       void
 418       deque<_Tp, _Alloc>::
 419       _M_range_insert_aux(iterator __pos,
 420                           _InputIterator __first, _InputIterator __last,
 421                           input_iterator_tag)
 422       { std::copy(__first, __last, std::inserter(*this, __pos)); }
 423
 424   template <typename _Tp, typename _Alloc>
 425     template <typename _ForwardIterator>
 426       void
 427       deque<_Tp, _Alloc>::
 428       _M_range_insert_aux(iterator __pos,
 429                           _ForwardIterator __first, _ForwardIterator __last,
 430                           forward_iterator_tag)
 431       {
 432         const size_type __n = std::distance(__first, __last);
 433         if (__pos._M_cur == this->_M_impl._M_start._M_cur)
 434           {
 435             iterator __new_start = _M_reserve_elements_at_front(__n);
 436             try
 437               {
 438                 std::__uninitialized_copy_a(__first, __last, __new_start,
 439                                             this->get_allocator());
 440                 this->_M_impl._M_start = __new_start;
 441               }
 442             catch(...)
 443               {
 444                 _M_destroy_nodes(__new_start._M_node,
 445                                  this->_M_impl._M_start._M_node);
 446                 __throw_exception_again;
 447               }
 448           }
 449         else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
 450           {
 451             iterator __new_finish = _M_reserve_elements_at_back(__n);
 452             try
 453               {
 454                 std::__uninitialized_copy_a(__first, __last,
 455                                             this->_M_impl._M_finish,
 456                                             this->get_allocator());
 457                 this->_M_impl._M_finish = __new_finish;
 458               }
 459             catch(...)
 460               {
 461                 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 462                                  __new_finish._M_node + 1);
 463                 __throw_exception_again;
 464               }
 465           }
 466         else
 467           _M_insert_aux(__pos, __first, __last, __n);
 468       }
 469
 470   template <typename _Tp, typename _Alloc>
 471     typename deque<_Tp, _Alloc>::iterator
 472     deque<_Tp, _Alloc>::
 473     _M_insert_aux(iterator __pos, const value_type& __x)
 474     {
 475       difference_type __index = __pos - this->_M_impl._M_start;
 476       value_type __x_copy = __x; // XXX copy
 477       if (static_cast<size_type>(__index) < size() / 2)
 478         {
 479           push_front(front());
 480           iterator __front1 = this->_M_impl._M_start;
 481           ++__front1;
 482           iterator __front2 = __front1;
 483           ++__front2;
 484           __pos = this->_M_impl._M_start + __index;
 485           iterator __pos1 = __pos;
 486           ++__pos1;
 487           std::copy(__front2, __pos1, __front1);
 488         }
 489       else
 490         {
 491           push_back(back());
 492           iterator __back1 = this->_M_impl._M_finish;
 493           --__back1;
 494           iterator __back2 = __back1;
 495           --__back2;
 496           __pos = this->_M_impl._M_start + __index;
 497           std::copy_backward(__pos, __back2, __back1);
 498         }
 499       *__pos = __x_copy;
 500       return __pos;
 501     }
 502
 503   template <typename _Tp, typename _Alloc>
 504     void
 505     deque<_Tp, _Alloc>::
 506     _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
 507     {
 508       const difference_type __elems_before = __pos - this->_M_impl._M_start;
 509       const size_type __length = this->size();
 510       value_type __x_copy = __x;
 511       if (__elems_before < difference_type(__length / 2))
 512         {
 513           iterator __new_start = _M_reserve_elements_at_front(__n);
 514           iterator __old_start = this->_M_impl._M_start;
 515           __pos = this->_M_impl._M_start + __elems_before;
 516           try
 517             {
 518               if (__elems_before >= difference_type(__n))
 519                 {
 520                   iterator __start_n = (this->_M_impl._M_start
 521                                         + difference_type(__n));
 522                   std::__uninitialized_copy_a(this->_M_impl._M_start, __start_n,
 523                                               __new_start,
 524                                               this->get_allocator());
 525                   this->_M_impl._M_start = __new_start;
 526                   std::copy(__start_n, __pos, __old_start);
 527                   fill(__pos - difference_type(__n), __pos, __x_copy);
 528                 }
 529               else
 530                 {
 531                   std::__uninitialized_copy_fill(this->_M_impl._M_start,
 532                                                  __pos, __new_start,
 533                                                  this->_M_impl._M_start,
 534                                                  __x_copy,
 535                                                  this->get_allocator());
 536                   this->_M_impl._M_start = __new_start;
 537                   std::fill(__old_start, __pos, __x_copy);
 538                 }
 539             }
 540           catch(...)
 541             {
 542               _M_destroy_nodes(__new_start._M_node,
 543                                this->_M_impl._M_start._M_node);
 544               __throw_exception_again;
 545             }
 546         }
 547       else
 548         {
 549           iterator __new_finish = _M_reserve_elements_at_back(__n);
 550           iterator __old_finish = this->_M_impl._M_finish;
 551           const difference_type __elems_after =
 552             difference_type(__length) - __elems_before;
 553           __pos = this->_M_impl._M_finish - __elems_after;
 554           try
 555             {
 556               if (__elems_after > difference_type(__n))
 557                 {
 558                   iterator __finish_n = (this->_M_impl._M_finish
 559                                          - difference_type(__n));
 560                   std::__uninitialized_copy_a(__finish_n, 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, __start_n,
 609                                                 __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