[thirdparty/gcc.git] / libstdc++-v3 / include / bits / vector.tcc

// Vector implementation (out of line) -*- C++ -*-

// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this  software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

/** @file vector.tcc
 *  This is an internal header file, included by other library headers.
 *  You should not attempt to use it directly.
 */

#ifndef _VECTOR_TCC
#define _VECTOR_TCC 1

_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)

  template<typename _Tp, typename _Alloc>
    void
    vector<_Tp, _Alloc>::
    reserve(size_type __n)
    {
      if (__n > this->max_size())
	__throw_length_error(__N("vector::reserve"));
      if (this->capacity() < __n)
	{
	  const size_type __old_size = size();
	  pointer __tmp = _M_allocate_and_copy(__n, this->_M_impl._M_start,
					       this->_M_impl._M_finish);
	  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
			_M_get_Tp_allocator());
	  _M_deallocate(this->_M_impl._M_start,
			this->_M_impl._M_end_of_storage
			- this->_M_impl._M_start);
	  this->_M_impl._M_start = __tmp;
	  this->_M_impl._M_finish = __tmp + __old_size;
	  this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
	}
    }

  template<typename _Tp, typename _Alloc>
    typename vector<_Tp, _Alloc>::iterator
    vector<_Tp, _Alloc>::
    insert(iterator __position, const value_type& __x)
    {
      const size_type __n = __position - begin();
      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
	  && __position == end())
	{
	  this->_M_impl.construct(this->_M_impl._M_finish, __x);
	  ++this->_M_impl._M_finish;
	}
      else
        _M_insert_aux(__position, __x);
      return iterator(this->_M_impl._M_start + __n);
    }

  template<typename _Tp, typename _Alloc>
    typename vector<_Tp, _Alloc>::iterator
    vector<_Tp, _Alloc>::
    erase(iterator __position)
    {
      if (__position + 1 != end())
        std::copy(__position + 1, end(), __position);
      --this->_M_impl._M_finish;
      this->_M_impl.destroy(this->_M_impl._M_finish);
      return __position;
    }

  template<typename _Tp, typename _Alloc>
    typename vector<_Tp, _Alloc>::iterator
    vector<_Tp, _Alloc>::
    erase(iterator __first, iterator __last)
    {
      if (__last != end())
	std::copy(__last, end(), __first);
      _M_erase_at_end(__first.base() + (end() - __last));
      return __first;
    }

  template<typename _Tp, typename _Alloc>
    vector<_Tp, _Alloc>&
    vector<_Tp, _Alloc>::
    operator=(const vector<_Tp, _Alloc>& __x)
    {
      if (&__x != this)
	{
	  const size_type __xlen = __x.size();
	  if (__xlen > capacity())
	    {
	      pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
						   __x.end());
	      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
			    _M_get_Tp_allocator());
	      _M_deallocate(this->_M_impl._M_start,
			    this->_M_impl._M_end_of_storage
			    - this->_M_impl._M_start);
	      this->_M_impl._M_start = __tmp;
	      this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
	    }
	  else if (size() >= __xlen)
	    {
	      std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
			    end(), _M_get_Tp_allocator());
	    }
	  else
	    {
	      std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
			this->_M_impl._M_start);
	      std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
					  __x._M_impl._M_finish,
					  this->_M_impl._M_finish,
					  _M_get_Tp_allocator());
	    }
	  this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
	}
      return *this;
    }

  template<typename _Tp, typename _Alloc>
    void
    vector<_Tp, _Alloc>::
    _M_fill_assign(size_t __n, const value_type& __val)
    {
      if (__n > capacity())
	{
	  vector __tmp(__n, __val, _M_get_Tp_allocator());
	  __tmp.swap(*this);
	}
      else if (__n > size())
	{
	  std::fill(begin(), end(), __val);
	  std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
					__n - size(), __val,
					_M_get_Tp_allocator());
	  this->_M_impl._M_finish += __n - size();
	}
      else
        _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
    }

  template<typename _Tp, typename _Alloc>
    template<typename _InputIterator>
      void
      vector<_Tp, _Alloc>::
      _M_assign_aux(_InputIterator __first, _InputIterator __last,
		    std::input_iterator_tag)
      {
	pointer __cur(this->_M_impl._M_start);
	for (; __first != __last && __cur != this->_M_impl._M_finish;
	     ++__cur, ++__first)
	  *__cur = *__first;
	if (__first == __last)
	  _M_erase_at_end(__cur);
	else
	  insert(end(), __first, __last);
      }

  template<typename _Tp, typename _Alloc>
    template<typename _ForwardIterator>
      void
      vector<_Tp, _Alloc>::
      _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
		    std::forward_iterator_tag)
      {
	const size_type __len = std::distance(__first, __last);

	if (__len > capacity())
	  {
	    pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
	    std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
			  _M_get_Tp_allocator());
	    _M_deallocate(this->_M_impl._M_start,
			  this->_M_impl._M_end_of_storage
			  - this->_M_impl._M_start);
	    this->_M_impl._M_start = __tmp;
	    this->_M_impl._M_finish = this->_M_impl._M_start + __len;
	    this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
	  }
	else if (size() >= __len)
	  _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
	else
	  {
	    _ForwardIterator __mid = __first;
	    std::advance(__mid, size());
	    std::copy(__first, __mid, this->_M_impl._M_start);
	    this->_M_impl._M_finish =
	      std::__uninitialized_copy_a(__mid, __last,
					  this->_M_impl._M_finish,
					  _M_get_Tp_allocator());
	  }
      }

  template<typename _Tp, typename _Alloc>
    void
    vector<_Tp, _Alloc>::
    _M_insert_aux(iterator __position, const _Tp& __x)
    {
      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
	{
	  this->_M_impl.construct(this->_M_impl._M_finish,
				  *(this->_M_impl._M_finish - 1));
	  ++this->_M_impl._M_finish;
	  _Tp __x_copy = __x;
	  std::copy_backward(__position.base(),
			     this->_M_impl._M_finish - 2,
			     this->_M_impl._M_finish - 1);
	  *__position = __x_copy;
	}
      else
	{
	  const size_type __len =
	    _M_check_len(size_type(1), "vector::_M_insert_aux");
	  pointer __new_start(this->_M_allocate(__len));
	  pointer __new_finish(__new_start);
	  try
	    {
	      __new_finish =
		std::__uninitialized_copy_a(this->_M_impl._M_start,
					    __position.base(), __new_start,
					    _M_get_Tp_allocator());
	      this->_M_impl.construct(__new_finish, __x);
	      ++__new_finish;
	      __new_finish =
		std::__uninitialized_copy_a(__position.base(),
					    this->_M_impl._M_finish,
					    __new_finish,
					    _M_get_Tp_allocator());
	    }
	  catch(...)
	    {
	      std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
	      _M_deallocate(__new_start, __len);
	      __throw_exception_again;
	    }
	  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
			_M_get_Tp_allocator());
	  _M_deallocate(this->_M_impl._M_start,
			this->_M_impl._M_end_of_storage
			- this->_M_impl._M_start);
	  this->_M_impl._M_start = __new_start;
	  this->_M_impl._M_finish = __new_finish;
	  this->_M_impl._M_end_of_storage = __new_start + __len;
	}
    }

  template<typename _Tp, typename _Alloc>
    void
    vector<_Tp, _Alloc>::
    _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
    {
      if (__n != 0)
	{
	  if (size_type(this->_M_impl._M_end_of_storage
			- this->_M_impl._M_finish) >= __n)
	    {
	      value_type __x_copy = __x;
	      const size_type __elems_after = end() - __position;
	      pointer __old_finish(this->_M_impl._M_finish);
	      if (__elems_after > __n)
		{
		  std::__uninitialized_copy_a(this->_M_impl._M_finish - __n,
					      this->_M_impl._M_finish,
					      this->_M_impl._M_finish,
					      _M_get_Tp_allocator());
		  this->_M_impl._M_finish += __n;
		  std::copy_backward(__position.base(), __old_finish - __n,
				     __old_finish);
		  std::fill(__position.base(), __position.base() + __n,
			    __x_copy);
		}
	      else
		{
		  std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
						__n - __elems_after,
						__x_copy,
						_M_get_Tp_allocator());
		  this->_M_impl._M_finish += __n - __elems_after;
		  std::__uninitialized_copy_a(__position.base(), __old_finish,
					      this->_M_impl._M_finish,
					      _M_get_Tp_allocator());
		  this->_M_impl._M_finish += __elems_after;
		  std::fill(__position.base(), __old_finish, __x_copy);
		}
	    }
	  else
	    {
	      const size_type __len =
		_M_check_len(__n, "vector::_M_fill_insert");
	      pointer __new_start(this->_M_allocate(__len));
	      pointer __new_finish(__new_start);
	      try
		{
		  __new_finish =
		    std::__uninitialized_copy_a(this->_M_impl._M_start,
						__position.base(),
						__new_start,
						_M_get_Tp_allocator());
		  std::__uninitialized_fill_n_a(__new_finish, __n, __x,
						_M_get_Tp_allocator());
		  __new_finish += __n;
		  __new_finish =
		    std::__uninitialized_copy_a(__position.base(),
						this->_M_impl._M_finish,
						__new_finish,
						_M_get_Tp_allocator());
		}
	      catch(...)
		{
		  std::_Destroy(__new_start, __new_finish,
				_M_get_Tp_allocator());
		  _M_deallocate(__new_start, __len);
		  __throw_exception_again;
		}
	      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
			    _M_get_Tp_allocator());
	      _M_deallocate(this->_M_impl._M_start,
			    this->_M_impl._M_end_of_storage
			    - this->_M_impl._M_start);
	      this->_M_impl._M_start = __new_start;
	      this->_M_impl._M_finish = __new_finish;
	      this->_M_impl._M_end_of_storage = __new_start + __len;
	    }
	}
    }

  template<typename _Tp, typename _Alloc>
    template<typename _InputIterator>
      void
      vector<_Tp, _Alloc>::
      _M_range_insert(iterator __pos, _InputIterator __first,
		      _InputIterator __last, std::input_iterator_tag)
      {
	for (; __first != __last; ++__first)
	  {
	    __pos = insert(__pos, *__first);
	    ++__pos;
	  }
      }

  template<typename _Tp, typename _Alloc>
    template<typename _ForwardIterator>
      void
      vector<_Tp, _Alloc>::
      _M_range_insert(iterator __position, _ForwardIterator __first,
		      _ForwardIterator __last, std::forward_iterator_tag)
      {
	if (__first != __last)
	  {
	    const size_type __n = std::distance(__first, __last);
	    if (size_type(this->_M_impl._M_end_of_storage
			  - this->_M_impl._M_finish) >= __n)
	      {
		const size_type __elems_after = end() - __position;
		pointer __old_finish(this->_M_impl._M_finish);
		if (__elems_after > __n)
		  {
		    std::__uninitialized_copy_a(this->_M_impl._M_finish - __n,
						this->_M_impl._M_finish,
						this->_M_impl._M_finish,
						_M_get_Tp_allocator());
		    this->_M_impl._M_finish += __n;
		    std::copy_backward(__position.base(), __old_finish - __n,
				       __old_finish);
		    std::copy(__first, __last, __position);
		  }
		else
		  {
		    _ForwardIterator __mid = __first;
		    std::advance(__mid, __elems_after);
		    std::__uninitialized_copy_a(__mid, __last,
						this->_M_impl._M_finish,
						_M_get_Tp_allocator());
		    this->_M_impl._M_finish += __n - __elems_after;
		    std::__uninitialized_copy_a(__position.base(),
						__old_finish,
						this->_M_impl._M_finish,
						_M_get_Tp_allocator());
		    this->_M_impl._M_finish += __elems_after;
		    std::copy(__first, __mid, __position);
		  }
	      }
	    else
	      {
		const size_type __len =
		  _M_check_len(__n, "vector::_M_range_insert");
		pointer __new_start(this->_M_allocate(__len));
		pointer __new_finish(__new_start);
		try
		  {
		    __new_finish =
		      std::__uninitialized_copy_a(this->_M_impl._M_start,
						  __position.base(),
						  __new_start,
						  _M_get_Tp_allocator());
		    __new_finish =
		      std::__uninitialized_copy_a(__first, __last, __new_finish,
						  _M_get_Tp_allocator());
		    __new_finish =
		      std::__uninitialized_copy_a(__position.base(),
						  this->_M_impl._M_finish,
						  __new_finish,
						  _M_get_Tp_allocator());
		  }
		catch(...)
		  {
		    std::_Destroy(__new_start, __new_finish,
				  _M_get_Tp_allocator());
		    _M_deallocate(__new_start, __len);
		    __throw_exception_again;
		  }
		std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
			      _M_get_Tp_allocator());
		_M_deallocate(this->_M_impl._M_start,
			      this->_M_impl._M_end_of_storage
			      - this->_M_impl._M_start);
		this->_M_impl._M_start = __new_start;
		this->_M_impl._M_finish = __new_finish;
		this->_M_impl._M_end_of_storage = __new_start + __len;
	      }
	  }
      }


  // vector<bool>

  template<typename _Alloc>
    void
    vector<bool, _Alloc>::
    _M_fill_insert(iterator __position, size_type __n, bool __x)
    {
      if (__n == 0)
	return;
      if (capacity() - size() >= __n)
	{
	  std::copy_backward(__position, end(),
			     this->_M_impl._M_finish + difference_type(__n));
	  std::fill(__position, __position + difference_type(__n), __x);
	  this->_M_impl._M_finish += difference_type(__n);
	}
      else
	{
	  const size_type __len = 
	    _M_check_len(__n, "vector<bool>::_M_fill_insert");
	  _Bit_type * __q = this->_M_allocate(__len);
	  iterator __i = _M_copy_aligned(begin(), __position,
					 iterator(__q, 0));
	  std::fill(__i, __i + difference_type(__n), __x);
	  this->_M_impl._M_finish = std::copy(__position, end(),
					      __i + difference_type(__n));
	  this->_M_deallocate();
	  this->_M_impl._M_end_of_storage = (__q + ((__len
						     + int(_S_word_bit) - 1)
						    / int(_S_word_bit)));
	  this->_M_impl._M_start = iterator(__q, 0);
	}
    }

  template<typename _Alloc>
    template<typename _ForwardIterator>
      void
      vector<bool, _Alloc>::
      _M_insert_range(iterator __position, _ForwardIterator __first, 
		      _ForwardIterator __last, std::forward_iterator_tag)
      {
	if (__first != __last)
	  {
	    size_type __n = std::distance(__first, __last);
	    if (capacity() - size() >= __n)
	      {
		std::copy_backward(__position, end(),
				   this->_M_impl._M_finish
				   + difference_type(__n));
		std::copy(__first, __last, __position);
		this->_M_impl._M_finish += difference_type(__n);
	      }
	    else
	      {
		const size_type __len =
		  _M_check_len(__n, "vector<bool>::_M_insert_range");
		_Bit_type * __q = this->_M_allocate(__len);
		iterator __i = _M_copy_aligned(begin(), __position,
					       iterator(__q, 0));
		__i = std::copy(__first, __last, __i);
		this->_M_impl._M_finish = std::copy(__position, end(), __i);
		this->_M_deallocate();
		this->_M_impl._M_end_of_storage = (__q
						   + ((__len
						       + int(_S_word_bit) - 1)
						      / int(_S_word_bit)));
		this->_M_impl._M_start = iterator(__q, 0);
	      }
	  }
      }

  template<typename _Alloc>
    void
    vector<bool, _Alloc>::
    _M_insert_aux(iterator __position, bool __x)
    {
      if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
	{
	  std::copy_backward(__position, this->_M_impl._M_finish, 
			     this->_M_impl._M_finish + 1);
	  *__position = __x;
	  ++this->_M_impl._M_finish;
	}
      else
	{
	  const size_type __len =
	    _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
	  _Bit_type * __q = this->_M_allocate(__len);
	  iterator __i = _M_copy_aligned(begin(), __position,
					 iterator(__q, 0));
	  *__i++ = __x;
	  this->_M_impl._M_finish = std::copy(__position, end(), __i);
	  this->_M_deallocate();
	  this->_M_impl._M_end_of_storage = (__q + ((__len
						     + int(_S_word_bit) - 1)
						    / int(_S_word_bit)));
	  this->_M_impl._M_start = iterator(__q, 0);
	}
    }

