How exactly does the 'reference' typedef behave?

Question

STL containers have a reference and const_reference typedef, which, in many cases I've seen (containers of bool being the only exceptions I can think of), could be trivially defined as

typedef value_type& reference;
typedef const value_type& const_reference;

What exactly, however, are the semantics of these types?

From what I understand, they are supposed to "behave like references to the value type", but what exactly does that mean?

MSDN says that reference is:

A type that provides a reference to an element stored in a vector.

But what does this mean, exactly? Do they need to overload specific operators, or have a specific behavior? If so, what is the required behavior?

Answer 1

I think part of the question comes from an assumption that allocators are useful. Allocators (at least pre-C++11) were something of a late addition to the STL:

People wanted containers independent of the memory model, which was somewhat excessive because the language doesn't include memory models. People wanted the library to provide some mechanism for abstracting memory models. Earlier versions of STL assumed that the size of the container is expressible as an integer of type size_t and that the distance between two iterators is of type ptrdiff_t. And now we were told, why don't you abstract from that? It's a tall order because the language does not abstract from that; C and C++ arrays are not parameterized by these types. We invented a mechanism called "allocator," which encapsulates information about the memory model. That caused grave consequences for every component in the library. You might wonder what memory models have to do with algorithms or the container interfaces. If you cannot use things like size_t, you also cannot use things like T* because of different pointer types (T*, T huge *, etc.). Then you cannot use references because with different memory models you have different reference types. There were tremendous ramifications on the library.

Unfortunately, they turned out to be substandard:

I invented allocators to deal with Intel's memory architecture. They are not such a bad ideas in theory - having a layer that encapsulates all memory stuff: pointers, references, ptrdiff_t, size_t. Unfortunately they cannot work in practice. For example,

vector<int, alloc1> a(...);
vector<int, alloc2> b(...);

you cannot now say:

find(a.begin(), a.end(), b[1]);

b[1] returns a alloc2::reference and not int&. It could be a type mismatch. It is necessary to change the way that the core language deals with references to make allocators really useful.

The reference typedef is meant to return whatever the equivalent of T& is for the allocator in question. On modern architectures, this is probably T&. However, the assumption was that on some architectures it could be something different (e.g., a compiler targeting an architecture with "near" and "far" pointers might need special syntax for "near" and "far" references). Sadly, this brilliant idea turned out to be less-than-brilliant. C++11 makes substantial changes to allocators -- adding scoped allocators -- and the memory model. I have to admit I don't know enough about C++11's changes w.r.t. allocators to say if things get better or worse.

---

Looking at the comments on the original question, since the Standard does not actually state how the containers must be implemented (although the Standard does put so many requirements on the behavior of the containers that it might as well ...), whatever type you typedef as reference must have the behaviors of T& that somebody could potentially rely on when implementing the container: an object of type reference should be a transparent alias to the original object, assigning to it should change the value of the original object without slicing, there is no need to support "reseating" the reference, taking the address of the reference should return the address of the original object, etc. If at all possible, it should in fact be T&; and the only case I can imagine where it wouldn't be possible would be if you were allocating memory that you couldn't manipulate through pointers or references (e.g., if the "memory" were actually on disk, or if the memory were actually allocated on a separate computer and reachable over the network through RPC calls, etc.).

Answer 2

Taken out of the standard:

It also defines reference as a typedef of value_type& which is a typedef of T

(New answer as previous one was different focus)