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

[Dhruv Matani <dhruvbird at gmx dot net>]

On Mon, 2004-10-18 at 18:36, Dhruv Matani wrote:
> On Sun, 2004-10-17 at 23:48, Matt Austern wrote:
> > On Oct 17, 2004, at 1:43 AM, Dhruv Matani wrote:
> > 
> > > 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.
> > 
> > We already support allocators where l1.get_allocator() != 
> > l2.get_allocator().  What we don't do is make any special provisions to 
> > detect those allocators in splice() and swap().  (Splice is an issue 
> > for list only, of course, and swap is an issue for all containers.)
> > 
> > There has been longstanding disagreement about what those operations 
> > should mean in the case of non-equal allocators.  [Historical note: 
> > this is one reason that I opposed putting stateful allocators in the 
> > standard at all, back in '95.]  What to do about them is an open 
> > library issue: 
> > http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#431
> > 
> > My favorite solution is that splicing or swapping between containers 
> > with unequal allocators should be undefined behavior.  Howard Hinnant 
> > argues that swap should be defined and should swap both the contents 
> > and the allocators themselves.  (You may notice a potential 
> > complication with that solution...)
> 
> Yes, but for swap() it seems fine.. The problem only seems to creep in
> when we apply the same logic to splice. I'm talking about applying
> solution(3) to swap here.
> 
> Then again for splice we can go with your solution about throwing, but
> undefined behaviour seems a bit harsh to me ;-)
> 
> Then again, since an implementation has the liberty to choose O(N) or
> O(1) size, wherein the complexity requirements for splice change, there,
> they can go with option(2) which you have proposed. However, it
> introduces a new situation wherein splice can throw!
> 
> All this probably out of the scope of this list. Maybe I'll start a
> thread on comp.std?

Ok, I did a bit of googling, and this issue seems to have been discussed
quite widely already, thus not probably mandating another discussion.

The links for everyone's reference are:
http://groups.google.com/groups?q=swap+member+function+containers+swap+allocator&hl=en&lr=&selm=948vq8%24vdf%241%40nnrp1.deja.com&rnum=7
http://groups.google.com/groups?q=swap+member+function+containers+swap+allocator&hl=en&lr=&selm=9a4jtg%243lfso%241%40ID-62495.news.dfncis.de&rnum=3
http://groups.google.com/groups?q=swap+member+function+containers+swap+allocator&hl=en&lr=&selm=gridd-1407011016210001%40modemcable215.92-202-24.mtl.mc.videotron.ca&rnum=9
http://groups.google.com/groups?q=swap+member+function+containers+swap+allocator&hl=en&lr=&selm=XHMbc.30983%24jVF.981%40news04.bloor.is.net.cable.rogers.com&rnum=10
http://groups.google.com/groups?hl=en&lr=&threadm=948vq8%24vdf%241%40nnrp1.deja.com&rnum=7&prev=/groups%3Fq%3Dswap%2Bmember%2Bfunction%2Bcontainers%2Bswap%2Ballocator%26hl%3Den%26lr%3D%26selm%3D948vq8%2524vdf%25241%2540nnrp1.deja.com%26rnum%3D7

Matt, is a resolution forthcoming in the present meeting?

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

The price of freedom is responsibility, but it's a bargain, because
freedom is priceless. ~ Hugh Downs