Are C++11 stateful allocators interchangeable across type boundaries?

Question

My question here is basically a follow up to :

How can I write a stateful allocator in C++11, given requirements on copy construction?

Basically, despite the fact that the C++11 standard now allows for stateful allocators, we still have the requirement that if you copy a certain Allocator, the copy must compare equal via the == operator with the original. This indicates that the copy can safely deallocate memory which was allocated by the original, and vice-versa.

So, right off the bat this already prohibits an allocator from maintaining unique internal state, like a slab-allocator or memory pool or something. One solution would be to use a shared_ptr pointer-to-implementation idiom for the internal state, so that all copies of some original Allocator use the same underlying memory pool. That's not too bad. Except...

According to the above referenced question, as well as the accepted answer, the standard also seems to require that Allocator<T> has an interoperable copy constructor with Allocator<U>, so that:

Allocator<T> alloc1;
Allocator<U> alloc2(alloc1);
assert(alloc1 == alloc2); // must hold true

So in other words, allocator types must be interoperable regardless of different template parameters. That means if I allocate some memory using Allocator<T>, I must be able to deallocate that memory using an Allocator<U> instance constructed from the original Allocator<T>.

...and that's pretty much a show-stopper for any attempt to write an allocator that uses some sort of size-based memory pool, like a simple_segregated_storage pool that only returns chunks of a certain size based on sizeof(T).

But... is this really true?

I realize the interoperable copy constructor is required for Allocator<T>::rebind so users of containers don't need to know the internal details of say, a linked-list node type or something. But as far as I can see, the standard itself doesn't seem to say anything so draconian as the requirement that an Allocator<U> constructed from an Allocator<T> must compare equal with the original Allocator<T> instance.

The standard basically requires the following semantics, where X is a type Allocator<T>, a1 and a2 are instances of X, Y is a type Allocator<U>, and b is an instance of Allocator<U>.

From: § 17.6.3.5 (Allocator requirements)

a1 == a2 returns true only if storage allocated from each can be deallocated via the other.

operator == shall be reflexive, symmetric, and transitive, and shall not exit via an exception.

a1 != a2 : same as !(a1 == a2)

a == b : same as a == Y::rebind<T>::other(b)

a != b : same as !(a == b)

X a1(a); Shall not exit via an exception. post: a1 == a

X a(b); Shall not exit via an exception. post: Y(a) == b, a == X(b)

So, the way I read this, instances of Allocator<T> constructed from Allocator<U> are not necessarily interchangeable. The standard merely requires that a == b must be equivalent to Y(a) == b,  not that a == b must be true!

I think the requirement for the cross-type-boundary copy constructor makes this confusing. But, the way I read this, if I have an Allocator<T>, it must have a copy constructor that takes an Allocator<U>, but that doesn't imply that:

Allocator<T> alloc1;
Allocator<U> alloc2(alloc1);
assert(alloc2 == alloc1); 

In other words, the way I read this, the above assertion is allowed to fail. But I'm not confident in my understanding here, because:

1. The accepted answer to this question says otherwise, and the answerer is a guy with 108K reputation

2. The interaction between copy constructor requirements and equality requirements in the standard is a bit confusing, and I may be misunderstanding the verbiage.

So, I am I correct here? (Incidentally, the implementation of boost::pool_allocator seems to imply I am correct, assuming the boost developer cares about standards compliance, since this allocator is not interchangeable accross type boundaries.)

Marie

"That means if I allocate some memory using Allocator<T>, I must be able to deallocate that memory using an Allocator<U> instance constructed from the original Allocator<T>." I don't think it means that. Read Casey's answer that explains that you'd need to rebind the Allocator<U> back to T before deallocating objects of type T. – Maudiemaudlin

[allocator.requirements]/9 says "An allocator may constrain the types on which it can be instantiated" which implies that you can constrain it to sizeof(T) == some_fixed_size. – Antimacassar

"In other words ... the above assertion is allowed to fail." This doesn't help too much because X(Y(a))==a must still hold. Which means any allocator created from a must carry the same state a carries. – Kentigera

Answer 1

The last line that you quote:

X a(b); Shall not exit via an exception. post: Y(a) == b, a == X(b)

Conflicts with your conclusion.

using X = Allocator<T>;
using Y = Allocator<U>;
Y b;
X a(b);
assert(Y(a) == b);
assert(a == X(b));
// therefore
assert(a == b);

Brush

Answer 2

The standard does not entertain the possibility that objects (or values) of different types could ever be truly equal; this would contradict the very idea that objects have types. They can however compare equal, which just tells us what operator== would return when called for the objects. For different instances of an allocator template, it is specified that calling that operator between objects of those distinct types effectively replaces the second operand by an object of the type of the first operand but "copy-constructed" from the second operand, and then applies operator== for these equal type operands. (It escapes me why the type is specified as Y::rebind<T>::other (which need not be defined) rather than allocator_traits<Y>::rebind_alloc<T>, or better even simply X, the type of a; probably just an historic remnant.) So in the end, the comparison is always between objects of the same type; for that case (only) it is specified that equality means interoperability, i.e., that storage given out by one allocator can be recycled using the other.

So Yes, after saying Y b(a) where the type X of a is Allocator<T> while Y is Allocator<U>, it is ensured that b == a, which equals b == Y(a), returns true; also a == b, which equals a == X(b) must return true (the passage you cited says so explicitly, though with some interchanges of names). But No, this does not mean that "if I allocate some memory using Allocator<T>, I must be able to deallocate that memory using an Allocator<U>", because that requirement is only made for equality of allocators of the same type. Indeed, it is not clear how one would even set up for such a deallocation, because the method Allocator<U>::deallocate has a first argument of type Allocator<U>::pointer, which is presumably U* and in any case different from Allocator<T>::pointer, so one could only get into this scenario after doing pointer type travesty, which I believe gives you Undefined Behaviour on the spot.

There is one implication, sort of, of the requirements that I would like to point out: an allocator type Allocator<T> can hardly have any non-static data members whose type depends on T. (With "hardly" I mean it is not rigorously impossible, just not doable in any useful manner.) Because if such a member accesses some storage resource useful for future allocations of type T (think of a pointer to T to some free space) with presumably equality of allocators requiring this resource to be shared (since allocations from one can be deallocated to another) then copy-constructing an Allocator<U> must somehow initialise the corresponding data member, which has a different type, and which can now be used as a resource or future allocations of type U, but still retain the identity of the resource (so it cannot simply construct an empty resource for type U) because copy-constructing back to Allocator<T> must result in the resource being shared with the original allocator; this I think is a very tall order.

My conclusion would be that in practice allocators have to be either stateless (no non-static data members at all) or else have a type-ignorant resource management (with in particular all data members independent of the value_type, and with all copy-constructed versions for different types of the same allocator sharing resources, just like malloc serves all types at once). Or both, like for std::allocator. But I'd love to be proven wrong.

Cartie