operator= in allocators

[Mark A. Gibbs]

I'm having yet another headache with making a standard allocator. What
behaviour should be expected from the assigment operator? When would it
be called? Why is it there at all, when you can't change allocators in
containers?

To give a little more depth, I have a class like this:

class HeapAllocator
{
// All requirements of the allocator interface are met along with:
// - A constructor to pass in a heap reference
// - A GetHeap function that returns a reference to the internal heap
// (which can never be 0)

private:
mutable Heap* heap_;
};

Now, I would have liked to define heap_ as a Heap&, but I can't because of:

template <class U>
HeapAllocator& operator=(HeapA llocator<U> const& ha) /*throw()*/
{
heap_ = ha.heap_;
}

Which is an annoyance but otherwise not that big of an issue. The
problem for me is one of elegance and robustness. Under what
circumstances could I expect operator= to be called (aside from in
operator= in a container)? Memory allocated in one heap cannot be
deallocated in another (operator== tests for heap equality). Am I
guaranteed that all allocations would be deallocated by the correct
allocator (or to put it more specifically allocations by an allocator A
will only be deallocated by A or by another allocator B for which B ==
A) - ie, is this a requirement?

I'm a little disturbed by the statement in 20.1.5.4:

"Implementation s of containers described in this International Standard
are permitted to assume that their Allocator template parameter meets
the following two additional requirements... .

- All instances of a given allocator type are required to be
interchangeable and always compare equal to each other."

Does this mean that I am essentially wasting my time?

mark

[Howard Hinnant]

In article
<De************ *******@news01. bloor.is.net.ca ble.rogers.com> ,
"Mark A. Gibbs" <x_*********@ro gers.com_x> wrote:

I'm having yet another headache with making a standard allocator. What
behaviour should be expected from the assigment operator? When would it
be called? Why is it there at all, when you can't change allocators in
containers?

To give a little more depth, I have a class like this:

class HeapAllocator
{
// All requirements of the allocator interface are met along with:
// - A constructor to pass in a heap reference
// - A GetHeap function that returns a reference to the internal heap
// (which can never be 0)

private:
mutable Heap* heap_;
};

Now, I would have liked to define heap_ as a Heap&, but I can't because of:

template <class U>
HeapAllocator& operator=(HeapA llocator<U> const& ha) /*throw()*/
{
heap_ = ha.heap_;
}

Which is an annoyance but otherwise not that big of an issue. The
problem for me is one of elegance and robustness. Under what
circumstances could I expect operator= to be called (aside from in
operator= in a container)? Memory allocated in one heap cannot be
deallocated in another (operator== tests for heap equality). Am I
guaranteed that all allocations would be deallocated by the correct
allocator (or to put it more specifically allocations by an allocator A
will only be deallocated by A or by another allocator B for which B ==
A) - ie, is this a requirement?

I'm a little disturbed by the statement in 20.1.5.4:

"Implementation s of containers described in this International Standard
are permitted to assume that their Allocator template parameter meets
the following two additional requirements... .

- All instances of a given allocator type are required to be
interchangeable and always compare equal to each other."

Does this mean that I am essentially wasting my time?

Not at all. But it does mean you have stumbled into implementation
defined territory. Your experience could contribute to the next C++
standard.

Allocators are not required to be assignable, so you could just omit the
operator=. However, allocators are required to be equal. But however
again, implementors are encouraged to deal with non-equal allocators
(and several do).

Non-equal allocators mainly come into play during resource transferring
operations such as swap or splice, but not during container assignment.
There is an open lwg issue concerning swap here:

http://anubis.dkuug.dk/jtc1/sc22/wg2...ctive.html#431

Here is a response I have written to that issue:

http://anubis.dkuug.dk/jtc1/sc22/wg2...004/n1599.html

Neither the issue, nor the response have yet been discussed in
committee. I point them out just fyi, and also so that you have the
opportunity to join in the discussion.

-Howard