_GLIBCXX_END_NESTED_NAMESPACE

#endif /* _VECTOR_TCC */
Commit	Line	Data
83144cfc PE	1	// Vector implementation (out of line) -- C++ --
83144cfc PE	2
232c4925 PC	3	// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
232c4925 PC	4	// Free Software Foundation, Inc.
83144cfc PE	5	//
	6	// This file is part of the GNU ISO C++ Library. This library is free
	7	// software; you can redistribute it and/or modify it under the
	8	// terms of the GNU General Public License as published by the
	9	// Free Software Foundation; either version 2, or (at your option)
	10	// any later version.
	11
	12	// This library is distributed in the hope that it will be useful,
	13	// but WITHOUT ANY WARRANTY; without even the implied warranty of
	14	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	15	// GNU General Public License for more details.
	16
	17	// You should have received a copy of the GNU General Public License along
	18	// with this library; see the file COPYING. If not, write to the Free
83f51799	19	// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
83144cfc PE	20	// USA.
	21
	22	// As a special exception, you may use this file as part of a free software
	23	// library without restriction. Specifically, if other files instantiate
	24	// templates or use macros or inline functions from this file, or you compile
	25	// this file and link it with other files to produce an executable, this
	26	// file does not by itself cause the resulting executable to be covered by
	27	// the GNU General Public License. This exception does not however
	28	// invalidate any other reasons why the executable file might be covered by
	29	// the GNU General Public License.
	30
	31	/*
	32	*
	33	* Copyright (c) 1994
	34	* Hewlett-Packard Company
	35	*
	36	* Permission to use, copy, modify, distribute and sell this software
	37	* and its documentation for any purpose is hereby granted without fee,
	38	* provided that the above copyright notice appear in all copies and
	39	* that both that copyright notice and this permission notice appear
	40	* in supporting documentation. Hewlett-Packard Company makes no
	41	* representations about the suitability of this software for any
	42	* purpose. It is provided "as is" without express or implied warranty.
	43	*
	44	*
	45	* Copyright (c) 1996
	46	* Silicon Graphics Computer Systems, Inc.
	47	*
	48	* Permission to use, copy, modify, distribute and sell this software
	49	* and its documentation for any purpose is hereby granted without fee,
	50	* provided that the above copyright notice appear in all copies and
	51	* that both that copyright notice and this permission notice appear
	52	* in supporting documentation. Silicon Graphics makes no
	53	* representations about the suitability of this software for any
	54	* purpose. It is provided "as is" without express or implied warranty.
	55	*/
	56
	57	/** @file vector.tcc
	58	* This is an internal header file, included by other library headers.
	59	* You should not attempt to use it directly.
	60	*/
	61
