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

[Dhruv Matani <dhruvbird at gmx dot net>]

Hello,
	Ok, I'd like to confirm whether the following functions are indeed the
only ones that would need to be touched:

1. _M_range_insert.
2. _M_fill_insert.
3. _M_insert_aux.
4. erase (both overloads).
5. insert.
6. reserve
7. resize
8. _M_allocate_and_copy.

I can prepare a patch along with a performance test-case if that's
what's required.

Is that fine.



On Sat, 2004-05-29 at 00:00, Dhruv Matani wrote:
> 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