Proposal for std::vector.

[Stephen M. Webb]

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?

> Even the current vector implements this optimization, but in a
> non-conforming fashion.

Can you explain how it is non-conforming?

> > 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.

> > 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.

> 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:

(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.

-- 
Stephen M. Webb
stephen.webb@bregmasoft.com