3d7c150e BK	62	#ifndef _VECTOR_TCC
3d7c150e BK	63	#define _VECTOR_TCC 1
83144cfc	64
c2ba9709	65	_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
3cbc7af0	66
af5fb6ab	67	template<typename _Tp, typename _Alloc>
3971a4d2	68	void
874e7baa	69	vector<_Tp, _Alloc>::
3971a4d2	70	reserve(size_type __n)
83144cfc	71	{
48d1c3c5	72	if (__n > this->max_size())
ba9119ec	73	__throw_length_error(__N("vector::reserve"));
48d1c3c5 BK	74	if (this->capacity() < __n)
	75	{
	76	const size_type __old_size = size();
bc9053ab	77	pointer __tmp = _M_allocate_and_copy(__n, this->_M_impl._M_start,
03f9ea44	78	this->_M_impl._M_finish);
1985f1cd	79	std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
4fd20a8f	80	_M_get_Tp_allocator());
03f9ea44	81	_M_deallocate(this->_M_impl._M_start,
874e7baa PC	82	this->_M_impl._M_end_of_storage
874e7baa PC	83	- this->_M_impl._M_start);
03f9ea44 DM	84	this->_M_impl._M_start = __tmp;
	85	this->_M_impl._M_finish = __tmp + __old_size;
	86	this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
48d1c3c5	87	}
3971a4d2	88	}
ed6814f7	89
af5fb6ab	90	template<typename _Tp, typename _Alloc>
874e7baa PC	91	typename vector<_Tp, _Alloc>::iterator
874e7baa PC	92	vector<_Tp, _Alloc>::
3971a4d2 PE	93	insert(iterator __position, const value_type& __x)
3971a4d2 PE	94	{
43da93a7	95	const size_type __n = __position - begin();
874e7baa PC	96	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
	97	&& __position == end())
	98	{
1985f1cd	99	this->_M_impl.construct(this->_M_impl._M_finish, __x);
874e7baa PC	100	++this->_M_impl._M_finish;
874e7baa PC	101	}
83144cfc	102	else
3971a4d2	103	_M_insert_aux(__position, __x);
bc9053ab	104	return iterator(this->_M_impl._M_start + __n);
83144cfc	105	}
ed6814f7	106
af5fb6ab	107	template<typename _Tp, typename _Alloc>
874e7baa PC	108	typename vector<_Tp, _Alloc>::iterator
874e7baa PC	109	vector<_Tp, _Alloc>::
3971a4d2	110	erase(iterator __position)
83144cfc	111	{
3971a4d2	112	if (__position + 1 != end())
2f805868	113	std::copy(__position + 1, end(), __position);
03f9ea44	114	--this->_M_impl._M_finish;
1985f1cd	115	this->_M_impl.destroy(this->_M_impl._M_finish);
3971a4d2	116	return __position;
83144cfc	117	}
ed6814f7	118
af5fb6ab	119	template<typename _Tp, typename _Alloc>
874e7baa PC	120	typename vector<_Tp, _Alloc>::iterator
874e7baa PC	121	vector<_Tp, _Alloc>::
3971a4d2	122	erase(iterator __first, iterator __last)
83144cfc	123	{
bc9053ab PC	124	if (__last != end())
	125	std::copy(__last, end(), __first);
	126	_M_erase_at_end(__first.base() + (end() - __last));
3971a4d2	127	return __first;
83144cfc	128	}
ed6814f7	129
af5fb6ab	130	template<typename _Tp, typename _Alloc>
874e7baa PC	131	vector<_Tp, _Alloc>&
	132	vector<_Tp, _Alloc>::
	133	operator=(const vector<_Tp, _Alloc>& __x)
