Stateful allocators in libstdc++v [was: Re: Patch: stl_vector.h]

[Dhruv Matani]

On Sun, 2004-10-17 at 00:04, Matt Austern wrote:
> On Oct 16, 2004, at 3:37 AM, Dhruv Matani wrote:
> 
> > On an unrelated note, would we be interested in providing support for
> > stateful allocators in gcc4?
> 
> Don't we provide it already?  Perhaps you mean something by "support 
> for stateful allocators" than I do, but _Vector_base squirrels away a 
> copy of the allocator the user provided, all the allocator operations 
> dispatch to that copy, and get_allocator returns another copy of it.  
> To me that seems like we're preserving and using state.

What I mean is different. ie. allocators which have "state", meaning
that:

allocator1<type> a;
allocator1<type> b;

a == b; // should not necessarily return true.

So, consider:

list<int, stateful_allocator<int> > l1;
list<int, stateful_allocator<int> > l2;

// Now splice should not work when you try to move around objects from
l1 to l2 or vice-versa.

What I am trying to achieve by this is get O(1) size() for list without
having to change the internal implementation. Armed with the knowledge
that the list asks for the nodes from the allocator(this is non-portable
though), I could easily calculate the size in constant time without
using list::size().

Thus, for such allocators, a1 == a2 would return false. Currently, we
make no provision for such things. However we are not mandated to do so
anyways.

> 
> >
> > Also, one more thing that comes to mind is the O(N) complexity of
> > std::list::size(). Should we provide an option of choosing the
> > complexity? I'm asking this because I've found myself using list and
> > then also maintaining a separate counter for fast size lookup.
> 
> I wouldn't be strongly opposed to changing the complexity to O(1)
> (slightly opposed, since it makes other operations slower and I
> think those other operations are more important), 

I agree.

> but I would be
> strongly opposed to making it an option.  Any mechanism I can
> think of for making this a user option would either slow things
> down, or cause compatibility problems, or both.  

Yes, I guess the binary compatibility would be lost.

> We should make
> a definite choice and stick to it.  The wrong choice (whichever
> choice one thinks that is) is better than no choice.
> 
> 			--Matt

I have attached a test case which tries to show what I'm getting at by
bringing in the stateful allocator support.

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

The price of freedom is responsibility, but it's a bargain, because
freedom is priceless. ~ Hugh Downs
-------------- next part --------------
A non-text attachment was scrubbed...
Name: lsize_test.cpp
Type: text/x-c++
Size: 1820 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20041017/9636fc6a/attachment.bin>