[Mark A. Gibbs]

Howard Hinnant wrote:

Allocators are not required to be assignable, so you could just omit the
operator=. However, allocators are required to be equal. But however
again, implementors are encouraged to deal with non-equal allocators
(and several do).
DOH! You're right, I just re-read that section. What I thought was a
requirement for a1 = a2 is actually a requirement for a1 == a2.
Assignment is not necessary. So that problem is all but solved.

But when you say that allocators are required to be equal, do you mean
that a1 == a2 MUST return true? Or that a1 and a2 should be
interchangeable for all purposes even if a1 != a2?

I have already implemented the latter anyway throughout the course of my
experimentation . The deallocate function in my HeapAllocator class is
roughly:

void HeapAllocator:: deallocate(poin ter p, size_type n)
{
Heap* the_heap = heap_;
if (!the_heap->Owns(p))
the_heap = Heap::GetOwner( p);
the_heap->Deallocate(p );
}

In other words, as currently written, any instance of HeapAllocator can
free memory allocated by any other instance of HeapAllocator, even if
they are not "equal" (ie, the heap_ member is different). This is a
simplification, along with all the assertions, a trace statement records
cases when heap_->Owns(p) is false.

But to me, this is a nasty hack that I would like to avoid if possible.
Non-equal allocators mainly come into play during resource transferring
operations such as swap or splice, but not during container assignment.
There is an open lwg issue concerning swap here:

http://anubis.dkuug.dk/jtc1/sc22/wg2...ctive.html#431

Here is a response I have written to that issue:

http://anubis.dkuug.dk/jtc1/sc22/wg2...004/n1599.html

Neither the issue, nor the response have yet been discussed in
committee. I point them out just fyi, and also so that you have the
opportunity to join in the discussion.

No, thank you. I appreciate the offer, but I'm just a hobbyist
programmer who has never taken a "real" programming course - let alone
an entire cs or sotware engineering degree.

But if I may point out some things that came to mind reading your
comments....

Your second concern in option 2 could be allayed via the use of a
smarter iterator class for the container. The enhanced iterator class
would not be necessary for containers using std::allocator - or for any
containers using an always-equal allocator - so existing code and
binaries remain unchanged, and continue to use naked pointers if that's
what they do. I suppose a *really* smart compiler and library could
theoretically even optimize the smart iterators down to dumb iterators
at compile time if it detects that operator== is always true, but that's
probably not practical. I guess you could create a static boolean
constant in the allocator interface that is true if the allocators are
always equal, but that's a whole new can of worms.

But your first concern in option 2 is also a little odd to me, unless
I'm just misunderstandin g what you mean by slow swap. swap() is only
guaranteed nothrow if both the copy constructor is nothrow and either no
allocation is required or the allocation is nothrow. Unless your
definition of slow swap is not the same as mine, I don't see how an
element-by-element swap violates that principle just because now a1 may
or may not be == a2.

The net result of all this is that I don't see the problematic semantic
changes you allude to, though I do see performance concerns.

That's all I have. Though I really appreciate the knock on the skull
regarding the non-necessity of an assignment operator.

mark

[Mark A. Gibbs]

Howard Hinnant wrote:

Allocators are not required to be assignable, so you could just omit the
operator=. However, allocators are required to be equal. But however
again, implementors are encouraged to deal with non-equal allocators
(and several do).
DOH! You're right, I just re-read that section. What I thought was a
requirement for a1 = a2 is actually a requirement for a1 == a2.
Assignment is not necessary. So that problem is all but solved.

But when you say that allocators are required to be equal, do you mean
that a1 == a2 MUST return true? Or that a1 and a2 should be
interchangeable for all purposes even if a1 != a2?

I have already implemented the latter anyway throughout the course of my
experimentation . The deallocate function in my HeapAllocator class is
roughly:

void HeapAllocator:: deallocate(poin ter p, size_type n)
{
Heap* the_heap = heap_;
if (!the_heap->Owns(p))
the_heap = Heap::GetOwner( p);
the_heap->Deallocate(p );
}

In other words, as currently written, any instance of HeapAllocator can
free memory allocated by any other instance of HeapAllocator, even if
they are not "equal" (ie, the heap_ member is different). This is a
simplification, along with all the assertions, a trace statement records
cases when heap_->Owns(p) is false.

But to me, this is a nasty hack that I would like to avoid if possible.
Non-equal allocators mainly come into play during resource transferring
operations such as swap or splice, but not during container assignment.
There is an open lwg issue concerning swap here:

http://anubis.dkuug.dk/jtc1/sc22/wg2...ctive.html#431

Here is a response I have written to that issue:

http://anubis.dkuug.dk/jtc1/sc22/wg2...004/n1599.html

Neither the issue, nor the response have yet been discussed in
committee. I point them out just fyi, and also so that you have the
opportunity to join in the discussion.

No, thank you. I appreciate the offer, but I'm just a hobbyist
programmer who has never taken a "real" programming course - let alone
an entire cs or sotware engineering degree.

But if I may point out some things that came to mind reading your
comments....

Your second concern in option 2 could be allayed via the use of a
smarter iterator class for the container. The enhanced iterator class
would not be necessary for containers using std::allocator - or for any
containers using an always-equal allocator - so existing code and
binaries remain unchanged, and continue to use naked pointers if that's
what they do. I suppose a *really* smart compiler and library could
theoretically even optimize the smart iterators down to dumb iterators
at compile time if it detects that operator== is always true, but that's
probably not practical. I guess you could create a static boolean
constant in the allocator interface that is true if the allocators are
always equal, but that's a whole new can of worms.

But your first concern in option 2 is also a little odd to me, unless
I'm just misunderstandin g what you mean by slow swap. swap() is only
guaranteed nothrow if both the copy constructor is nothrow and either no
allocation is required or the allocation is nothrow. Unless your
definition of slow swap is not the same as mine, I don't see how an
element-by-element swap violates that principle just because now a1 may
or may not be == a2.

The net result of all this is that I don't see the problematic semantic
changes you allude to, though I do see performance concerns.

That's all I have. Though I really appreciate the knock on the skull
regarding the non-necessity of an assignment operator.

mark

[Rolf Magnus]

Mark A. Gibbs wrote:

Claudio Puviani wrote:

20.1.5 ("Allocator requirements") doesn't state copyability as a
requirement. Comparison, yes, but definitely not copying.

It does state that a conversion constructor must be there to convert an
allocator for one type into an allocator for another type. But "one"
and "another" can also be the same type, making that constructor also a
copy constructor.
But that makes no logical sense if containers own their allocator.

vector<int, SomeAllocator> foo()
{
SomeAllocator a;
vector<int, SomeAllocator> v(a);
Even the above line would need the allocator to be copied.
return v;
}

void bar()
{
vector<int, SomeAllocator> v = foo();
// Undefined behaviour
}

And how can the containers not own their own allocator?

[Rolf Magnus]

Mark A. Gibbs wrote:

But when you say that allocators are required to be equal, do you mean
that a1 == a2 MUST return true? Or that a1 and a2 should be
interchangeable for all purposes even if a1 != a2?

20.1p4 says it quite explicitly:

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
interchangable and always compare equal to each other.

....

[Rolf Magnus]

Mark A. Gibbs wrote:

Claudio Puviani wrote:

20.1.5 ("Allocator requirements") doesn't state copyability as a
requirement. Comparison, yes, but definitely not copying.

It does state that a conversion constructor must be there to convert an
allocator for one type into an allocator for another type. But "one"
and "another" can also be the same type, making that constructor also a
copy constructor.
But that makes no logical sense if containers own their allocator.

vector<int, SomeAllocator> foo()
{
SomeAllocator a;
vector<int, SomeAllocator> v(a);
Even the above line would need the allocator to be copied.
return v;
}