83144cfc	134	{
3971a4d2	135	if (&__x != this)
874e7baa PC	136	{
	137	const size_type __xlen = __x.size();
	138	if (__xlen > capacity())
	139	{
	140	pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
	141	__x.end());
1985f1cd	142	std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
4fd20a8f	143	_M_get_Tp_allocator());
874e7baa PC	144	_M_deallocate(this->_M_impl._M_start,
	145	this->_M_impl._M_end_of_storage
	146	- this->_M_impl._M_start);
	147	this->_M_impl._M_start = __tmp;
	148	this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
	149	}
	150	else if (size() >= __xlen)
	151	{
bc9053ab PC	152	std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
bc9053ab PC	153	end(), _M_get_Tp_allocator());
874e7baa PC	154	}
	155	else
	156	{
bc9053ab	157	std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
874e7baa	158	this->_M_impl._M_start);
bc9053ab PC	159	std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
	160	__x._M_impl._M_finish,
	161	this->_M_impl._M_finish,
4fd20a8f	162	_M_get_Tp_allocator());
874e7baa PC	163	}
	164	this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
	165	}
3971a4d2	166	return *this;
83144cfc	167	}
ed6814f7	168
af5fb6ab	169	template<typename _Tp, typename _Alloc>
3971a4d2	170	void
874e7baa	171	vector<_Tp, _Alloc>::
3971a4d2	172	_M_fill_assign(size_t __n, const value_type& __val)
83144cfc	173	{
3971a4d2	174	if (__n > capacity())
874e7baa	175	{
4fd20a8f	176	vector __tmp(__n, __val, _M_get_Tp_allocator());
874e7baa PC	177	__tmp.swap(*this);
874e7baa PC	178	}
3971a4d2	179	else if (__n > size())
874e7baa PC	180	{
874e7baa PC	181	std::fill(begin(), end(), __val);
1985f1cd MA	182	std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
1985f1cd MA	183	__n - size(), __val,
4fd20a8f	184	_M_get_Tp_allocator());
368b7a30	185	this->_M_impl._M_finish += __n - size();
874e7baa	186	}
3971a4d2	187	else
bc9053ab	188	_M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
83144cfc	189	}
ed6814f7	190
874e7baa PC	191	template<typename _Tp, typename _Alloc>
	192	template<typename _InputIterator>
	193	void
	194	vector<_Tp, _Alloc>::
	195	_M_assign_aux(_InputIterator __first, _InputIterator __last,
6323b34e	196	std::input_iterator_tag)
3971a4d2	197	{
bc9053ab PC	198	pointer __cur(this->_M_impl._M_start);
	199	for (; __first != __last && __cur != this->_M_impl._M_finish;
	200	++__cur, ++__first)
874e7baa PC	201	__cur = __first;
874e7baa PC	202	if (__first == __last)
bc9053ab	203	_M_erase_at_end(__cur);
874e7baa PC	204	else
874e7baa PC	205	insert(end(), __first, __last);
3971a4d2	206	}
874e7baa PC	207
	208	template<typename _Tp, typename _Alloc>
	209	template<typename _ForwardIterator>
	210	void
