James Kuyper Jr. <kuyper@wizard.net> wrote:

>> ... In brief, my point is (please ignore what I previously
>> said - it takes me time to distill what I mean) that containers,
>> as an abstract concept, do not (and should not) care about allocators,

> OK. The next question is, why? I think that your claim that they "do not
> .... care" is true to some extent, but only because most containers are
> currently not written to handle allocators that have inequivalent
> instances. However, it seems to me that containers should care about
> allocators, particularly when written to handle ones that allow
> inequivalent instances.

Well, the allocators in and of themselves are a reflection of limitations
of the operating environment: limited amount of memory (that's why
we want short lifetime memory pools), limited memory performance
(that's why we want locality-optimized allocators), or limited
memory persistence (that's why we need special handling
for the objects that need to persist across processes). (Did I
miss anything?) But all that is beyond the scope of the concept
of a container, and I believe that bringing any additional
allocator-related semantics (i.e. abolishing 20.1.5.4req1)
into the objects that represent containers is not needed. What
I would want instead is to abstract the concept of a pointer
(i.e. to abolish 20.1.5.4req2) and require all standard containers
to use Allocator<T>::pointer wherever T* is needed, etc. Think
shorter (based) pointers, allowing for memory-efficient
implementations of std::set and std::map.

> In your reply to Kevin S. Van Horn you claimed that treating the
> allocator as part of the container's state is error prone. It's
> certainly error prone, if you aren't expecting it to be treated as part
> of the state. However, I don't think you've established the case that it
> would be more error-prone than the alternative would be, when used by
> developers who expect the container to treat the allocator whichever way
> it actually does treat it.

Maybe. What, again, is a compelling argument in favor of
allowing inequivalent allocator instances?

 Leo

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

xleobx@qmailcomq.com wrote:
>
> James Kuyper Jr. <kuyper@wizard.net> wrote:
....
> > In your reply to Kevin S. Van Horn you claimed that treating the
> > allocator as part of the container's state is error prone. It's
> > certainly error prone, if you aren't expecting it to be treated as part
> > of the state. However, I don't think you've established the case that it
> > would be more error-prone than the alternative would be, when used by
> > developers who expect the container to treat the allocator whichever way
> > it actually does treat it.
>
> Maybe. What, again, is a compelling argument in favor of
> allowing inequivalent allocator instances?

I hadn't realized you were arguing against that feature. The
prototypical example of an allocator type with inequivalent instances,
is one where each independently constructed instance of the allocator
manages a seperate pool of memory. Generically, it would seem there
would have to be some situation where that feature would be useful, but
I don't claim to know of any. I'm fascinated by the concept of
allocators with inequivalent instances, mainly because dealing with them
properly imposes so many interesting complications for the
implementations of containers, not because I have any actual use for
them. They are either an appalling wart on the concept of allocators, or
a powerful extension to the concept, but I'm not sure which - possibly
they're both. :-)

The standard specifies what a==b means for Allocators, and of course
support for inequivalent instances is encouraged in 20.1.5p5, so a fair
number of people on the committee must have thought it was worthwhile to
allow for a==b to be false. Would anyone care to explain why?

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Kevin S. Van Horn <kevin_vanhorn@ndsu.nodak.edu> wrote:
> xleobx@qmailcomq.com wrote in message news:<zrIu8.6902$T_.147885@iad-read.news.verio.net>...

>> See the original post. In this example I pretended that the model
>> is modified as to allow an allocator to be a variable part of the
>> object - that's what the original poster wanted.

> I'm the original poster, and you're wrong about what I wanted.  The
> whole discussion is about what behavior we should have with assignment
> and swap if you have an allocator type where all instances do not have
> identical behavior (e.g., due to internal state).

Sorry I misunderstood you.

> As Plauger pointed out, although standard
> containers are not required to support such allocators, if a standard
> library implementer chooses to support such allocators, the standard
> prescribes that a standard library container always use the allocator
> with which it was created.  In such a case, you *do* have allocator
> state as part of an object's state, but this is state that cannot be
> modified.  THIS is where my objection is.  Assignment and swap should
> affect *all* of an object's state, not just part.

Says who? They are defined on _containers_, represented by the objects,
and they both do affect all of a container's state, whereas the allocator
is not part of a container's state, but an immutable property, represented
by a part of an object's state.

The point I tried to make is that treating the allocator as part of
a container's state is error-prone.

 Leo

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

James Kuyper Jr. <kuyper@wizard.net> wrote:

> I assumed that what we're discussing are containers using Allocators
> with inequivalent instances; otherwise, there's not much point in caring
> whether or not they get exchanged. You indicated that you felt that the
> correct topic was containers "where an allocator may be part of the
> state". I'm not sure I understand what that could mean, other than being
> another way of saying essentially the same thing. However, you gave it
> as a correction, so you apparantly feel that they're not the same. In
> which direction was the correction intended? Do you think there's a
> container that fits your description, but not mine? Do you think there's
> a container that fits my description, but not yours? Please elaborate.

I do not want to fork the thread, so please refer to my answer to
Kevin S. Van Horn. In brief, my point is (please ignore what I previously
said - it takes me time to distill what I mean) that containers,
as an abstract concept, do not (and should not) care about allocators,
so, even if an instance of an allocator is a part of an object
that represents a container (and therefore
is a part of the object's state), that instance is not a part
of the container's state, and therefore should be
immune from the operations "assign container" and "swap container".

 Leo

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

xleobx@qmailcomq.com wrote:
....
> I do not want to fork the thread, so please refer to my answer to
> Kevin S. Van Horn. ...

I'm answering here, rather than on that branch, because more of my reply
concerns the following statement, than anything you said in that
message.

> ... In brief, my point is (please ignore what I previously
> said - it takes me time to distill what I mean) that containers,
> as an abstract concept, do not (and should not) care about allocators,

OK. The next question is, why? I think that your claim that they "do not
.... care" is true to some extent, but only because most containers are
currently not written to handle allocators that have inequivalent
instances. However, it seems to me that containers should care about
allocators, particularly when written to handle ones that allow
inequivalent instances.

In your reply to Kevin S. Van Horn you claimed that treating the
allocator as part of the container's state is error prone. It's
certainly error prone, if you aren't expecting it to be treated as part
of the state. However, I don't think you've established the case that it
would be more error-prone than the alternative would be, when used by
developers who expect the container to treat the allocator whichever way
it actually does treat it.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

James Kuyper Jr. <kuyper@wizard.net> wrote:

>> Maybe. What, again, is a compelling argument in favor of
>> allowing inequivalent allocator instances?

> I hadn't realized you were arguing against that feature. The
> prototypical example of an allocator type with inequivalent instances,
> is one where each independently constructed instance of the allocator
> manages a seperate pool of memory. Generically, it would seem there

Currently I do it with a type templated by (magic) integers
(when all compilers that we use support global variables as templates,
I'll use global variables instead).

> would have to be some situation where that feature would be useful, but
> I don't claim to know of any. I'm fascinated by the concept of
> allocators with inequivalent instances, mainly because dealing with them
> properly imposes so many interesting complications for the
> implementations of containers, not because I have any actual use for
> them. They are either an appalling wart on the concept of allocators, or
> a powerful extension to the concept, but I'm not sure which - possibly
> they're both. :-)

I'll agree.

> The standard specifies what a==b means for Allocators, and of course
> support for inequivalent instances is encouraged in 20.1.5p5, so a fair

2.1.5p4 says "it's OK to cut corners"; 2.1.5p5 says "you're encouraged
not to cut corners". Guess what will the commercial implementors do?

> number of people on the committee must have thought it was worthwhile to
> allow for a==b to be false. Would anyone care to explain why?

I'm more interested in seeing an explanation of 2.1.5p4/2. I am really
annoyed by it, having to port software to a 64-bit platform.

 Leo

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

xleobx@qmailcomq.com wrote:
>
> James Kuyper Jr. <kuyper@wizard.net> wrote:
....
> > The standard specifies what a==b means for Allocators, and of course
> > support for inequivalent instances is encouraged in 20.1.5p5, so a fair
>
> 2.1.5p4 says "it's OK to cut corners"; 2.1.5p5 says "you're encouraged
> not to cut corners". Guess what will the commercial implementors do?

Both. Most will cut corners, a few will probably experiment. Which is
precisely what the committee wanted. The next version of the standard
should contian a more detailed specification of the semantics. The
committee wanted a few implementations to experiment with the concept,
to build up the experience need to help decide what those specifications
should say.

....
> I'm more interested in seeing an explanation of 2.1.5p4/2. I am really
> annoyed by it, having to port software to a 64-bit platform.

Could you explain that in more detail?

By the way, it's 20.1.5, not 2.1.5.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

James Kuyper Jr. <kuyper@wizard.net> wrote:

>> 2.1.5p4 says "it's OK to cut corners"; 2.1.5p5 says "you're encouraged
>> not to cut corners". Guess what will the commercial implementors do?

> Both. Most will cut corners, a few will probably experiment. Which is
> precisely what the committee wanted. The next version of the standard
> should contian a more detailed specification of the semantics. The
> committee wanted a few implementations to experiment with the concept,
> to build up the experience need to help decide what those specifications
> should say.

Maybe; but more likely, esp. re: 20.1.5p4/2, because rebinding did not
work in many compilers yet.

> ....
>> I'm more interested in seeing an explanation of 2.1.5p4/2. I am really
>> annoyed by it, having to port software to a 64-bit platform.

> Could you explain that in more detail?

std::set and std::map, as specified in the standard, pretty much require a
pointer-heavy implementation. Porting an application that uses them
actively, from a 32-bit platform to a 64-bit platform on the same hardware
will reduce the effective memory cache size in half (what used to
take 4 bytes, now takes 8), therefore reducing performance by an
unpredictable amount.

Without 20.1.5p4/2 there would have been some recourse: specifying
std::set<T, ..., based_ptr_allocator<T> > where, roughly speaking,
sizeof(based_ptr_allocator<T>::pointer) == 4, so that the size
of the set nodes will be the same as before, allowing for more
graceful performance degradation. But now the compiler is
allowed to cut corners, so, no matter what the allocator is,
std::set still uses native pointers for its internal purposes.

> By the way, it's 20.1.5, not 2.1.5.

Sorry, a persistent typo.

 Leo

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

James Kuyper Jr. <kuyper@wizard.net> wrote:

> I'm unclear what it is you mean there. If all instances of an allocator
> type are equivalent, even if they are part of the state (whatever you
> mean by that), then any one of those instances may freely be used to
> deallocate memory allocated by one of the other instances (see table 31,
> the entry of == ). I don't see that there's any reason, in that case, to
> worry about which instance you're using.

I believe we diverged on what we're trying to discuss. I'm trying to
make a point that no matter how the allocation strategies are associated
with an object, allowing a non-identity modification of the allocation
strategy may have unintended results, and I have not seen a compelling
usage of the 'on-the-fly' modification of the allocation strategy.

>> void foo() {
>>     ShortAlloc<int>::init();
>>     {
>>         vector<int> b(ShortAlloc<int>());
>>         ...
>>         a.swap(b);
>>     }
>>     ShortAlloc<int>::fini();
>> }
>>
>> ....and the fact that `a' points to the dead storage goes unnoticed.

> a and b have different types. 'a' has the type
> std::vector<int,std::allocator<int> >, while b has the type
> std::vector<int,ShortAlloc<int> >. Table 65 only requires a.swap(b) to
> work when 'a' and 'b' have the same type. The only signature required by
> the standard for std::vector<T,Allocator>.swap() is one that takes a
> std::vector<T,Allocator>& argument (23.2.4.2). An implementation is free
> to add an overload that accepts other arguments (17.4.4.4), but the
> behavior of that overload is not governed by the C++ standard, except
> insofar as it must not interfere with legal calls to swap().

See the original post. In this example I pretended that the model
is modified as to allow an allocator to be a variable part of the
object - that's what the original poster wanted.

 Leo

> ---
> [ comp.std.c++ is moderated.  To submit articles, try just posting with ]
> [ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
> [              --- Please see the FAQ before posting. ---               ]
> [ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]


--
*** Lifelike Entity Optimized for Nocturnal Infiltration and Destruction
aka Leonid

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

xleobx@qmailcomq.com wrote:
>
> James Kuyper Jr. <kuyper@wizard.net> wrote:
>
> > I'm unclear what it is you mean there. If all instances of an allocator
> > type are equivalent, even if they are part of the state (whatever you
> > mean by that), then any one of those instances may freely be used to
> > deallocate memory allocated by one of the other instances (see table 31,
> > the entry of == ). I don't see that there's any reason, in that case, to
> > worry about which instance you're using.
>
> I believe we diverged on what we're trying to discuss. I'm trying to
> make a point that no matter how the allocation strategies are associated
> with an object, allowing a non-identity modification of the allocation
> strategy may have unintended results, and I have not seen a compelling
> usage of the 'on-the-fly' modification of the allocation strategy.

I assumed that what we're discussing are containers using Allocators
with inequivalent instances; otherwise, there's not much point in caring
whether or not they get exchanged. You indicated that you felt that the
correct topic was containers "where an allocator may be part of the
state". I'm not sure I understand what that could mean, other than being
another way of saying essentially the same thing. However, you gave it
as a correction, so you apparantly feel that they're not the same. In
which direction was the correction intended? Do you think there's a
container that fits your description, but not mine? Do you think there's
a container that fits my description, but not yours? Please elaborate.

It seems to me that exchange of equivalent allocator instances qualifies
as an identity modification, and NOT as a modification of the allocation
strategy. The exchange of inequivalent instances wouldn't qualify as a
change of allocation strategy, since the strategy is determined by the
allocator type, which would remain unchanged by such an exchange.

....
> > a and b have different types. 'a' has the type
> > std::vector<int,std::allocator<int> >, while b has the type
> > std::vector<int,ShortAlloc<int> >. Table 65 only requires a.swap(b) to
> > work when 'a' and 'b' have the same type. The only signature required by
> > the standard for std::vector<T,Allocator>.swap() is one that takes a
> > std::vector<T,Allocator>& argument (23.2.4.2). An implementation is free
> > to add an overload that accepts other arguments (17.4.4.4), but the
> > behavior of that overload is not governed by the C++ standard, except
> > insofar as it must not interfere with legal calls to swap().
>
> See the original post. In this example I pretended that the model
> is modified as to allow an allocator to be a variable part of the
> object - that's what the original poster wanted.

I've looked at the original post. Nothing he said implied allowing the
allocator's type to be variable, only the allocator instance. That
requires no new signatures for swap(); the existing one is sufficient.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

xleobx@qmailcomq.com wrote in message news:<zrIu8.6902$T_.147885@iad-read.news.verio.net>...

> > a and b have different types. 'a' has the type
> > std::vector<int,std::allocator<int> >, while b has the type
> > std::vector<int,ShortAlloc<int> >. Table 65 only requires a.swap(b) to
> > work when 'a' and 'b' have the same type. The only signature required by
> > the standard for std::vector<T,Allocator>.swap() is one that takes a
> > std::vector<T,Allocator>& argument (23.2.4.2). An implementation is free
> > to add an overload that accepts other arguments (17.4.4.4), but the
> > behavior of that overload is not governed by the C++ standard, except
> > insofar as it must not interfere with legal calls to swap().
>
> See the original post. In this example I pretended that the model
> is modified as to allow an allocator to be a variable part of the
> object - that's what the original poster wanted.

I'm the original poster, and you're wrong about what I wanted.  The
whole discussion is about what behavior we should have with assignment
and swap if you have an allocator type where all instances do not have
identical behavior (e.g.,
due to internal state).  As Plauger pointed out, although standard
containers are not required to support such allocators, if a standard
library implementer chooses to support such allocators, the standard
prescribes that a standard library container always use the allocator
with which it was created.  In such a case, you *do* have allocator
state as part of an object's state, but this is state that cannot be
modified.  THIS is where my objection is.  Assignment and swap should
affect *all* of an object's state, not just part.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

James Kuyper Jr. <kuyper@wizard.net> wrote:

>> int a = 5;      // allocation strategy: data segment
>> void foo() {
>>         int b;  // allocation strategy: stack
>>         b = a;
>>         ...
>> }
>>
>> Are you surprized that `b' dies at the end of foo()? I don't think so.
>> Why should other objects be any different? Allocation strategy is
>> presumed to be a part of an object's type, not part of an object's state.

> a and b have the same type, yet different allocation strategies. I think

One can say (loosely) that `a' is actually `extern int',
whereas `b' is `auto int'.

> you've chosen a bad example.

Which shows, nevertheless, that allocation strategy is not port of an
object's state.

> Note: it doesn't matter whether containers swaps allocators, if all such
> instances are equivalent. Therefore, I'm assuming that this discussion

Yes, as far they are of the same type.

> is specifically about Allocators with inequivalent instances. It must

Or, rather, where an allocator may be made a part of the state.

> What does change when swap() exchanges inequivalent allocators along
> with the rest of the container's contents, is the set of objects that
> can be deallocated. I think we can safely presume that a container
> should always be able to deallocate it's own contents.

Also it should always be able to ensure the lifetime of its contents, right?
But if objects are allowed to exchange allocators freely, a long-lived
object can get an allocator for short-lived memory.

> If swap() does swap allocators, then it can be a constant-time
> operation, and satisfy 23.1p10, without using heavy pointers. I consider
> this a very strong argument in favor of swapping the allocators.
> However, because of 20.1.5p5, I can't actually claim that this is
> required.

Yes, it can, but it will wreak havoc, akin to returning pointers to
stack or temporaries, that is much harder to debug.

>> Memory management will be a nightmare. Memory pools tend to have limited
>> lifetime. If the allocators can be swapped or assigned, you hardly can
>> be sure if there are no references to an allocator whose memory pool
>> is about to go away, from objects that you have no control over.

> I'm afraid I don't follow that. I've never seen code that uses
> allocators with inequivalent instances; support for them is
> experimental, and I've never seen one of the experiments. When you
> swap() the contents of two containers, all iterators, pointers, and
> references to elements of the first container become iterators,
> pointers, and references to elements of the second container. That's
> only possible interpretation of the validity requirement - they can't
> become iterators pointing at the corresponding element of the original
> container, because the two containers might have different numbers of
> elements - there might not be a corresponding element, and such
> iterators/pointers/references could not possibly remain valid.

This is not what I meant. Assume the allocator is a part of an object's state,
the syntax is for demonstration only.

template<class T> class ShortAlloc ....

vector<int> a; // with the default allocator

void foo() {
    ShortAlloc<int>::init();
    {
 vector<int> b(ShortAlloc<int>());
 ...
 a.swap(b);
    }
    ShortAlloc<int>::fini();
}

....and the fact that `a' points to the dead storage goes unnoticed.
The current implementation does not allow this to happen, and the reasons
to allow it should be quite compelling.

 Leo

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

xleobx@qmailcomq.com wrote:
>
> James Kuyper Jr. <kuyper@wizard.net> wrote:
>
> >> int a = 5;      // allocation strategy: data segment
> >> void foo() {
> >>         int b;  // allocation strategy: stack
> >>         b = a;
> >>         ...
> >> }
> >>
> >> Are you surprized that `b' dies at the end of foo()? I don't think so.
> >> Why should other objects be any different? Allocation strategy is
> >> presumed to be a part of an object's type, not part of an object's state.
>
> > a and b have the same type, yet different allocation strategies. I think
>
> One can say (loosely) that `a' is actually `extern int',
> whereas `b' is `auto int'.

Which means that they have the same type, but different storage classes.

....
> > Note: it doesn't matter whether containers swaps allocators, if all such
> > instances are equivalent. Therefore, I'm assuming that this discussion
>
> Yes, as far they are of the same type.

Containers can only legally swap() if they have the same type. All of
the standard-defined container types, (which are the only container
types for which the standard says anything about allocators) are
templated by Allocator type, so they can only swap() if they have the
same Allocator type.

> > is specifically about Allocators with inequivalent instances. It must
>
> Or, rather, where an allocator may be made a part of the state.

I'm unclear what it is you mean there. If all instances of an allocator
type are equivalent, even if they are part of the state (whatever you
mean by that), then any one of those instances may freely be used to
deallocate memory allocated by one of the other instances (see table 31,
the entry of == ). I don't see that there's any reason, in that case, to
worry about which instance you're using.

> > What does change when swap() exchanges inequivalent allocators along
> > with the rest of the container's contents, is the set of objects that
> > can be deallocated. I think we can safely presume that a container
> > should always be able to deallocate it's own contents.
>
> Also it should always be able to ensure the lifetime of its contents, right?
> But if objects are allowed to exchange allocators freely, a long-lived
> object can get an allocator for short-lived memory.

I don't understand what you're saying. You've got two instances of the
same allocator type, one of which has a different  lifetime than the
other. I'd say that code which terminates the lifetime of an the memory
allocated using a given allocator instance, while that allocator
instance is still in use by a container, is defective. It's not clear to
me that there's any special problem with avoiding such code. Your
example below doesn't qualify, for the reasons I give below.

> > If swap() does swap allocators, then it can be a constant-time
> > operation, and satisfy 23.1p10, without using heavy pointers. I consider
> > this a very strong argument in favor of swapping the allocators.
> > However, because of 20.1.5p5, I can't actually claim that this is
> > required.
>
> Yes, it can, but it will wreak havoc, akin to returning pointers to
> stack or temporaries, that is much harder to debug.

I don't follow that. Can you provide an example?

....
> > I'm afraid I don't follow that. I've never seen code that uses
> > allocators with inequivalent instances; support for them is
> > experimental, and I've never seen one of the experiments. When you
> > swap() the contents of two containers, all iterators, pointers, and
> > references to elements of the first container become iterators,
> > pointers, and references to elements of the second container. That's
> > only possible interpretation of the validity requirement - they can't
> > become iterators pointing at the corresponding element of the original
> > container, because the two containers might have different numbers of
> > elements - there might not be a corresponding element, and such
> > iterators/pointers/references could not possibly remain valid.
>
> This is not what I meant. Assume the allocator is a part of an object's state,
> the syntax is for demonstration only.
>
> template<class T> class ShortAlloc ....
>
> vector<int> a;  // with the default allocator
>
> void foo() {
>     ShortAlloc<int>::init();
>     {
>         vector<int> b(ShortAlloc<int>());
>         ...
>         a.swap(b);
>     }
>     ShortAlloc<int>::fini();
> }
>
> ....and the fact that `a' points to the dead storage goes unnoticed.

a and b have different types. 'a' has the type
std::vector<int,std::allocator<int> >, while b has the type
std::vector<int,ShortAlloc<int> >. Table 65 only requires a.swap(b) to
work when 'a' and 'b' have the same type. The only signature required by
the standard for std::vector<T,Allocator>.swap() is one that takes a
std::vector<T,Allocator>& argument (23.2.4.2). An implementation is free
to add an overload that accepts other arguments (17.4.4.4), but the
behavior of that overload is not governed by the C++ standard, except
insofar as it must not interfere with legal calls to swap().

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

xleobx@qmailcomq.com wrote:
>
> James Kuyper Jr. <kuyper@wizard.net> wrote:
>
> >> You get to determine what allocation strategy goes with each object.
> >> It doesn't change in surprising ways as the result of swaps and
> >> assignments.
>
> > That depends upon what suprises you. I'd be surprised if the allocation
> > strategy was NOT swapped or assigned along with the rest of the object.
>
> int a = 5;      // allocation strategy: data segment
> void foo() {
>         int b;  // allocation strategy: stack
>         b = a;
>         ...
> }
>
> Are you surprized that `b' dies at the end of foo()? I don't think so.
> Why should other objects be any different? Allocation strategy is
> presumed to be a part of an object's type, not part of an object's state.

a and b have the same type, yet different allocation strategies. I think
you've chosen a bad example.

In any event, you're correct; for the containers defined by the
standard, allocation is a part of the object's type. I made a mistake -
I normally try to retain the wording of the message I reply to, in order
to make it clear what I was referring to. It was Plauger who first said
"allocation strategy", and I copied that wording without even thinking
about it. However, if swap() were to swap allocator instances along with
the rest of the contents of the container, then it would NOT result in a
change of allocation strategy. That strategy is determined by the
allocator's type, not by the allocator itself. Two containers that use
different Allocator types have different container types, and therefore
are not required to be able to swap() with each other (that ability
could be provided as an extension, with implmentation-defined
semantics).

Note: it doesn't matter whether containers swaps allocators, if all such
instances are equivalent. Therefore, I'm assuming that this discussion
is specifically about Allocators with inequivalent instances. It must
also be restricted to implementations that choose to implement
containers that allow such allocators. Such support is optional, but
encouraged, by section 20.1.5p5. That section essentially leaves it
entirely up to the implementor what rules apply to such containers,
which makes it basically impossible to talk about what is required by
the standard. Therefore, I assume we're only talking about what should
be requiered, when the standard finally adopts more specific rules for
such containers.

What does change when swap() exchanges inequivalent allocators along
with the rest of the container's contents, is the set of objects that
can be deallocated. I think we can safely presume that a container
should always be able to deallocate it's own contents. If swap() didn't
swap allocators, then whenever two containers had inequivalent
allocators, it would have to allocate new memory, and copy over the
elements of the other container into that memeory. That would take time
proportional to the number of elements, and would invalidate all
references, pointers, or iterators to the elements in their old
locations. According to table 65, swap() "Should have constant
complexity". and and according to 23.1p10, "no swap() function
invalidates any references, pointers, or iterators referring to the
elements of the containters being swapped." There are ways around this,
but the only ones I can thing of require heavy iterators.

If swap() does swap allocators, then it can be a constant-time
operation, and satisfy 23.1p10, without using heavy pointers. I consider
this a very strong argument in favor of swapping the allocators.
However, because of 20.1.5p5, I can't actually claim that this is
required.

As I mentioned earlier, splice() is a different issue - there's no way I
can see to meet to complexity requirements on splice() when using
inequivalent allocators. But that remains true, whether the allocators
are exchanged or kept in place.

> > If the allocators were swap()d, along with the rest of the container's
> > contents, there'd be no need for reallocation. splice() is the only case
> > where reallocation would be needed when using an allocator with
> > inequivalent instances.
>
> Memory management will be a nightmare. Memory pools tend to have limited
> lifetime. If the allocators can be swapped or assigned, you hardly can
> be sure if there are no references to an allocator whose memory pool
> is about to go away, from objects that you have no control over.

I'm afraid I don't follow that. I've never seen code that uses
allocators with inequivalent instances; support for them is
experimental, and I've never seen one of the experiments. When you
swap() the contents of two containers, all iterators, pointers, and
references to elements of the first container become iterators,
pointers, and references to elements of the second container. That's
only possible interpretation of the validity requirement - they can't
become iterators pointing at the corresponding element of the original
container, because the two containers might have different numbers of
elements - there might not be a corresponding element, and such
iterators/pointers/references could not possibly remain valid.

Therefore, any algorithm that uses such iterators, pointers, or
references across a swap() between two containers, must either not care
about which of the two containers each one points into, or it must keep
track of the fact that the container they point into has changed.
Therefore, so long as the allocator stored in a given container can
deallocate the elements of that container, I don't see why there's be
any special problem.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"P.J. Plauger" <pjp@dinkumware.com> wrote:

> However it may seem to you, we did discuss this within the committee.
> An allocator for a container is fixed at construction (to the extent that
> you can tell).

Why in the world was such a decision made?  What benefit is there from
such
a choice?  I've already mentioned one great disadvantage of such an
approach:
swap is needlessly complicated and made expensive in some
circumstances.
Another disadvantage is that this choice violates the principle of
least surprise.  One generally expects that after executing "x = y",
then x and y
are identical in all ways that affect their subsequent behavior (with
the exception of addresses of the objects and their constituent
parts).  A similar
comment holds for swap.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Kevin S. Van Horn" <kevin_vanhorn@ndsu.nodak.edu> wrote in message
news:42aba677.0204051121.59ee7aca@posting.google.com...

> > However it may seem to you, we did discuss this within the committee.
> > An allocator for a container is fixed at construction (to the extent that
> > you can tell).
>
> Why in the world was such a decision made?  What benefit is there from such
> a choice?

You get to determine what allocation strategy goes with each object.
It doesn't change in surprising ways as the result of swaps and
assignments.

>          I've already mentioned one great disadvantage of such an approach:
> swap is needlessly complicated and made expensive in some circumstances.

The circumstances are exactly when it might be wise to reallocate copied
elements, because they have to live in a different memory pool.

> Another disadvantage is that this choice violates the principle of
> least surprise.  One generally expects that after executing "x = y", then x and y
> are identical in all ways that affect their subsequent behavior (with
> the exception of addresses of the objects and their constituent parts).  A similar
> comment holds for swap.

I think you can argue least surprise either way.

BTW, I'm not in love with the particular choice made in the C++ Standard,
but I accept it as reasonable.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"P.J. Plauger" wrote:
>
> "Kevin S. Van Horn" <kevin_vanhorn@ndsu.nodak.edu> wrote in message
> news:42aba677.0204051121.59ee7aca@posting.google.com...
>
> > > However it may seem to you, we did discuss this within the committee.
> > > An allocator for a container is fixed at construction (to the extent that
> > > you can tell).
> >
> > Why in the world was such a decision made?  What benefit is there from such
> > a choice?
>
> You get to determine what allocation strategy goes with each object.
> It doesn't change in surprising ways as the result of swaps and
> assignments.

That depends upon what suprises you. I'd be surprised if the allocation
strategy was NOT swapped or assigned along with the rest of the object.

> >          I've already mentioned one great disadvantage of such an approach:
> > swap is needlessly complicated and made expensive in some circumstances.
>
> The circumstances are exactly when it might be wise to reallocate copied
> elements, because they have to live in a different memory pool.

If the allocators were swap()d, along with the rest of the container's
contents, there'd be no need for reallocation. splice() is the only case
where reallocation would be needed when using an allocator with
inequivalent instances.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

James Kuyper Jr. <kuyper@wizard.net> wrote:

>> You get to determine what allocation strategy goes with each object.
>> It doesn't change in surprising ways as the result of swaps and
>> assignments.

> That depends upon what suprises you. I'd be surprised if the allocation
> strategy was NOT swapped or assigned along with the rest of the object.

int a = 5; // allocation strategy: data segment
void foo() {
 int b; // allocation strategy: stack
 b = a;
 ...
}

Are you surprized that `b' dies at the end of foo()? I don't think so.
Why should other objects be any different? Allocation strategy is
presumed to be a part of an object's type, not part of an object's state.

> If the allocators were swap()d, along with the rest of the container's
> contents, there'd be no need for reallocation. splice() is the only case
> where reallocation would be needed when using an allocator with
> inequivalent instances.

Memory management will be a nightmare. Memory pools tend to have limited
lifetime. If the allocators can be swapped or assigned, you hardly can
be sure if there are no references to an allocator whose memory pool
is about to go away, from objects that you have no control over.

 Leo

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"James Kuyper Jr." wrote:
>
> "P.J. Plauger" wrote:
> >
> > You get to determine what allocation strategy goes with each object.
> > It doesn't change in surprising ways as the result of swaps and
> > assignments.
>
> That depends upon what suprises you. I'd be surprised if the allocation
> strategy was NOT swapped or assigned along with the rest of the object.
>

Thus demonstrating why "the principle of least surprise" is not a useful
design criterion.

--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Suppose that C is any container class defined in the standard library,
and I have

C x(...);
C y(...);
...
x = y;

The implementation of STL in Plauger, Stepanov, Lee, and Musser's book
assumes that x should have its sequence of elements updated, but *not*
its allocator.  This seems wrong to me.  I would expect x to also get
y's allocator.  Similarly, if I do

x.swap(y);

I would expect allocators to get swapped too; PSLM's book assumes that
the allocators do *not* get swapped, and that one therefore has to do
an expensive copy operation if x and y do not have the same allocator
value.

As I understand it, the standard says that standard containers assume
that all instances of a particular allocator type are identical, and
so the above issues are moot; the PSLM implementation is an attempt to
experiment with extensions to allow distinct allocators of the same
type.  However, does the standard provide any guidance as to whether
swap() and operator=() should update the allocator in such extensions?

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Kevin S. Van Horn" <kevin_vanhorn@ndsu.nodak.edu> wrote in message
news:42aba677.0203291151.ff4f74c@posting.google.com...

> Suppose that C is any container class defined in the standard library,
> and I have
>
> C x(...);
> C y(...);
> ...
> x = y;
>
> The implementation of STL in Plauger, Stepanov, Lee, and Musser's book
> assumes that x should have its sequence of elements updated, but *not*
> its allocator.  This seems wrong to me.  I would expect x to also get
> y's allocator.

However it may seem to you, we did discuss this within the committee.
An allocator for a container is fixed at construction (to the extent that
you can tell). There are some subtle traces of this decision, such as in
23.1:

: In all container types defined in this clause, the member
: get_allocator() returns a copy of the Allocator object used
: to construct the container.

I know there are others, but I forget where at the moment.

>               Similarly, if I do
>
> x.swap(y);
>
> I would expect allocators to get swapped too; PSLM's book assumes that
> the allocators do *not* get swapped, and that one therefore has to do
> an expensive copy operation if x and y do not have the same allocator
> value.

Correct.

> As I understand it, the standard says that standard containers assume
> that all instances of a particular allocator type are identical, and
> so the above issues are moot;

No, the C++ Standard says that standard containers ARE PERMITTED TO
ASSUME that all allocators compare equal. See 20.1.5:

: Implementations of containers described in this International Standard
: are permitted to assume that their Allocator template parameter meets the
: following two additional requirements beyond those in Table 32.
:
: - All instances of a given allocator type are required to be interchangeable
: and always compare equal to each other.
:
: - The typedef members pointer, const_pointer, size_type, and difference_type
: are required to be T*, T const*, size_t, and ptrdiff_t, respectively.
:
: Implementors are encouraged to supply libraries that can accept allocators
: that encapsulate more general memory models and that support non-equal
: instances. In such implementations, any requirements imposed on allocators
: by containers beyond those requirements that appear in Table 32, and the
: semantics of containers and algorithms when allocator instances compare
: non-equal, are implementation-defined.

>                            the PSLM implementation is an attempt to
> experiment with extensions to allow distinct allocators of the same
> type.

It's an attempt to deliver what the C++ Standard ENCOURAGES.

>       However, does the standard provide any guidance as to whether
> swap() and operator=() should update the allocator in such extensions?

I think so, yes.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]