void bar()
{
vector<int, SomeAllocator> v = foo();
// Undefined behaviour
}

And how can the containers not own their own allocator?

[Rolf Magnus]

Mark A. Gibbs wrote:

But when you say that allocators are required to be equal, do you mean
that a1 == a2 MUST return true? Or that a1 and a2 should be
interchangeable for all purposes even if a1 != a2?

20.1p4 says it quite explicitly:

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
interchangable and always compare equal to each other.

....

[Mark A. Gibbs]

Rolf Magnus wrote:

Mark A. Gibbs wrote:

But when you say that allocators are required to be equal, do you mean
that a1 == a2 MUST return true? Or that a1 and a2 should be
interchangeab le for all purposes even if a1 != a2?

20.1p4 says it quite explicitly:

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
interchangable and always compare equal to each other.

The way I read this is that containers don't need to bother testing a1
== a2 - they can just assume that it will always be true. "Containers
may assume that allocators always return true" is not the same as
"Allocators must always return true" to me.

My interpretation is that I am free to provide allocators that are
non-interchangeable , and not always equal, but that in doing so I am
relying on undefined behaviour (p5). My question is that if I were to
provide allocators that *are* interchangeable - even though they may not
return true (the result would be a trace in an error log and a
performance penalty) - would I still be ok according to the strict
definition (p4, as quoted)?

I mean, is there any known implementation that tests for allocator
equality and chokes if they are not equal (via an exception, I assume).
This kind of thing introduces a subtle and unnecessary run time error,
unless I write a separate test unit to include with the library to test
for that explicit scenario.

In my case the equality test does not constitute a test for correctness,
but a test for performance costs. If a container detects that two
allocators are equal then it can skip a lot of work in swap and splice
operations. But if the container just assumes the allocators are equal,
and later one allocator tries to deallocate memory allocated in another
allocator, the only penalty is a performance hit (Heap::GetOwner (void*)
is expensive, far more so than a slow copy).

In the more general case my question is: If I were to write an allocator
that does not always return true but allows cross-allocator
deallocations regardless, would that allocator satisfy both the current
standard and future changes? Would this method present a problem on any
known implementations ?

mark

[Mark A. Gibbs]

Rolf Magnus wrote:

Mark A. Gibbs wrote:

But when you say that allocators are required to be equal, do you mean
that a1 == a2 MUST return true? Or that a1 and a2 should be
interchangeab le for all purposes even if a1 != a2?

20.1p4 says it quite explicitly:

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
interchangable and always compare equal to each other.

The way I read this is that containers don't need to bother testing a1
== a2 - they can just assume that it will always be true. "Containers
may assume that allocators always return true" is not the same as
"Allocators must always return true" to me.

My interpretation is that I am free to provide allocators that are
non-interchangeable , and not always equal, but that in doing so I am
relying on undefined behaviour (p5). My question is that if I were to
provide allocators that *are* interchangeable - even though they may not
return true (the result would be a trace in an error log and a
performance penalty) - would I still be ok according to the strict
definition (p4, as quoted)?

I mean, is there any known implementation that tests for allocator
equality and chokes if they are not equal (via an exception, I assume).
This kind of thing introduces a subtle and unnecessary run time error,
unless I write a separate test unit to include with the library to test
for that explicit scenario.

In my case the equality test does not constitute a test for correctness,
but a test for performance costs. If a container detects that two
allocators are equal then it can skip a lot of work in swap and splice
operations. But if the container just assumes the allocators are equal,
and later one allocator tries to deallocate memory allocated in another
allocator, the only penalty is a performance hit (Heap::GetOwner (void*)
is expensive, far more so than a slow copy).

In the more general case my question is: If I were to write an allocator
that does not always return true but allows cross-allocator
deallocations regardless, would that allocator satisfy both the current
standard and future changes? Would this method present a problem on any
known implementations ?

mark