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