Proposal for std::vector.

[Dhruv Matani]

On Fri, 2004-02-06 at 20:58, Stephen M. Webb wrote:
> On Friday, February 06 2004 10:09, Dhruv Matani wrote:
> > On Fri, 2004-02-06 at 19:21, Stephen M. Webb wrote:
> > > On Friday, February 06 2004 07:51, Dhruv Matani wrote:
> > > > The relevant discussion can be found by searching google for:
> > > > About std::vector and standard containers in general.
> > > >
> > > >
> > > > Wierd as it may seem, are standard containers such as std::vector
> > > > allowed
> > > > to derive from std::allocator, or more generally from an allocator
> > > > class?
> > >
> > > Some implementations do this.  Vector is the trivial case.  Consider what
> > > you would do with deque and map.
> >
> > Leave them as they are because they would probably not be using
> > stateless allocators.
> 
> 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:

OBJECT SIZE       SIZE PASSED TO ALLOCATE
   4			128 <= int, float, std::string, empty classes, etc...
   8			64 <= double, etc...
  12			42 <= std::vector, etc...
  16			32 <= deque's iterators, etc...

Note: The current std::string implementation very ingeneously makes use
of the EBO for allocators, and also ensures that the size of the string
object does not exceed 4 bytes for an empty allocator!

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



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


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


> I'm not saying it's impossible to base the standard containers on their 
> allocators to take advantage of the EBCO -- I've done it and got it working, 
> for std::list at least.  I'm saying consider the impact in terms of code 
> complexity for those containers (it increases) and readability (it decreases) 
> vs. size or speed advantages (I couldn't measure anything significant).

You have a point there.


> Your results may differ.  I would be pleased to review them.

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:

sizeof(std::vector<int>): 12
sizeof(std::vector<int>::iterator): 4
sizeof(std::deque<int>): 40
sizeof(std::deque<int>::iterator) 16
sizeof(std::list<int>): 8
sizeof(std::list<int>::iterator): 4
sizeof(std::map<int, int>): 24
sizeof(std::map<int, int>::iterator): 4

sizeof(std::vector<double>): 12
sizeof(std::vector<double>::iterator): 4
sizeof(std::deque<double>): 40
sizeof(std::deque<double>::iterator) 16
sizeof(std::list<double>): 8
sizeof(std::list<double>::iterator): 4
sizeof(std::map<double, double>): 24
sizeof(std::map<double, double>::iterator): 4

sizeof(std::string): 4



Suggestion that deque is a very heavy container in terms of size, and
implementing a 2D matrix in terms of a deque would be a very bad idea! 




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