43da93a7	211	vector<_Tp, _Alloc>::
874e7baa	212	_M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
6323b34e	213	std::forward_iterator_tag)
3971a4d2	214	{
43da93a7	215	const size_type __len = std::distance(__first, __last);
874e7baa PC	216
	217	if (__len > capacity())
	218	{
	219	pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
1985f1cd	220	std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
4fd20a8f	221	_M_get_Tp_allocator());
874e7baa PC	222	_M_deallocate(this->_M_impl._M_start,
	223	this->_M_impl._M_end_of_storage
	224	- this->_M_impl._M_start);
	225	this->_M_impl._M_start = __tmp;
	226	this->_M_impl._M_finish = this->_M_impl._M_start + __len;
	227	this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
	228	}
	229	else if (size() >= __len)
bc9053ab	230	_M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
874e7baa PC	231	else
	232	{
	233	_ForwardIterator __mid = __first;
	234	std::advance(__mid, size());
	235	std::copy(__first, __mid, this->_M_impl._M_start);
1985f1cd MA	236	this->_M_impl._M_finish =
	237	std::__uninitialized_copy_a(__mid, __last,
	238	this->_M_impl._M_finish,
4fd20a8f	239	_M_get_Tp_allocator());
874e7baa	240	}
3971a4d2	241	}
ed6814f7	242
af5fb6ab	243	template<typename _Tp, typename _Alloc>
3971a4d2	244	void
43da93a7	245	vector<_Tp, _Alloc>::
3971a4d2 PE	246	_M_insert_aux(iterator __position, const _Tp& __x)
3971a4d2 PE	247	{
03f9ea44	248	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
874e7baa	249	{
1985f1cd MA	250	this->_M_impl.construct(this->_M_impl._M_finish,
1985f1cd MA	251	*(this->_M_impl._M_finish - 1));
874e7baa PC	252	++this->_M_impl._M_finish;
874e7baa PC	253	_Tp __x_copy = __x;
bc9053ab PC	254	std::copy_backward(__position.base(),
	255	this->_M_impl._M_finish - 2,
	256	this->_M_impl._M_finish - 1);
874e7baa PC	257	*__position = __x_copy;
874e7baa PC	258	}
83144cfc	259	else
874e7baa	260	{
be1088fa ML	261	const size_type __len =
be1088fa ML	262	_M_check_len(size_type(1), "vector::_M_insert_aux");
bc9053ab PC	263	pointer __new_start(this->_M_allocate(__len));
bc9053ab PC	264	pointer __new_finish(__new_start);
874e7baa PC	265	try
874e7baa PC	266	{
1985f1cd	267	__new_finish =
bc9053ab PC	268	std::__uninitialized_copy_a(this->_M_impl._M_start,
bc9053ab PC	269	__position.base(), __new_start,
4fd20a8f	270	_M_get_Tp_allocator());
bc9053ab	271	this->_M_impl.construct(__new_finish, __x);
874e7baa	272	++__new_finish;
1985f1cd	273	__new_finish =
bc9053ab PC	274	std::__uninitialized_copy_a(__position.base(),
bc9053ab PC	275	this->_M_impl._M_finish,
1985f1cd	276	__new_finish,
4fd20a8f	277	_M_get_Tp_allocator());
996e5395	278	}
874e7baa PC	279	catch(...)
874e7baa PC	280	{
4fd20a8f	281	std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
bc9053ab	282	_M_deallocate(__new_start, __len);
874e7baa PC	283	__throw_exception_again;
874e7baa PC	284	}
bc9053ab PC	285	std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
bc9053ab PC	286	_M_get_Tp_allocator());
874e7baa PC	287	_M_deallocate(this->_M_impl._M_start,
	288	this->_M_impl._M_end_of_storage
	289	- this->_M_impl._M_start);
bc9053ab PC	290	this->_M_impl._M_start = __new_start;
	291	this->_M_impl._M_finish = __new_finish;
	292	this->_M_impl._M_end_of_storage = __new_start + __len;
874e7baa	293	}
83144cfc	294	}
64ebadac	295
af5fb6ab	296	template<typename _Tp, typename _Alloc>
3971a4d2	297	void
43da93a7	298	vector<_Tp, _Alloc>::
3971a4d2 PE	299	_M_fill_insert(iterator __position, size_type __n, const value_type& __x)
	300	{
	301	if (__n != 0)
874e7baa PC	302	{
	303	if (size_type(this->_M_impl._M_end_of_storage
	304	- this->_M_impl._M_finish) >= __n)
	305	{
	306	value_type __x_copy = __x;
	307	const size_type __elems_after = end() - __position;
bc9053ab	308	pointer __old_finish(this->_M_impl._M_finish);
874e7baa PC	309	if (__elems_after > __n)
874e7baa PC	310	{
1985f1cd MA	311	std::__uninitialized_copy_a(this->_M_impl._M_finish - __n,
	312	this->_M_impl._M_finish,
	313	this->_M_impl._M_finish,
4fd20a8f	314	_M_get_Tp_allocator());
874e7baa	315	this->_M_impl._M_finish += __n;
bc9053ab	316	std::copy_backward(__position.base(), __old_finish - __n,
874e7baa	317	__old_finish);
bc9053ab PC	318	std::fill(__position.base(), __position.base() + __n,
bc9053ab PC	319	__x_copy);
874e7baa PC	320	}
	321	else
	322	{
1985f1cd MA	323	std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
	324	__n - __elems_after,
	325	__x_copy,
4fd20a8f	326	_M_get_Tp_allocator());
874e7baa	327	this->_M_impl._M_finish += __n - __elems_after;
bc9053ab	328	std::__uninitialized_copy_a(__position.base(), __old_finish,
1985f1cd	329	this->_M_impl._M_finish,
4fd20a8f	330	_M_get_Tp_allocator());
874e7baa	331	this->_M_impl._M_finish += __elems_after;
bc9053ab	332	std::fill(__position.base(), __old_finish, __x_copy);
874e7baa PC	333	}
	334	}
	335	else
	336	{
be1088fa ML	337	const size_type __len =
be1088fa ML	338	_M_check_len(__n, "vector::_M_fill_insert");
bc9053ab PC	339	pointer __new_start(this->_M_allocate(__len));
bc9053ab PC	340	pointer __new_finish(__new_start);
874e7baa PC	341	try
874e7baa PC	342	{
1985f1cd	343	__new_finish =
bc9053ab PC	344	std::__uninitialized_copy_a(this->_M_impl._M_start,
bc9053ab PC	345	__position.base(),
1985f1cd	346	__new_start,
4fd20a8f	347	_M_get_Tp_allocator());
1985f1cd	348	std::__uninitialized_fill_n_a(__new_finish, __n, __x,
4fd20a8f	349	_M_get_Tp_allocator());
368b7a30	350	__new_finish += __n;
1985f1cd	351	__new_finish =
bc9053ab PC	352	std::__uninitialized_copy_a(__position.base(),
	353	this->_M_impl._M_finish,
	354	__new_finish,
4fd20a8f	355	_M_get_Tp_allocator());
874e7baa PC	356	}
	357	catch(...)
	358	{
1985f1cd	359	std::_Destroy(__new_start, __new_finish,
4fd20a8f	360	_M_get_Tp_allocator());
bc9053ab	361	_M_deallocate(__new_start, __len);
874e7baa PC	362	__throw_exception_again;
874e7baa PC	363	}
1985f1cd	364	std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
4fd20a8f	365	_M_get_Tp_allocator());
874e7baa PC	366	_M_deallocate(this->_M_impl._M_start,
	367	this->_M_impl._M_end_of_storage
	368	- this->_M_impl._M_start);
bc9053ab PC	369	this->_M_impl._M_start = __new_start;
	370	this->_M_impl._M_finish = __new_finish;
	371	this->_M_impl._M_end_of_storage = __new_start + __len;
874e7baa PC	372	}
874e7baa PC	373	}
3971a4d2	374	}
ed6814f7	375
232c4925 PC	376	template<typename _Tp, typename _Alloc>
	377	template<typename _InputIterator>
	378	void
	379	vector<_Tp, _Alloc>::
	380	_M_range_insert(iterator __pos, _InputIterator __first,
	381	_InputIterator __last, std::input_iterator_tag)
	382	{
	383	for (; __first != __last; ++__first)
	384	{
	385	__pos = insert(__pos, *__first);
	386	++__pos;
	387	}
	388	}
