This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: About std::vector::resize().
Hello,
Here is the initial testing patch.
You will have to manually add the patched file stl_type_traits.h to the
include/bits directory for testing purposes, because I do not know how
to write makefiles ;-(
Here are the numbers for the extreme test-case for the patched and
un-patched vector. The test-case is attached.
*******PATCHED**********
[dhruv@localhost test]$ compile vec_vec_test.cpp v4 -O3
The Compiler command passed is: g++34 -Wall -O3 -o vec_vec_test
vec_vec_test.cpp
[dhruv@localhost test]$ ./vec_vec_test
[dhruv@localhost test]$ time ./vec_vec_test
real 0m0.525s
user 0m0.400s
sys 0m0.120s
*******UN_PATCHED*********
[dhruv@localhost test]$ compile vec_vec_test.cpp -O3
The Compiler command passed is: g++ -Wall -O3 -o vec_vec_test
vec_vec_test.cpp
[dhruv@localhost test]$ time ./vec_vec_test
real 1m40.819s
user 1m30.410s
sys 0m0.120s
On Sat, 2004-05-29 at 13:32, Paolo Carlini wrote:
> Dhruv Matani wrote:
>
> >Thanks ;-)
> >
> >Actually, this patch is because of my own selfish needs. I use currently
> >std::vector<std::vector<char> > very heavily in a file processing app.
> >of mine, and figured that would help with this optimization, so I
> >thought about it.
> >
> >
> That's ok... provided the final result doesn't apply only to
> vector<vector>>, of
> course... ;) ;)
>
> Paolo.
--
-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-05-29 23:50:46.000000000 +0530
***************
*** 0 ****
--- 1,43 ----
+ // -*- C++ -*-
+
+ namespace std
+ {
+ template<typename, typename>
+ class vector;
+
+ template<typename, typename>
+ class list;
+
+ template<typename, typename>
+ class deque;
+ }
+
+ 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;
+ };
+ }
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-05-29 23:50:40.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
*** 902,907 ****
--- 928,941 ----
// 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-05-29 23:50: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,299 ****
--- 428,442 ----
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(iterator __position, size_type __n, const value_type& __x)
{
if (__n != 0)
#include <vector>
#include <iostream>
using namespace std;
int main()
{
//Test-1.
//Create a vector of vector of ints. Each of size 1024, and
//containing 10 ints. Thus, the total space occupied should be
//1024*1024*sizeof(int)*10 bytes.
typedef std::vector<int> child;
typedef std::vector<child> victim;
victim ivv;
child iv(10240, 23);
for (int i = 0; i < 1024; ++i)
ivv.insert(ivv.begin(), iv);
//ivv.push_back(iv);
victim::iterator i = ivv.begin();
int tmp = 0;
while (i != ivv.end())
tmp = i++-ivv.begin();
}