Why is Allocator::reference being phased out?

Question

So I was looking at specification of std::vector and noticed that reference typedef changed from Allocator::reference in C++03 to to value_type& in C++11. I was surprised, so I've started looking deeper.

In C++03 §20.1.5 [lib.allocator.requirements] there's table 32 in which X::reference is defined to be T& and X::const_reference is defined to be T const&.

However, in C++11 §17.6.3.5 [allocator.requirements] there's table 28 in which reference and const_reference are missing.

Next we have §20.6.8 std::allocator_traits added in C++11 which doesn't include reference. But §20.6.9 std::allocator does.

Finally, there's §23.2.1 [container.requirements.general] which define X::reference to be "lvalue of T" and X::const_reference to be "const lvalue of T".

So, I've googled and found this paper (1, 2) that proposes removal of reference from allocator requirements, but it doesn't mention any rationale behind it. But there is also a LWG issue which opposes the change.

Also, I've found the interview with Alexander Stepanov in which he talks how reference encapsulates machine-specific memory layout and Herb Sutter's post in which he talks about taking pointers to container elements, container requirements and how std::vector<bool> is not a container.

So, what do you think about all of this? Was reference useful, did it serve it's purpose? How do "fancy" references fit into the Standard? Is this a bold move to completely eliminate them, make more strict container requirements and deprecate std::vector<bool>?

Answer 1

In the interview with Alexander Stepanov he mentions that during the proposal to add STL to the Standard library he was asked to create an abstraction from memory model. Thus, the allocators was born. In the LWG issue there is an example of implementation where reference of custom allocator is defined to be T __far&.

But, for reasons unknown because I don't have that much time to search, the C++03 standard has the following text in §20.1.5 p4:

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.

This effectively defeats the ability of custom memory model allocator to interoperate with standard containers.

During my search for all pre-C++11 papers which mention the word "allocator" I've found a major consensus to remove those words from the Standard. Finally, this paper proposes to remove them with the following commentary:

The weasel words are gone. Raise your glass and make a toast.

Victory? Can we finally go wild with our memory models? No so much. Among other things, the same paper proposes to remove reference from allocator requirements. And it looks like it was voted into the Standard.

The LWG issue I mentioned earlier opposes the change but it was closed with the following statement:

No consensus to make a change

So it looks like the original purpose of allocators is not so important today. Here's what Wikipedia has to say:

The current purpose of allocators is to give the programmer control over memory allocation within containers, rather than to adapt the address model of the underlying hardware. In fact, the revised standard eliminated the ability of allocators to represent extensions to the C++ address model, formally (and deliberately) eliminating their original purpose.

Finally, the Container::reference has nothing to do with allocators. It was created to allow for proxied collections which are not actually containers. So it's here to stay. By the way, it looks like it is another example of how final words in the Standard go against original intentions.

Answer 2

Because that nested typedef is superfluous. Scott Meyers' Effective STL, page 49:

the Standard explicitly allows library implementers to assume that every allocator's pointer typedef is a synonym for T* and every allocator's reference typedef is the same as T&

Answer 3

http://en.wikipedia.org/wiki/Allocator_(C%2B%2B)

"They were originally intended as a means to make the library more flexible and independent of the underlying memory model, allowing programmers to utilize custom pointer and reference types with the library. However, in the process of adopting STL into the C++ standard, the C++ standardization committee realized that a complete abstraction of the memory model would incur unacceptable performance penalties. To remedy this, the requirements of allocators were made more restrictive. As a result, the level of customization provided by allocators is more limited than was originally envisioned by Stepanov."

Originally they were designed to abstract away memory itself, allowing one to allocate memory on say, another machine via and internet connection, and copy data back and forth using pointers/references to keep track of what's live. Similarly, one could make a Java-like GC in pure C++. This abstraction seemed like an amazing idea!

However, This incurred performance penalties that were deemed unacceptable at the time. Also, if you think about it, it's very nearly impossible to work in code. Every void func(const string&) would have to be made into a template<class allocator> void func(allocator::reference), which is a non-deducible context so you'd have to explicitly write the allocator in the function call (func<std::allocator<std::string>::const_reference>(username)), which nobody would do, which would make the GC not work properly. Nowadays, allocators merely abstract memory allocation/deallocation.