ed6814f7	389
874e7baa PC	390	template<typename _Tp, typename _Alloc>
	391	template<typename _ForwardIterator>
	392	void
43da93a7	393	vector<_Tp, _Alloc>::
996e5395	394	_M_range_insert(iterator __position, _ForwardIterator __first,
6323b34e	395	_ForwardIterator __last, std::forward_iterator_tag)
3971a4d2	396	{
874e7baa PC	397	if (__first != __last)
874e7baa PC	398	{
43da93a7	399	const size_type __n = std::distance(__first, __last);
874e7baa PC	400	if (size_type(this->_M_impl._M_end_of_storage
	401	- this->_M_impl._M_finish) >= __n)
	402	{
	403	const size_type __elems_after = end() - __position;
bc9053ab	404	pointer __old_finish(this->_M_impl._M_finish);
874e7baa PC	405	if (__elems_after > __n)
874e7baa PC	406	{
1985f1cd MA	407	std::__uninitialized_copy_a(this->_M_impl._M_finish - __n,
	408	this->_M_impl._M_finish,
	409	this->_M_impl._M_finish,
4fd20a8f	410	_M_get_Tp_allocator());
874e7baa	411	this->_M_impl._M_finish += __n;
bc9053ab	412	std::copy_backward(__position.base(), __old_finish - __n,
874e7baa PC	413	__old_finish);
	414	std::copy(__first, __last, __position);
	415	}
	416	else
	417	{
	418	_ForwardIterator __mid = __first;
	419	std::advance(__mid, __elems_after);
1985f1cd MA	420	std::__uninitialized_copy_a(__mid, __last,
1985f1cd MA	421	this->_M_impl._M_finish,
4fd20a8f	422	_M_get_Tp_allocator());
874e7baa	423	this->_M_impl._M_finish += __n - __elems_after;
bc9053ab PC	424	std::__uninitialized_copy_a(__position.base(),
bc9053ab PC	425	__old_finish,
1985f1cd	426	this->_M_impl._M_finish,
4fd20a8f	427	_M_get_Tp_allocator());
874e7baa PC	428	this->_M_impl._M_finish += __elems_after;
	429	std::copy(__first, __mid, __position);
	430	}
	431	}
	432	else
	433	{
be1088fa ML	434	const size_type __len =
be1088fa ML	435	_M_check_len(__n, "vector::_M_range_insert");
bc9053ab PC	436	pointer __new_start(this->_M_allocate(__len));
bc9053ab PC	437	pointer __new_finish(__new_start);
874e7baa PC	438	try
874e7baa PC	439	{
1985f1cd	440	__new_finish =
bc9053ab PC	441	std::__uninitialized_copy_a(this->_M_impl._M_start,
bc9053ab PC	442	__position.base(),
1985f1cd	443	__new_start,
4fd20a8f	444	_M_get_Tp_allocator());
1985f1cd MA	445	__new_finish =
1985f1cd MA	446	std::__uninitialized_copy_a(__first, __last, __new_finish,
4fd20a8f	447	_M_get_Tp_allocator());
1985f1cd	448	__new_finish =
bc9053ab PC	449	std::__uninitialized_copy_a(__position.base(),
bc9053ab PC	450	this->_M_impl._M_finish,
1985f1cd	451	__new_finish,
4fd20a8f	452	_M_get_Tp_allocator());
874e7baa PC	453	}
	454	catch(...)
	455	{
bc9053ab	456	std::_Destroy(__new_start, __new_finish,
4fd20a8f	457	_M_get_Tp_allocator());
bc9053ab	458	_M_deallocate(__new_start, __len);
874e7baa PC	459	__throw_exception_again;
874e7baa PC	460	}
1985f1cd	461	std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
4fd20a8f	462	_M_get_Tp_allocator());
874e7baa PC	463	_M_deallocate(this->_M_impl._M_start,
	464	this->_M_impl._M_end_of_storage
	465	- this->_M_impl._M_start);
bc9053ab PC	466	this->_M_impl._M_start = __new_start;
	467	this->_M_impl._M_finish = __new_finish;
	468	this->_M_impl._M_end_of_storage = __new_start + __len;
874e7baa PC	469	}
874e7baa PC	470	}
83144cfc	471	}
3cbc7af0	472
232c4925 PC	473
	474	// vector<bool>
	475
	476	template<typename _Alloc>
	477	void
	478	vector<bool, _Alloc>::
	479	_M_fill_insert(iterator __position, size_type __n, bool __x)
	480	{
	481	if (__n == 0)
	482	return;
	483	if (capacity() - size() >= __n)
	484	{
	485	std::copy_backward(__position, end(),
	486	this->_M_impl._M_finish + difference_type(__n));
	487	std::fill(__position, __position + difference_type(__n), __x);
	488	this->_M_impl._M_finish += difference_type(__n);
	489	}
	490	else
	491	{
be1088fa ML	492	const size_type __len =
be1088fa ML	493	_M_check_len(__n, "vector<bool>::_M_fill_insert");
232c4925 PC	494	_Bit_type * __q = this->_M_allocate(__len);
	495	iterator __i = _M_copy_aligned(begin(), __position,
	496	iterator(__q, 0));
	497	std::fill(__i, __i + difference_type(__n), __x);
	498	this->_M_impl._M_finish = std::copy(__position, end(),
	499	__i + difference_type(__n));
	500	this->_M_deallocate();
	501	this->_M_impl._M_end_of_storage = (__q + ((__len
	502	+ int(_S_word_bit) - 1)
	503	/ int(_S_word_bit)));
	504	this->_M_impl._M_start = iterator(__q, 0);
	505	}
	506	}
	507
	508	template<typename _Alloc>
	509	template<typename _ForwardIterator>
	510	void
	511	vector<bool, _Alloc>::
	512	_M_insert_range(iterator __position, _ForwardIterator __first,
	513	_ForwardIterator __last, std::forward_iterator_tag)
	514	{
	515	if (__first != __last)
	516	{
	517	size_type __n = std::distance(__first, __last);
	518	if (capacity() - size() >= __n)
	519	{
	520	std::copy_backward(__position, end(),
	521	this->_M_impl._M_finish
	522	+ difference_type(__n));
	523	std::copy(__first, __last, __position);
	524	this->_M_impl._M_finish += difference_type(__n);
	525	}
	526	else
	527	{
be1088fa ML	528	const size_type __len =
be1088fa ML	529	_M_check_len(__n, "vector<bool>::_M_insert_range");
232c4925 PC	530	_Bit_type * __q = this->_M_allocate(__len);
	531	iterator __i = _M_copy_aligned(begin(), __position,
	532	iterator(__q, 0));
	533	__i = std::copy(__first, __last, __i);
	534	this->_M_impl._M_finish = std::copy(__position, end(), __i);
	535	this->_M_deallocate();
	536	this->_M_impl._M_end_of_storage = (__q
	537	+ ((__len
	538	+ int(_S_word_bit) - 1)
	539	/ int(_S_word_bit)));
	540	this->_M_impl._M_start = iterator(__q, 0);
	541	}
	542	}
	543	}
	544
	545	template<typename _Alloc>
	546	void
	547	vector<bool, _Alloc>::
	548	_M_insert_aux(iterator __position, bool __x)
	549	{
	550	if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
	551	{
	552	std::copy_backward(__position, this->_M_impl._M_finish,
	553	this->_M_impl._M_finish + 1);
	554	*__position = __x;
	555	++this->_M_impl._M_finish;
	556	}
	557	else
	558	{
be1088fa ML	559	const size_type __len =
be1088fa ML	560	_M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
232c4925 PC	561	_Bit_type * __q = this->_M_allocate(__len);
	562	iterator __i = _M_copy_aligned(begin(), __position,
	563	iterator(__q, 0));
	564	*__i++ = __x;
	565	this->_M_impl._M_finish = std::copy(__position, end(), __i);
	566	this->_M_deallocate();
	567	this->_M_impl._M_end_of_storage = (__q + ((__len
	568	+ int(_S_word_bit) - 1)
	569	/ int(_S_word_bit)));
	570	this->_M_impl._M_start = iterator(__q, 0);
	571	}
	572	}
	573
3cbc7af0	574	_GLIBCXX_END_NESTED_NAMESPACE
83144cfc	575
3d7c150e	576	#endif /* _VECTOR_TCC */