This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Patch: stl_vector.h and vector.tcc
- From: Dhruv Matani <dhruvbird at gmx dot net>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Cc: Paolo Carlini <pcarlini at suse dot de>
- Date: 12 Jul 2004 18:55:49 +0530
- Subject: Patch: stl_vector.h and vector.tcc
- Organization:
Hi,
This patch optimizes std::vector<> for Swappable types. Ones that can
be swapped in constant time, like std::vector<> itself, and where swap
is not defined in terms of assignment.
Also, attached is a test case, which tries to detect possible errors in
the new code, and also some performance routines, that give a fair idea
of how much improvement the patch has brought about for some fairly
common cases.
The file stl_type_traits.h needs to be copied to the include/bits folder
for the correct operation of this patch.
--
-Dhruv Matani.
http://www.geocities.com/dhruvbird/
As a rule, man is a fool. When it's hot, he wants it cold.
When it's cold he wants it hot. He always wants what is not.
-Anon.
*** stl_vector.h 2004-07-12 18:26:36.000000000 +0530
--- /home/dhruv/projects/new_libstdc++-v3/stl_vector.h 2004-06-09 19:13:36.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
*** 81,87 ****
_Tp* _M_start;
_Tp* _M_finish;
_Tp* _M_end_of_storage;
! _Vector_impl(_Alloc const& __a)
: _Alloc(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
{ }
};
--- 82,88 ----
_Tp* _M_start;
_Tp* _M_finish;
_Tp* _M_end_of_storage;
! _Vector_impl (_Alloc const& __a)
: _Alloc(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
{ }
};
*************** namespace _GLIBCXX_STD
*** 153,171 ****
typedef vector<_Tp, _Alloc> vector_type;
public:
! typedef _Tp value_type;
! typedef typename _Alloc::pointer pointer;
! typedef typename _Alloc::const_pointer const_pointer;
! typedef typename _Alloc::reference reference;
! typedef typename _Alloc::const_reference const_reference;
typedef __gnu_cxx::__normal_iterator<pointer, vector_type> iterator;
typedef __gnu_cxx::__normal_iterator<const_pointer, vector_type>
const_iterator;
! typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
! typedef std::reverse_iterator<iterator> reverse_iterator;
! typedef size_t size_type;
! typedef ptrdiff_t difference_type;
! typedef typename _Base::allocator_type allocator_type;
protected:
/** @if maint
--- 154,173 ----
typedef vector<_Tp, _Alloc> vector_type;
public:
! typedef _Tp value_type;
! typedef value_type* pointer;
! typedef const value_type* const_pointer;
typedef __gnu_cxx::__normal_iterator<pointer, vector_type> iterator;
typedef __gnu_cxx::__normal_iterator<const_pointer, vector_type>
const_iterator;
! typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
! typedef std::reverse_iterator<iterator> reverse_iterator;
! typedef value_type& reference;
! typedef const value_type& const_reference;
! 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
*** 799,805 ****
_M_range_initialize(_InputIterator __first,
_InputIterator __last, input_iterator_tag)
{
! for (; __first != __last; ++__first)
push_back(*__first);
}
--- 825,831 ----
_M_range_initialize(_InputIterator __first,
_InputIterator __last, input_iterator_tag)
{
! for ( ; __first != __last; ++__first)
push_back(*__first);
}
*************** namespace _GLIBCXX_STD
*** 809,815 ****
_M_range_initialize(_ForwardIterator __first,
_ForwardIterator __last, forward_iterator_tag)
{
! const size_type __n = std::distance(__first, __last);
this->_M_impl._M_start = this->_M_allocate(__n);
this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
this->_M_impl._M_finish = std::uninitialized_copy(__first, __last,
--- 835,841 ----
_M_range_initialize(_ForwardIterator __first,
_ForwardIterator __last, forward_iterator_tag)
{
! size_type __n = std::distance(__first, __last);
this->_M_impl._M_start = this->_M_allocate(__n);
this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
this->_M_impl._M_finish = std::uninitialized_copy(__first, __last,
*************** 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);
};
*** vector.tcc 2004-07-12 18:26:38.000000000 +0530
--- /home/dhruv/projects/new_libstdc++-v3/vector.tcc 2004-06-25 11:37:00.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
*** 91,97 ****
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())
{
--- 123,129 ----
vector<_Tp, _Alloc>::
insert(iterator __position, const value_type& __x)
{
! size_type __n = __position - begin();
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
&& __position == end())
{
*************** 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
*** 193,199 ****
input_iterator_tag)
{
iterator __cur(begin());
! for (; __first != __last && __cur != end(); ++__cur, ++__first)
*__cur = *__first;
if (__first == __last)
erase(__cur, end());
--- 277,283 ----
input_iterator_tag)
{
iterator __cur(begin());
! for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
*__cur = *__first;
if (__first == __last)
erase(__cur, end());
*************** namespace _GLIBCXX_STD
*** 204,214 ****
template<typename _Tp, typename _Alloc>
template<typename _ForwardIterator>
void
! vector<_Tp, _Alloc>::
_M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag)
{
! const size_type __len = std::distance(__first, __last);
if (__len > capacity())
{
--- 288,298 ----
template<typename _Tp, typename _Alloc>
template<typename _ForwardIterator>
void
! vector<_Tp,_Alloc>::
_M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag)
{
! size_type __len = std::distance(__first, __last);
if (__len > capacity())
{
*************** namespace _GLIBCXX_STD
*** 242,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)
{
--- 326,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
*** 293,370 ****
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>
void
! vector<_Tp, _Alloc>::
_M_range_insert(iterator __pos, _InputIterator __first,
_InputIterator __last, input_iterator_tag)
{
! for (; __first != __last; ++__first)
{
__pos = insert(__pos, *__first);
++__pos;
--- 427,645 ----
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)
! {
! //How many elemnts to move for insertion?
! const size_type __elems_after = end() - __position;
! //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;
! const value_type __x_copy = __x;
! const iterator __old_finish(this->_M_impl._M_finish);
! 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>
void
! vector<_Tp,_Alloc>::
_M_range_insert(iterator __pos, _InputIterator __first,
_InputIterator __last, input_iterator_tag)
{
! for ( ; __first != __last; ++__first)
{
__pos = insert(__pos, *__first);
++__pos;
*************** namespace _GLIBCXX_STD
*** 374,386 ****
template<typename _Tp, typename _Alloc>
template<typename _ForwardIterator>
void
! vector<_Tp, _Alloc>::
! _M_range_insert(iterator __position,_ForwardIterator __first,
! _ForwardIterator __last, 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)
{
--- 649,790 ----
template<typename _Tp, typename _Alloc>
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
// -*- 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
#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() { }
// // 2. Define a nested typedef _Swappable_container.
// typedef void _Swappable_container;
// // 3. Create a member swap function.
// void swap(Non_swappable& _other) { this->_c.swap(_other._c); }
};
template<typename Child_type>
void
check01(int Iterations)
{
typedef std::vector<Child_type> victim;
victim _vic;
for(int i = 0; i < Iterations; ++i)
_vic.insert(_vic.begin(), Child_type(i, 0));
int ctr = 0;
for(int i = Iterations - 1; i >= 0; --i)
{
assert((int)_vic[ctr++].size() == i);
}
}
template<typename Child_type>
void
check02(int Iterations)
{
typedef std::vector<Child_type> victim;
std::vector<int> sizes;
victim _vic;
for(int i = 0; i < Iterations; ++i)
{
int _sz = _vic.size();
int _pos = _sz ? rand()%_sz : 0;
_vic.insert(_vic.begin() + _pos, Child_type(i, 0));
sizes.insert(sizes.begin() + _pos, i);
}
for(int i = 0; i < Iterations; ++i)
{
assert(sizes[i] == (int)_vic[i].size());
}
}
template<typename Child_type>
void
check03(int Iterations)
{
typedef std::vector<Child_type> victim;
victim _vic;
for(int i = 0; i < Iterations; ++i)
_vic.push_back(Child_type(i, 0));
for(int i = 0; i < Iterations; ++i)
assert((int)_vic[i].size() == i);
}
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);
check01<child>(1024);
check02<child>(1024);
check03<child>(1024);
cout<<endl<<"All Checks Passed!"<<endl<<endl;
//Test-1.
cout<<endl<<"Insertion at the beginning of the vector."<<endl;
test01(iv, 1024);
test01(_ns, 1024);
//Test-2.
cout<<endl<<"Random insertion into the vector:"<<endl;
test02(iv, 1024);
test02(_ns, 1024);
//Test-3.
cout<<endl<<"Insertion at the end of the vector:"<<endl;
test03(iv, 1024);
test03(_ns, 1024);
//Test-4.
cout<<endl<<"Erasing from the beginning of the vector:"<<endl;
test04(iv, 1024);
test04(_ns, 1024);
//Test-6.
cout<<endl<<"Erasing at random positions:"<<endl;
test05(iv, 1024);
test05(_ns, 1024);
//Test-7.
cout<<endl<<"Erasing at the end:"<<endl;
test06(iv, 1024);
test06(_ns, 1024);
}