Re: About std::vector::resize().

[Dhruv Matani <dhruvbird at gmx dot net>]

On Sun, 2004-05-30 at 14:47, Paolo Carlini wrote:
> Dhruv Matani wrote:
> 
> >> That's ok... provided the final result doesn't apply only to
> >> vector<vector>>, of course... ;) ;)
> >
> > Yes.
> >
> > It would apply to vector <any_STL_container>
> 
> I see. Honestly, I will be away all the next week and will not be able
> to follow in detail your work 'til next week. Anyway, I first, preliminary,
> comment: any chances we can begin with the simple improvement sketched by
> Carlo? That would apply to builtin types, if I understand well, and 
> definitely,
> *much* more code around would benefit from it. Seems straightforward, right?

Continuing from where we left off last time, I have a patch for the
vector that I am currently using.

I have also attached the file used to test out the patch, because I
believe that there is no test-suite file that exercises
vector<vector<>>.

-- 
        -Dhruv Matani.
http://www.geocities.com/dhruvbird/

Proud to be a Vegetarian.
http://www.vegetarianstarterkit.com/
http://www.vegkids.com/vegkids/index.html

diff -Nrcp -x'*cvs*' ./include/bits/stl_type_traits.h /home/dhruv/projects/modified_library/include/bits/stl_type_traits.h
*** ./include/bits/stl_type_traits.h	1970-01-01 05:30:00.000000000 +0530
--- /home/dhruv/projects/modified_library/include/bits/stl_type_traits.h	2004-06-09 19:32:47.000000000 +0530
***************
*** 0 ****
--- 1,36 ----
+ // -*- C++ -*-
+ 
+ #if !defined _STL_TYPE_TRAITS_H
+ #define _STL_TYPE_TRAITS_H 1
+ 
+ namespace __gnu_internal
+ {
+   typedef char __one;
+   typedef char __two[2];
+ 
+   template<typename _Tp>
+   __one&
+   __has_swappable_typedef(typename _Tp::_Swappable_container const*);
+ 
+   template<typename>
+   __two&
+   __has_swappable_typedef(...);
+ 
+   struct _STL_swappable_container { };
+   struct _Non_swappable_type { };
+ 
+   template<typename _Tp, bool = 
+ 	   sizeof(__has_swappable_typedef<_Tp>(0)) == sizeof(char)>
+     struct _STL_type_trait
+     {
+       typedef _Non_swappable_type _Type;
+     };
+ 
+   template<typename _Tp>
+     struct _STL_type_trait<_Tp, true>
+     {
+       typedef _STL_swappable_container _Type;
+     };
+ }
+ 
+ #endif //_STL_TYPE_TRAITS_H
diff -Nrcp -x'*cvs*' ./include/bits/stl_vector.h /home/dhruv/projects/modified_library/include/bits/stl_vector.h
*** ./include/bits/stl_vector.h	2004-04-26 14:32:43.000000000 +0530
--- /home/dhruv/projects/modified_library/include/bits/stl_vector.h	2004-06-09 19:32:39.000000000 +0530
***************
*** 64,69 ****
--- 64,70 ----
  #include <bits/stl_iterator_base_funcs.h>
  #include <bits/functexcept.h>
  #include <bits/concept_check.h>
