Proposal for std::vector.

[Dhruv Matani]

On Fri, 2004-02-06 at 23:15, Stephen M. Webb wrote:
> On Friday, February 06 2004 12:19, Dhruv Matani wrote:
> > On Fri, 2004-02-06 at 20:58, Stephen M. Webb wrote:
> > >
> > > Deque is no less likely to use a stateless allocator than is vector.
> >
> > Yes agreed. However, if the object size for deque exceeds 512 bytes
> > (which is highly unlikely), the complexity of the iterators and the
> > extra space in the nodes would be an overkill. So, for normal operation,
> > deque would call the allocate function with these values:
> 
> [snip]
> 
> In the general case a deque needs two allocators, one for its node list and 
> one for its nodes.  The allocation requirements of its node list allocator 
> are different from those of its nodes.  From which allocator should the deque 
> itself derive?  What do you do with the other allocator?

That is an exception. I guess you will have to have a data member here?
Does anyone have any other ideas?



> > Even the current vector implements this optimization, but in a
> > non-conforming fashion.
> 
> Can you explain how it is non-conforming?

An allocator may contain a virtual clear() function, or for that matter
even a virtual push_back function, and the current vector derives from
vector_base, which in turn derives from the allocator.


> 
> > > Since all the containers use std::allocator by default, unless you're
> > > planning on changing std::allocator to specialize it for the various
> > > standard containers, the "normal" usage for all containers is the same.
> >
> > What do you mean by "normal" uage?
> 
> This is just a guess, but by far the vase majority of usage of standard 
> container do not explicitly specify an allocator, but instead use the default 
> of std::allocator<T> for type T parameterizing the container.  In other 
> words, under the most frequently seen circumstances all containers use the 
> same allocator, and it's either instanceless or instanceful.

But those interseted in fine tuning their app. will use specialized
allocators for different containers.



> > > Consider that all of the associative containers and all of the sequence
> > > containers save std::vector (not specialized for bool) need to rebind
> > > their allocators.
> >
> > They may derive from the rebinded (rebound!) allocators.
> 
> All of their allocators?  I suppose it's possible.  Hairy, but possible.

What is "All of their allocators?"? AFAIK, there is only one allocator
that works (does memory allocation). And the other allocatior is not
even required, because it is not mandated by the standard that a
container use the allocator's construct and destroy functions to copy
construct and destruct objects. It may directly call operator new.



> 
> > I don't have any performance numbers with me as of yet, because I
> > haven't implemented anything of this sort. This is just a discussion
> > about whether it should be done or not. However, I do have these
> > results:
> 
> Here's an idea:  do it and report the results.  Start with vector, that 
> lowliest of beasts, then try list or set (save deque until last, trust me).  
> Metrics I'm interested in include but are not limited to:

libstdc++-v3 already has these optimizations (as I mentioned earlier!)


> (1) Execution speed, say empty creation+destruction, initialized creation
> +destruciton, range insertion, and whole-container copying.  Note that speed 
> can be affected by object size and locality of reference.
> 
> (2) Object code size, at the -O0, -O, and -O2 settings.
> 
> (3) Code metrics like LOC, compile time (with and without precompiled headers)
> 
> Any metric that shows a difference in at least the third significant digit 
> might be worth examining further.
-- 
	-Dhruv Matani.
http://www.geocities.com/dhruvbird/