home *** CD-ROM | disk | FTP | other *** search
/ Beginning C++ Through Gam…rogramming (2nd Edition) / BCGP2E.ISO / bloodshed / devcpp-4.9.9.2_setup.exe / vector.tcc < prev    next >
Text File  |  2005-01-29  |  15KB  |  415 lines
  1. // Vector 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) 1996
  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 vector.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 _VECTOR_TCC
  62. #define _VECTOR_TCC 1
  63.  
  64. namespace _GLIBCXX_STD
  65. {
  66.   template<typename _Tp, typename _Alloc>
  67.     void
  68.     vector<_Tp,_Alloc>::
  69.     reserve(size_type __n)
  70.     {
  71.       if (__n > this->max_size())
  72.     __throw_length_error(__N("vector::reserve"));
  73.       if (this->capacity() < __n)
  74.     {
  75.       const size_type __old_size = size();
  76.       pointer __tmp = _M_allocate_and_copy(__n,
  77.                            this->_M_impl._M_start,
  78.                            this->_M_impl._M_finish);
  79.       std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);
  80.       _M_deallocate(this->_M_impl._M_start,
  81.             this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
  82.       this->_M_impl._M_start = __tmp;
  83.       this->_M_impl._M_finish = __tmp + __old_size;
  84.       this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
  85.     }
  86.     }
  87.  
  88.   template<typename _Tp, typename _Alloc>
  89.     typename vector<_Tp,_Alloc>::iterator
  90.     vector<_Tp,_Alloc>::
  91.     insert(iterator __position, const value_type& __x)
  92.     {
  93.       size_type __n = __position - begin();
  94.       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage && __position == end())
  95.       {
  96.         std::_Construct(this->_M_impl._M_finish, __x);
  97.         ++this->_M_impl._M_finish;
  98.       }
  99.       else
  100.         _M_insert_aux(__position, __x);
  101.       return begin() + __n;
  102.     }
  103.  
  104.   template<typename _Tp, typename _Alloc>
  105.     typename vector<_Tp,_Alloc>::iterator
  106.     vector<_Tp,_Alloc>::
  107.     erase(iterator __position)
  108.     {
  109.       if (__position + 1 != end())
  110.         std::copy(__position + 1, end(), __position);
  111.       --this->_M_impl._M_finish;
  112.       std::_Destroy(this->_M_impl._M_finish);
  113.       return __position;
  114.     }
  115.  
  116.   template<typename _Tp, typename _Alloc>
  117.     typename vector<_Tp,_Alloc>::iterator
  118.     vector<_Tp,_Alloc>::
  119.     erase(iterator __first, iterator __last)
  120.     {
  121.       iterator __i(copy(__last, end(), __first));
  122.       std::_Destroy(__i, end());
  123.       this->_M_impl._M_finish = this->_M_impl._M_finish - (__last - __first);
  124.       return __first;
  125.     }
  126.  
  127.   template<typename _Tp, typename _Alloc>
  128.     vector<_Tp,_Alloc>&
  129.     vector<_Tp,_Alloc>::
  130.     operator=(const vector<_Tp,_Alloc>& __x)
  131.     {
  132.       if (&__x != this)
  133.       {
  134.         const size_type __xlen = __x.size();
  135.         if (__xlen > capacity())
  136.         {
  137.           pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
  138.           std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);
  139.           _M_deallocate(this->_M_impl._M_start,
  140.             this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
  141.           this->_M_impl._M_start = __tmp;
  142.           this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
  143.         }
  144.         else if (size() >= __xlen)
  145.         {
  146.           iterator __i(copy(__x.begin(), __x.end(), begin()));
  147.           std::_Destroy(__i, end());
  148.         }
  149.         else
  150.         {
  151.           std::copy(__x.begin(), __x.begin() + size(), this->_M_impl._M_start);
  152.           std::uninitialized_copy(__x.begin() + size(), __x.end(), this->_M_impl._M_finish);
  153.         }
  154.         this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
  155.       }
  156.       return *this;
  157.     }
  158.  
  159.   template<typename _Tp, typename _Alloc>
  160.     void
  161.     vector<_Tp,_Alloc>::
  162.     _M_fill_assign(size_t __n, const value_type& __val)
  163.     {
  164.       if (__n > capacity())
  165.       {
  166.         vector __tmp(__n, __val, get_allocator());
  167.         __tmp.swap(*this);
  168.       }
  169.       else if (__n > size())
  170.       {
  171.         std::fill(begin(), end(), __val);
  172.         this->_M_impl._M_finish
  173.       = std::uninitialized_fill_n(this->_M_impl._M_finish, __n - size(), __val);
  174.       }
  175.       else
  176.         erase(fill_n(begin(), __n, __val), end());
  177.     }
  178.  
  179.   template<typename _Tp, typename _Alloc> template<typename _InputIterator>
  180.     void
  181.     vector<_Tp,_Alloc>::
  182.     _M_assign_aux(_InputIterator __first, _InputIterator __last, input_iterator_tag)
  183.     {
  184.       iterator __cur(begin());
  185.       for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
  186.         *__cur = *__first;
  187.       if (__first == __last)
  188.         erase(__cur, end());
  189.       else
  190.         insert(end(), __first, __last);
  191.     }
  192.  
  193.   template<typename _Tp, typename _Alloc> template<typename _ForwardIterator>
  194.     void
  195.     vector<_Tp,_Alloc>::
  196.     _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
  197.                   forward_iterator_tag)
  198.     {
  199.       size_type __len = std::distance(__first, __last);
  200.  
  201.       if (__len > capacity())
  202.       {
  203.         pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
  204.         std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);
  205.         _M_deallocate(this->_M_impl._M_start,
  206.               this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
  207.         this->_M_impl._M_start = __tmp;
  208.         this->_M_impl._M_end_of_storage = this->_M_impl._M_finish = this->_M_impl._M_start + __len;
  209.       }
  210.       else if (size() >= __len)
  211.       {
  212.         iterator __new_finish(copy(__first, __last, this->_M_impl._M_start));
  213.         std::_Destroy(__new_finish, end());
  214.         this->_M_impl._M_finish = __new_finish.base();
  215.       }
  216.       else
  217.       {
  218.         _ForwardIterator __mid = __first;
  219.         std::advance(__mid, size());
  220.         std::copy(__first, __mid, this->_M_impl._M_start);
  221.         this->_M_impl._M_finish = std::uninitialized_copy(__mid, __last, this->_M_impl._M_finish);
  222.       }
  223.     }
  224.  
  225.   template<typename _Tp, typename _Alloc>
  226.     void
  227.     vector<_Tp,_Alloc>::
  228.     _M_insert_aux(iterator __position, const _Tp& __x)
  229.     {
  230.       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
  231.       {
  232.         std::_Construct(this->_M_impl._M_finish, *(this->_M_impl._M_finish - 1));
  233.         ++this->_M_impl._M_finish;
  234.         _Tp __x_copy = __x;
  235.         std::copy_backward(__position,
  236.                iterator(this->_M_impl._M_finish-2),
  237.                iterator(this->_M_impl._M_finish-1));
  238.         *__position = __x_copy;
  239.       }
  240.       else
  241.       {
  242.         const size_type __old_size = size();
  243.         const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
  244.         iterator __new_start(this->_M_allocate(__len));
  245.         iterator __new_finish(__new_start);
  246.         try
  247.           {
  248.             __new_finish = std::uninitialized_copy(iterator(this->_M_impl._M_start),
  249.                            __position,
  250.                            __new_start);
  251.             std::_Construct(__new_finish.base(), __x);
  252.             ++__new_finish;
  253.             __new_finish = std::uninitialized_copy(__position,
  254.                            iterator(this->_M_impl._M_finish),
  255.                            __new_finish);
  256.           }
  257.         catch(...)
  258.           {
  259.             std::_Destroy(__new_start,__new_finish);
  260.             _M_deallocate(__new_start.base(),__len);
  261.             __throw_exception_again;
  262.           }
  263.         std::_Destroy(begin(), end());
  264.         _M_deallocate(this->_M_impl._M_start,
  265.               this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
  266.         this->_M_impl._M_start = __new_start.base();
  267.         this->_M_impl._M_finish = __new_finish.base();
  268.         this->_M_impl._M_end_of_storage = __new_start.base() + __len;
  269.       }
  270.     }
  271.  
  272.   template<typename _Tp, typename _Alloc>
  273.     void
  274.     vector<_Tp,_Alloc>::
  275.     _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
  276.     {
  277.       if (__n != 0)
  278.       {
  279.         if (size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_finish) >= __n)
  280.       {
  281.            value_type __x_copy = __x;
  282.        const size_type __elems_after = end() - __position;
  283.        iterator __old_finish(this->_M_impl._M_finish);
  284.        if (__elems_after > __n)
  285.          {
  286.            std::uninitialized_copy(this->_M_impl._M_finish - __n,
  287.                        this->_M_impl._M_finish,
  288.                        this->_M_impl._M_finish);
  289.            this->_M_impl._M_finish += __n;
  290.            std::copy_backward(__position, __old_finish - __n, __old_finish);
  291.            std::fill(__position, __position + __n, __x_copy);
  292.          }
  293.        else
  294.          {
  295.            std::uninitialized_fill_n(this->_M_impl._M_finish,
  296.                      __n - __elems_after,
  297.                      __x_copy);
  298.            this->_M_impl._M_finish += __n - __elems_after;
  299.            std::uninitialized_copy(__position, __old_finish, this->_M_impl._M_finish);
  300.            this->_M_impl._M_finish += __elems_after;
  301.            std::fill(__position, __old_finish, __x_copy);
  302.          }
  303.       }
  304.         else
  305.       {
  306.         const size_type __old_size = size();
  307.         const size_type __len = __old_size + std::max(__old_size, __n);
  308.         iterator __new_start(this->_M_allocate(__len));
  309.         iterator __new_finish(__new_start);
  310.         try
  311.           {
  312.         __new_finish = std::uninitialized_copy(begin(), __position,
  313.                                __new_start);
  314.         __new_finish = std::uninitialized_fill_n(__new_finish, __n, __x);
  315.         __new_finish = std::uninitialized_copy(__position, end(),
  316.                                __new_finish);
  317.           }
  318.         catch(...)
  319.           {
  320.         std::_Destroy(__new_start,__new_finish);
  321.         _M_deallocate(__new_start.base(),__len);
  322.         __throw_exception_again;
  323.           }
  324.         std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);
  325.         _M_deallocate(this->_M_impl._M_start,
  326.               this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
  327.         this->_M_impl._M_start = __new_start.base();
  328.         this->_M_impl._M_finish = __new_finish.base();
  329.         this->_M_impl._M_end_of_storage = __new_start.base() + __len;
  330.       }
  331.       }
  332.     }
  333.  
  334.   template<typename _Tp, typename _Alloc> template<typename _InputIterator>
  335.     void
  336.     vector<_Tp,_Alloc>::
  337.     _M_range_insert(iterator __pos,
  338.                     _InputIterator __first, _InputIterator __last,
  339.                     input_iterator_tag)
  340.     {
  341.       for ( ; __first != __last; ++__first)
  342.       {
  343.         __pos = insert(__pos, *__first);
  344.         ++__pos;
  345.       }
  346.     }
  347.  
  348.   template<typename _Tp, typename _Alloc> template<typename _ForwardIterator>
  349.     void
  350.     vector<_Tp,_Alloc>::
  351.     _M_range_insert(iterator __position,_ForwardIterator __first,
  352.             _ForwardIterator __last, forward_iterator_tag)
  353.     {
  354.       if (__first != __last)
  355.       {
  356.         size_type __n = std::distance(__first, __last);
  357.         if (size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_finish) >= __n)
  358.         {
  359.           const size_type __elems_after = end() - __position;
  360.           iterator __old_finish(this->_M_impl._M_finish);
  361.           if (__elems_after > __n)
  362.           {
  363.             std::uninitialized_copy(this->_M_impl._M_finish - __n,
  364.                     this->_M_impl._M_finish,
  365.                     this->_M_impl._M_finish);
  366.             this->_M_impl._M_finish += __n;
  367.             std::copy_backward(__position, __old_finish - __n, __old_finish);
  368.             std::copy(__first, __last, __position);
  369.           }
  370.           else
  371.           {
  372.             _ForwardIterator __mid = __first;
  373.             std::advance(__mid, __elems_after);
  374.             std::uninitialized_copy(__mid, __last, this->_M_impl._M_finish);
  375.             this->_M_impl._M_finish += __n - __elems_after;
  376.             std::uninitialized_copy(__position, __old_finish, this->_M_impl._M_finish);
  377.             this->_M_impl._M_finish += __elems_after;
  378.             std::copy(__first, __mid, __position);
  379.           }
  380.         }
  381.         else
  382.         {
  383.           const size_type __old_size = size();
  384.           const size_type __len = __old_size + std::max(__old_size, __n);
  385.           iterator __new_start(this->_M_allocate(__len));
  386.           iterator __new_finish(__new_start);
  387.           try
  388.             {
  389.               __new_finish = std::uninitialized_copy(iterator(this->_M_impl._M_start),
  390.                              __position, __new_start);
  391.               __new_finish = std::uninitialized_copy(__first, __last,
  392.                              __new_finish);
  393.               __new_finish = std::uninitialized_copy(__position,
  394.                              iterator(this->_M_impl._M_finish),
  395.                              __new_finish);
  396.             }
  397.           catch(...)
  398.             {
  399.               std::_Destroy(__new_start,__new_finish);
  400.               _M_deallocate(__new_start.base(), __len);
  401.               __throw_exception_again;
  402.             }
  403.           std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);
  404.           _M_deallocate(this->_M_impl._M_start,
  405.             this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
  406.           this->_M_impl._M_start = __new_start.base();
  407.           this->_M_impl._M_finish = __new_finish.base();
  408.           this->_M_impl._M_end_of_storage = __new_start.base() + __len;
  409.         }
  410.       }
  411.     }
  412. } // namespace std
  413.  
  414. #endif /* _VECTOR_TCC */
  415.