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

[Dhruv Matani <dhruvbird at gmx dot net>]

On Thu, 2004-05-27 at 08:27, Carlo Wood wrote:
> On Thu, May 27, 2004 at 07:45:11AM +0530, Dhruv Matani wrote:
> > This is not the full version, because your patch will have to be
> > patched, and the functions will have to be specialized for vector<T>,
> > list<T>, map<T>, etc... where we may assume that.
> 
> Ah, you want to specialize it.  

> But why not do this very every vector?

What do you mean by the above sentence? I can not understand it?


> If you have say, std::vector<Foo>, then that would result in the need
> to std::swap(foo1, foo2).  How is swap implemented for arbitrary objects?
> By calling a copy constructor, an assignment operator and a destructor
> I assume.  Ok, so that would be _slower_ than the current implementation.

Yes. exactly.

> 
> But it would also allow to make it faster.  Consider you have this:
> 
> class Foo {
>   std::vector<double> M_v;
>   // ...
> };
> 
> Then you could speed up growing the capacity of std::vector<Foo>
> considerably by overloading std::swap(Foo, Foo) :).

Yes.

> 
> On the other hand - when we'd demand such 'tricks' from users
> to get the speed or else they'll a slower result even - then
> they might as well specialize std::uninitialized_copy for their
> type themselfs to begin with.

Yes.

However, letting the user not specialize std::swap has 2 advantages:

1. He/she does not have to if they do not. Meaning that their swap
specializations may do something different if they wish, and not perform
a fast swap.

2. Automatic checking for the library implementors. This way, if there
is a bogus swap function(not specialized), then the compiler will
complain of the missing member swap function. In the scenario, when we
ask the user to overload swap, then if he/she does not, then the vector
will still compile, but with a worse performance than the normal case.


> 
> If you go for specializing __uninitialized_copy_swap for only our
> own vector, then note that there is no need to call a constructor
> at all (or swap).  You can just move the three members of the
> vector over and dealloc the old space, in fact - the fastest
> would be to just memcpy the old vector to its new allocation.

That's morally incorrect according to the standard gurus ;-) My
imaginary conscious pinches when I do that!

> No need for default constructors and swap members :/

Actually there is a need:

1. What about list, map, multimap, etc... We would have to use the swap
members for them.
BTW, do you know why list's swap is sooo... complicated. A few months
ago, it was just a swap of the internal pointer.

2. We are implementing this optimization not only for the case when the
vector needs to re-allocate, but also for the normal insertion case.
Consider: 
vector<vector<int> > vv(120);
vv.reserve(150);

vv.insert(begin(), 23);

Here, not re-allocation is needed, because reserve has done it's trick,
but still, the data movement happens just to insert 1 element! This can
be avoided by constructing 1 vector at end(), and performing a
swap_backward algorithm (akin to copy_backward).



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

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