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

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