+ #include <bits/stl_type_traits.h>
  
  namespace _GLIBCXX_STD
  {
*************** namespace _GLIBCXX_STD
*** 166,171 ****
--- 167,173 ----
        typedef size_t					size_type;
        typedef ptrdiff_t					difference_type;
        typedef typename _Base::allocator_type		allocator_type;
+       typedef allocator_type _Swappable_container;
  
      protected:
        /** @if maint
*************** namespace _GLIBCXX_STD
*** 177,182 ****
--- 179,188 ----
        using _Base::_M_deallocate;
        using _Base::_M_impl;
  
+       typedef ::__gnu_internal::_STL_swappable_container 
+         _STL_swappable_container;
+       typedef ::__gnu_internal::_Non_swappable_type _Non_swappable_type;
+ 
      public:
        // [23.2.4.1] construct/copy/destroy
        // (assign() and get_allocator() are also listed in this section)
*************** namespace _GLIBCXX_STD
*** 472,477 ****
--- 478,489 ----
        void
        reserve(size_type __n);
  
+       void
+       _M_reserve_dispatch(size_type __n, _STL_swappable_container);
+ 
+       void
+       _M_reserve_dispatch(size_type __n, _Non_swappable_type);
+ 
        // element access
        /**
         *  @brief  Subscript access to the data contained in the %vector.
*************** namespace _GLIBCXX_STD
*** 693,698 ****
--- 705,716 ----
        iterator
        erase(iterator __position);
  
+       iterator
+       _M_erase_dispatch(iterator __position, _STL_swappable_container);
+ 
+       iterator
+       _M_erase_dispatch(iterator __position, _Non_swappable_type);
+ 
        /**
         *  @brief  Remove a range of elements.
         *  @param  first  Iterator pointing to the first element to be erased.
*************** namespace _GLIBCXX_STD
*** 714,719 ****
--- 732,745 ----
        iterator
        erase(iterator __first, iterator __last);
  
+       iterator
+       _M_erase_dispatch(iterator __first, iterator __last, 
+ 			_STL_swappable_container);
+ 
+       iterator
+       _M_erase_dispatch(iterator __first, iterator __last, 
+ 			_Non_swappable_type);
+ 
        /**
         *  @brief  Swaps data with another %vector.
         *  @param  x  A %vector of the same element and allocator types.
*************** namespace _GLIBCXX_STD
*** 894,907 ****
--- 920,967 ----
          _M_range_insert(iterator __pos, _ForwardIterator __first,
  			_ForwardIterator __last, forward_iterator_tag);
  
+       template<typename _ForwardIterator>
+         void
+         _M_range_insert_fwd_iter_dispatch(iterator __pos, 
+ 					  _ForwardIterator __first,
+ 					  _ForwardIterator __last, 
+ 					  _STL_swappable_container);
+ 
+       template<typename _ForwardIterator>
+         void
+         _M_range_insert_fwd_iter_dispatch(iterator __pos, 
+ 					  _ForwardIterator __first,
+ 					  _ForwardIterator __last, 
+ 					  _Non_swappable_type);
+ 
        // Called by insert(p,n,x), and the range insert when it turns out to be
        // the same thing.
        void
        _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
  
+       void
+       _M_fill_insert_dispatch(iterator __pos, 
+ 			      size_type __n, 
+ 			      const value_type& __x, 
+ 			      _STL_swappable_container);
+ 
+       void
+       _M_fill_insert_dispatch(iterator __pos, 
+ 			      size_type __n, 
+ 			      const value_type& __x, 
+ 			      _Non_swappable_type);
+ 
        // Called by insert(p,x)
        void
        _M_insert_aux(iterator __position, const value_type& __x);
+ 
+       void
+       _M_insert_aux_dispatch(iterator __position, const value_type& __x, 
+ 			     _STL_swappable_container);
+ 
+       void
+       _M_insert_aux_dispatch(iterator __position, const value_type& __x, 
+ 			     _Non_swappable_type);
      };
  
  
diff -Nrcp -x'*cvs*' ./include/bits/vector.tcc /home/dhruv/projects/modified_library/include/bits/vector.tcc
*** ./include/bits/vector.tcc	2004-04-26 14:32:43.000000000 +0530
--- /home/dhruv/projects/modified_library/include/bits/vector.tcc	2004-06-09 19:32:32.000000000 +0530
*************** namespace _GLIBCXX_STD
*** 66,89 ****
    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_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>
--- 66,121 ----
    template<typename _Tp, typename _Alloc>
      void
      vector<_Tp, _Alloc>::
+     _M_reserve_dispatch(size_type __n, _STL_swappable_container)
+     {
+       //_Tp is guaranteed to be default constructible.
+       pointer __tmp = _M_allocate(__n);
+       std::uninitialized_fill(__tmp, __tmp+this->size(), _Tp());
+       iterator __rover = this->begin();
+       while (__rover != this->end())
+ 	{
+ 	  __rover->swap(*__tmp);
+ 	  ++__rover;
+ 	  ++__tmp;
+ 	}
+       size_type __old_size = this->size();
+ 
+       std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);
+       this->_M_deallocate(this->_M_impl._M_start, this->capacity());
+       this->_M_impl._M_start = __tmp;
+       this->_M_impl._M_finish = __tmp + __old_size;
+       this->_M_impl._M_end_of_storage = __tmp + __n;
+     }
+ 
+   template<typename _Tp, typename _Alloc>
+     void
+     vector<_Tp, _Alloc>::
+     _M_reserve_dispatch(size_type __n, _Non_swappable_type)
+     {
+       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_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>
+     void
+     vector<_Tp, _Alloc>::
      reserve(size_type __n)
      {
        if (__n > this->max_size())
  	__throw_length_error(__N("vector::reserve"));
        if (this->capacity() < __n)
! 	_M_reserve_dispatch(__n, typename 
! 			    ::__gnu_internal::_STL_type_trait
! 			    <_Tp>::_Type());
      }
  
    template<typename _Tp, typename _Alloc>
*************** namespace _GLIBCXX_STD
*** 106,112 ****
    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);
--- 138,160 ----
    template<typename _Tp, typename _Alloc>
      typename vector<_Tp, _Alloc>::iterator
      vector<_Tp, _Alloc>::
!     _M_erase_dispatch(iterator __position, _STL_swappable_container)
!     {
!       iterator __old_pos = __position;
!       while (__position + 1 != end())
! 	{
! 	  __position->swap(__position[1]);
! 	  ++__position;
! 	}
!       --this->_M_impl._M_finish;
!       std::_Destroy(this->_M_impl._M_finish);
!       return __old_pos;
!     }
! 
!   template<typename _Tp, typename _Alloc>
!     typename vector<_Tp, _Alloc>::iterator
!     vector<_Tp, _Alloc>::
!     _M_erase_dispatch(iterator __position, _Non_swappable_type)
      {
        if (__position + 1 != end())
          std::copy(__position + 1, end(), __position);
*************** namespace _GLIBCXX_STD
*** 118,124 ****
    template<typename _Tp, typename _Alloc>
      typename vector<_Tp, _Alloc>::iterator
      vector<_Tp, _Alloc>::
!     erase(iterator __first, iterator __last)
      {
        iterator __i(copy(__last, end(), __first));
        std::_Destroy(__i, end());
--- 166,199 ----
    template<typename _Tp, typename _Alloc>
      typename vector<_Tp, _Alloc>::iterator
      vector<_Tp, _Alloc>::
!     erase(iterator __position)
!     {
!       return _M_erase_dispatch(__position, typename 
! 			       ::__gnu_internal::_STL_type_trait
! 			       <_Tp>::_Type());
!     }
! 
!   template<typename _Tp, typename _Alloc>
!     typename vector<_Tp, _Alloc>::iterator
!     vector<_Tp, _Alloc>::
!     _M_erase_dispatch(iterator __first, iterator __last, _STL_swappable_container)
!     {
!       iterator __old_first = __first;
!       while (__last != this->end())
! 	{
! 	  __first->swap(*__last);
! 	  ++__first;
! 	  ++__last;
! 	}
!       std::_Destroy(__first, end());
!       this->_M_impl._M_finish = this->_M_impl._M_finish - (__last - __first);
!       return __old_first;
!     }
! 
!   template<typename _Tp, typename _Alloc>
!     typename vector<_Tp, _Alloc>::iterator
!     vector<_Tp, _Alloc>::
!     _M_erase_dispatch(iterator __first, iterator __last, _Non_swappable_type)
      {
        iterator __i(copy(__last, end(), __first));
        std::_Destroy(__i, end());
*************** namespace _GLIBCXX_STD
*** 127,132 ****
--- 202,216 ----
      }
  
    template<typename _Tp, typename _Alloc>
+     typename vector<_Tp, _Alloc>::iterator
+     vector<_Tp, _Alloc>::
+     erase(iterator __first, iterator __last)
+     {
+       return _M_erase_dispatch(__first, __last, typename
+ 			       ::__gnu_internal::_STL_type_trait<_Tp>::_Type());
+     }
+ 
+   template<typename _Tp, typename _Alloc>
      vector<_Tp, _Alloc>&
      vector<_Tp, _Alloc>::
      operator=(const vector<_Tp, _Alloc>& __x)
*************** namespace _GLIBCXX_STD
*** 243,249 ****
    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)
  	{
--- 327,383 ----
    template<typename _Tp, typename _Alloc>
      void
      vector<_Tp,_Alloc>::
!     _M_insert_aux_dispatch(iterator __position, const _Tp& __x, 
! 			   _STL_swappable_container)
!     {
!       //Is there room for the new single element?
!       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
! 	{
! 	  //There is room for at least 1 new element.
! 	  std::_Construct(this->_M_impl._M_finish, _Tp());
! 	  iterator __tmp = this->end();
! 	  ++this->_M_impl._M_finish;
! 	  _Tp __x_copy = __x;
! 	  while (__tmp != __position)
! 	    {
! 	      __tmp->swap(__tmp[-1]);
! 	      --__tmp;
! 	    }
! 	  *__tmp = __x_copy;
! 	}
!       else
! 	{
! 	  vector<_Tp, _Alloc> __temp(this->get_allocator());
! 	  __temp.reserve(this->size() ? this->size()*2 : 1);
! 	  //Perform all throwable operartions first.
! 	  __temp.resize(this->size() + 1);
! 	  size_type __insert_where = __position - this->begin();
! 	  __temp[__insert_where] = __x;
! 	  //The operations below should not throw.
! 	  iterator __first = this->begin();
! 	  iterator __other_first = __temp.begin();
! 	  while (__first != __position)
! 	    {
! 	      __other_first->swap(*__first);
! 	      ++__first;
! 	      ++__other_first;
! 	    }
! 	  ++__other_first;
! 	  while (__first != this->end())
! 	    {
! 	      __other_first->swap(*__first);
! 	      ++__first;
! 	      ++__other_first;
! 	    }
! 	  this->swap(__temp);
! 	}
!     }
! 
!   template<typename _Tp, typename _Alloc>
!     void
!     vector<_Tp,_Alloc>::
!     _M_insert_aux_dispatch(iterator __position, const _Tp& __x, 
! 			   _Non_swappable_type)
      {
        if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
  	{
*************** namespace _GLIBCXX_STD
*** 294,361 ****
    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;
! 	      iterator __old_finish(this->_M_impl._M_finish);
! 	      if (__elems_after > __n)
! 		{
! 		  std::uninitialized_copy(this->_M_impl._M_finish - __n,
! 					  this->_M_impl._M_finish,
! 					  this->_M_impl._M_finish);
! 		  this->_M_impl._M_finish += __n;
! 		  std::copy_backward(__position, __old_finish - __n,
! 				     __old_finish);
! 		  std::fill(__position, __position + __n, __x_copy);
! 		}
! 	      else
! 		{
! 		  std::uninitialized_fill_n(this->_M_impl._M_finish,
! 					    __n - __elems_after,
! 					    __x_copy);
! 		  this->_M_impl._M_finish += __n - __elems_after;
! 		  std::uninitialized_copy(__position, __old_finish,
! 					  this->_M_impl._M_finish);
! 		  this->_M_impl._M_finish += __elems_after;
! 		  std::fill(__position, __old_finish, __x_copy);
! 		}
  	    }
  	  else
  	    {
! 	      const size_type __old_size = size();
! 	      const size_type __len = __old_size + std::max(__old_size, __n);
! 	      iterator __new_start(this->_M_allocate(__len));
! 	      iterator __new_finish(__new_start);
! 	      try
! 		{
! 		  __new_finish = std::uninitialized_copy(begin(), __position,
! 							 __new_start);
! 		  __new_finish = std::uninitialized_fill_n(__new_finish, __n,
! 							   __x);
! 		  __new_finish = std::uninitialized_copy(__position, end(),
! 							 __new_finish);
! 		}
! 	      catch(...)
! 		{
! 		  std::_Destroy(__new_start,__new_finish);
! 		  _M_deallocate(__new_start.base(),__len);
! 		  __throw_exception_again;
! 		}
! 	      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);
! 	      _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.base();
! 	      this->_M_impl._M_finish = __new_finish.base();
! 	      this->_M_impl._M_end_of_storage = __new_start.base() + __len;
  	    }
  	}
      }
  
    template<typename _Tp, typename _Alloc> template<typename _InputIterator>
--- 428,636 ----
    template<typename _Tp, typename _Alloc>
      void
      vector<_Tp,_Alloc>::
!     _M_insert_aux(iterator __position, const _Tp& __x)
      {
!       _M_insert_aux_dispatch(__position, __x, typename
! 			     ::__gnu_internal::_STL_type_trait<_Tp>::_Type());
!     }
! 
!   template<typename _Tp, typename _Alloc>
!     void
!     vector<_Tp,_Alloc>::
!     _M_fill_insert_dispatch(iterator __position, size_type __n, 
! 			    const value_type& __x, _STL_swappable_container)
!     {
! 	//Is there space for these many elements without having to
! 	//re-allocate the memory?
! 	if (size_type(this->_M_impl._M_end_of_storage
! 		      - this->_M_impl._M_finish) >= __n)
! 	  {
! 	    value_type __x_copy = __x;
! 	    //How many elemnts to move for insertion?
! 	    const size_type __elems_after = end() - __position;
! 	    iterator __old_finish(this->_M_impl._M_finish);
! 	    //Construct __n elemnts at the end, and swap the
! 	    //last __n elemnts of the old vector with the
! 	    //default constructed ones.
! 	    if (__elems_after > __n)
! 	      {
! 		size_type __n_temp = __n;
! 		iterator __dest = this->end();
! 		iterator __src = __dest - __n;
! 
! 		while (__n_temp)
! 		  {
! 		    std::_Construct(&*__dest, value_type());
! 		    __dest->swap(*__src);
! 		    ++__dest;
! 		    ++__src;
! 		    --__n_temp;
! 		  }
! 		//Swap the remaining elemnts.
! 		__n_temp = __elems_after - __n;
! 		__src = __old_finish - __n - 1;
! 		__dest = __old_finish;
! 		while (__n_temp)
! 		  {
! 		    __dest->swap(*__src);
! 		    --__dest;
! 		    --__src;
! 		    --__n_temp;
! 		  }
! 		//Assign the remaining elements with the new range
! 		//to be inserted.
! 		while (__n)
! 		  {
! 		    *__position = __x_copy;
! 		    ++__position;
! 		    --__n;
! 		  }
! 	      }
! 	    else
! 	      {
! 		iterator __dest = this->end() + __n - 1;
! 		iterator __src = this->end() - 1;
! 		size_type __moves = __n - __elems_after;
! 		size_type __n_temp = __elems_after;
! 
! 		while (__n_temp)
! 		  {
! 		    std::_Construct(&*__dest, value_type());
! 		    __dest->swap(*__src);
! 		    --__dest;
! 		    --__src;
! 		    --__moves;
! 		  }
! 		__n_temp = __elems_after;
! 		__dest = this->end() - __elems_after;
! 
! 		while (__n_temp)
! 		  {
! 		    *__dest = __x;
! 		    --__n_temp;
! 		    ++__dest;
! 		  }
! 		__dest = this->end();
! 		while (__moves)
! 		  {
! 		    std::_Construct(&*__dest, __x);
! 		    --__moves;
! 		    ++__dest;
! 		  }
! 	      }
! 	    this->_M_impl._M_finish = this->_M_impl._M_finish + __n;
! 	  }
! 	else
! 	  {
! 	    const size_type __old_size = size();
! 	    const size_type __len = __old_size + std::max(__old_size, __n);
! 
! 	    vector<_Tp, _Alloc> __temp(this->get_allocator());
! 	    __temp.reserve(__len);
! 	    //Perform all throwable operartions first.
! 	    __temp.resize(this->size() + __n);
! 	    size_type __insert_where = __position - this->begin();
! 	    size_type __temp_n = __n;
! 	    while (__temp_n)
! 	      {
! 		__temp[__insert_where] = __x;
! 		++__insert_where;
! 		--__temp_n;
! 	      }
! 	    //The operations below should not throw.
! 	    iterator __new_first = this->begin();
! 	    iterator __other_first = __temp.begin();
! 	    while (__new_first != __position)
! 	      {
! 		__other_first->swap(*__new_first);
! 		++__new_first;
! 		++__other_first;
! 	      }
! 	    __other_first += __n;
! 	    while (__new_first != this->end())
! 	      {
! 		__other_first->swap(*__new_first);
! 		++__new_first;
! 		++__other_first;
! 	      }
! 	    this->swap(__temp);
! 	  }
!     }
! 
!   template<typename _Tp, typename _Alloc>
!     void
!     vector<_Tp,_Alloc>::
!     _M_fill_insert_dispatch(iterator __position, size_type __n, 
! 			    const value_type& __x, _Non_swappable_type)
!     {
!       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;
! 	  iterator __old_finish(this->_M_impl._M_finish);
! 	  if (__elems_after > __n)
  	    {
! 	      std::uninitialized_copy(this->_M_impl._M_finish - __n,
! 				      this->_M_impl._M_finish,
! 				      this->_M_impl._M_finish);
! 	      this->_M_impl._M_finish += __n;
! 	      std::copy_backward(__position, __old_finish - __n,
! 				 __old_finish);
! 	      std::fill(__position, __position + __n, __x_copy);
  	    }
  	  else
  	    {
! 	      std::uninitialized_fill_n(this->_M_impl._M_finish,
! 					__n - __elems_after,
! 					__x_copy);
! 	      this->_M_impl._M_finish += __n - __elems_after;
! 	      std::uninitialized_copy(__position, __old_finish,
! 				      this->_M_impl._M_finish);
! 	      this->_M_impl._M_finish += __elems_after;
! 	      std::fill(__position, __old_finish, __x_copy);
  	    }
  	}
+       else
+ 	{
+ 	  const size_type __old_size = size();
+ 	  const size_type __len = __old_size + std::max(__old_size, __n);
+ 	  iterator __new_start(this->_M_allocate(__len));
+ 	  iterator __new_finish(__new_start);
+ 	  try
+ 	    {
+ 	      __new_finish = std::uninitialized_copy(begin(), __position,
+ 						     __new_start);
+ 	      __new_finish = std::uninitialized_fill_n(__new_finish, __n,
+ 						       __x);
+ 	      __new_finish = std::uninitialized_copy(__position, end(),
+ 						     __new_finish);
+ 	    }
+ 	  catch(...)
+ 	    {
+ 	      std::_Destroy(__new_start,__new_finish);
+ 	      _M_deallocate(__new_start.base(),__len);
+ 	      __throw_exception_again;
+ 	    }
+ 	  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);
+ 	  _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.base();
+ 	  this->_M_impl._M_finish = __new_finish.base();
+ 	  this->_M_impl._M_end_of_storage = __new_start.base() + __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)
+ 	_M_fill_insert_dispatch
+ 	  (__position, __n, __x, typename 
+ 	   ::__gnu_internal::_STL_type_trait<_Tp>::_Type());
      }
  
    template<typename _Tp, typename _Alloc> template<typename _InputIterator>
*************** namespace _GLIBCXX_STD
*** 375,385 ****
      template<typename _ForwardIterator>
        void
        vector<_Tp,_Alloc>::
!       _M_range_insert(iterator __position,_ForwardIterator __first,
! 		      _ForwardIterator __last, forward_iterator_tag)
        {
! 	if (__first != __last)
  	  {
  	    size_type __n = std::distance(__first, __last);
  	    if (size_type(this->_M_impl._M_end_of_storage
  			  - this->_M_impl._M_finish) >= __n)
--- 650,789 ----
      template<typename _ForwardIterator>
        void
        vector<_Tp,_Alloc>::
!       _M_range_insert_fwd_iter_dispatch
!       (iterator __position, _ForwardIterator __first, 
!        _ForwardIterator __last, _STL_swappable_container)
        {
! 	//How many elements do we have to insert?
! 	size_type __n = std::distance(__first, __last);
! 	//Is there space for these many elements without having to
! 	//re-allocate the memory?
! 	if (size_type(this->_M_impl._M_end_of_storage
! 		      - this->_M_impl._M_finish) >= __n)
! 	  {
! 	    //How many elemnts to move for insertion?
! 	    const size_type __elems_after = end() - __position;
! 	    iterator __old_finish(this->_M_impl._M_finish);
! 	    //Construct __n elemnts at the end, and swap the
! 	    //last __n elemnts of the old vector with the
! 	    //default constructed ones.
! 
! 	    if (__elems_after > __n)
! 	      {
! 		size_type __n_temp = __n;
! 		iterator __dest = this->end();
! 		iterator __src = __dest - __n;
! 		while (__n_temp)
! 		  {
! 		    std::_Construct(&*__dest, value_type());
! 		    __dest->swap(*__src);
! 		    ++__dest;
! 		    ++__src;
! 		    --__n_temp;
! 		  }
! 		//Swap the remaining elemnts.
! 		__n_temp = __elems_after - __n;
! 		__src = __old_finish - __n - 1;
! 		__dest = __old_finish;
! 		while (__n_temp)
! 		  {
! 		    __dest->swap(*__src);
! 		    --__dest;
! 		    --__src;
! 		    --__n_temp;
! 		  }
! 		//Assign the remaining elements with the new range
! 		//to be inserted.
! 		while (__n)
! 		  {
! 		    *__position = *__first;
! 		    ++__position;
! 		    ++__first;
! 		    --__n;
! 		  }
! 	      }
! 	    else
! 	      {
! 		iterator __dest = this->end() + __n - 1;
! 		iterator __src = this->end() - 1;
! 		size_type __moves = __n - __elems_after;
! 		size_type __n_temp = __elems_after;
! 
! 		while (__n_temp)
! 		  {
! 		    std::_Construct(&*__dest, value_type());
! 		    __dest->swap(*__src);
! 		    --__dest;
! 		    --__src;
! 		    --__moves;
! 		  }
! 		__n_temp = __elems_after;
! 		__dest = this->end() - __elems_after;
! 
! 		while (__n_temp)
! 		  {
! 		    *__dest = *__first;
! 		    --__n_temp;
! 		    ++__dest;
! 		    ++__first;
! 		  }
! 		__dest = this->end();
! 		while (__moves)
! 		  {
! 		    std::_Construct(&*__dest, *__first);
! 		    --__moves;
! 		    ++__dest;
! 		    ++__first;
! 		  }
! 	      }
! 	    this->_M_impl._M_finish = this->_M_impl._M_finish + __n;
! 	  }
! 	else
  	  {
+ 	    const size_type __old_size = size();
+ 	    const size_type __len = __old_size + std::max(__old_size, __n);
+ 
+ 	    vector<_Tp, _Alloc> __temp(this->get_allocator());
+ 	    __temp.reserve(__len);
+ 	    //Perform all throwable operartions first.
+ 	    __temp.resize(this->size() + __n);
+ 	    size_type __insert_where = __position - this->begin();
+ 	    size_type __temp_n = __n;
+ 	    while (__temp_n)
+ 	      {
+ 		__temp[__insert_where] = *__first;
+ 		++__insert_where;
+ 		++__first;
+ 		--__temp_n;
+ 	      }
+ 	    //The operations below should not throw.
+ 	    iterator __new_first = this->begin();
+ 	    iterator __other_first = __temp.begin();
+ 	    while (__new_first != __position)
+ 	      {
+ 		__other_first->swap(*__new_first);
+ 		++__new_first;
+ 		++__other_first;
+ 	      }
+ 	    __other_first += __n;
+ 	    while (__new_first != this->end())
+ 	      {
+ 		__other_first->swap(*__new_first);
+ 		++__new_first;
+ 		++__other_first;
+ 	      }
+ 	    this->swap(__temp);
+ 	  }
+       }
+ 
+   template<typename _Tp, typename _Alloc>
+     template<typename _ForwardIterator>
+       void
+       vector<_Tp,_Alloc>::
+       _M_range_insert_fwd_iter_dispatch
+       (iterator __position, _ForwardIterator __first, 
+        _ForwardIterator __last, _Non_swappable_type)
+       {
  	    size_type __n = std::distance(__first, __last);
  	    if (size_type(this->_M_impl._M_end_of_storage
  			  - this->_M_impl._M_finish) >= __n)
*************** namespace _GLIBCXX_STD
*** 444,450 ****
  		this->_M_impl._M_finish = __new_finish.base();
  		this->_M_impl._M_end_of_storage = __new_start.base() + __len;
  	      }
! 	  }
        }
  } // namespace std
  
--- 848,867 ----
  		this->_M_impl._M_finish = __new_finish.base();
  		this->_M_impl._M_end_of_storage = __new_start.base() + __len;
  	      }
!       }
! 
!   template<typename _Tp, typename _Alloc>
!     template<typename _ForwardIterator>
!       void
!       vector<_Tp,_Alloc>::
!       _M_range_insert(iterator __position,_ForwardIterator __first,
! 		      _ForwardIterator __last, forward_iterator_tag)
!       {
! 	//Is the range to be inserted non-empty?
! 	if (__first != __last)
! 	  _M_range_insert_fwd_iter_dispatch
! 	    (__position, __first, __last, typename 
! 	     ::__gnu_internal::_STL_type_trait<_Tp>::_Type());
        }
  } // namespace std
  

#include <iostream>
using namespace std;

#include <vector>

#include <list>
#include <cstdlib>

struct Timer {
  clock_t begin, end;
  void start() { begin = clock(); }
  void stop() { end = clock(); }
  double operator()() { return static_cast<double>
			  (end-begin)/CLOCKS_PER_SEC; }
};

using namespace std;

typedef std::vector<int> child;
struct Non_swappable {
  child _c;
  Non_swappable(child const& _ch) : _c(_ch) { }

//   //To make a type swappable, we must:
//   //1. Define a default constructor.
//   Non_swappable() { }
//   //Define a nested typedef _Swappable_container.
//   typedef void _Swappable_container;
//   //Create a member swap function.
//   void swap(Non_swappable& _other) { this->_c.swap(_other._c); }
};

template<typename Child_type>
void test01(Child_type const& _child, int Iterations)
{
  typedef std::vector<Child_type> victim;
  victim _vic;
  victim tmp(5, _child);

  _vic.insert(_vic.end(), 5, _child);
  _vic.insert(_vic.end(), tmp.begin(), tmp.end());

  Timer t;
  t.start();
  for(int i = 0; i < Iterations; ++i)
    _vic.insert(_vic.begin(), _child);
  t.stop();
  cout<<"The time taken is: "<<t()<<" Seconds."<<endl;
}

template<typename Child_type>
void test02(Child_type const& _child, int Iterations)
{
  typedef std::vector<Child_type> victim;
  victim _vic;
  Timer t;
  t.start();
  for(int i = 0; i < Iterations; ++i)
    {
      int _sz = _vic.size();
      int _pos = _sz ? rand()%_sz : 0;
      _vic.insert(_vic.begin() + _pos, _child);
    }

  t.stop();
  cout<<"The time taken is: "<<t()<<" Seconds."<<endl;
}

template<typename Child_type>
void test03(Child_type const& _child, int Iterations)
{
  typedef std::vector<Child_type> victim;
  victim _vic;
  Timer t;
  t.start();
  for(int i = 0; i < Iterations; ++i)
    _vic.push_back(_child);
  t.stop();
  cout<<"The time taken is: "<<t()<<" Seconds."<<endl;
}

template<typename Child_type>
void test04(Child_type const& _child, int Iterations)
{
  typedef std::vector<Child_type> victim;
  victim _vic(Iterations, _child);
  Timer t;
  t.start();
  for(int i = 0; i < Iterations; ++i)
    _vic.erase(_vic.begin());
  t.stop();
  cout<<"The time taken is: "<<t()<<" Seconds."<<endl;
}

template<typename Child_type>
void test05(Child_type const& _child, int Iterations)
{
  typedef std::vector<Child_type> victim;
  victim _vic(Iterations, _child);
  Timer t;
  t.start();
  for(int i = 0; i < Iterations; ++i)
    {
      int _sz = _vic.size();
      int _pos = _sz ? rand()%_sz : 0;
      _vic.erase(_vic.begin() + _pos);
    }

  t.stop();
  cout<<"The time taken is: "<<t()<<" Seconds."<<endl;
}

template<typename Child_type>
void test06(Child_type const& _child, int Iterations)
{
  typedef std::vector<Child_type> victim;
  victim _vic(Iterations, _child);
  Timer t;
  t.start();
  for(int i = 0; i < Iterations; ++i)
    _vic.pop_back();
  t.stop();
  cout<<"The time taken is: "<<t()<<" Seconds."<<endl;
}

int main()
{
  child iv(1024, 23);
  Non_swappable _ns(iv);

  //Test-1.
  //Insertion at the beginning of the vector.
  test01(iv, 1024);
  test01(_ns, 1024);

  //Test-2.
  //Random insertion into the vector.
  test02(iv, 1024);
  test02(_ns, 1024);

  //Test-3.
  //Insertion at the end of the vector.
  test03(iv, 1024);
  test03(_ns, 1024);

  //Test-4.
  //Erasing from the beginning of the vector.
  test04(iv, 1024);
  test04(_ns, 1024);

  //Test-6.
  //Erasing at random positions.
  test05(iv, 1024);
  test05(_ns, 1024);

  //Test-7.
  //Erasing at the end.
  test06(iv, 1024);
  test06(_ns, 1024);
}