Why Can't I store references in a `std::map` in C++?

Question

I understand that references are not pointers, but an alias to an object. However, I still don't understand what exactly this means to me as a programmer, i.e. what are references under the hood?

I think the best way to understand this would be to understand why it is I can't store a reference in a map.

I know I need to stop thinking of references as syntactic suger over pointers, just not sure how to :/

Solution 1

They way I understand it, references are implemented as pointers under the hood. The reason why you can't store them in a map is purely semantic; you have to initialize a reference when it's created and you can't change it afterward anymore. This doesn't mesh with the way a map works.

Solution 2

You should think of a reference as a 'const pointer to a non-const object':

MyObject& ~~ MyObject * const

Furthermore, a reference can only be built as an alias of something which exists (which is not necessary for a pointer, though advisable apart from NULL). This does not guarantee that the object will stay around (and indeed you might have a core when accessing an object through a reference if it is no more), consider this code:

// Falsifying a reference
MyObject& firstProblem = *((MyObject*)0);
firstProblem.do(); // undefined behavior

// Referencing something that exists no more
MyObject* anObject = new MyObject;
MyObject& secondProblem = *anObject;
delete anObject;
secondProblem.do(); // undefined behavior

Now, there are two requirements for a STL container:

• T must be default constructible (a reference is not)
• T must be assignable (you cannot reset a reference, though you can assign to its referee)

So, in STL containers, you have to use proxys or pointers.

Now, using pointers might prove problematic for memory handling, so you may have to:

• use smart pointers (boost::shared_ptr for example)
• use a specialized container: Boost Pointer Container Library

DO NOT use auto_ptr, there is a problem with assignment since it modifies the right hand operand.

Hope it helps :)

Solution 3

The important difference apart from the syntactic sugar is that references cannot be changed to refer to another object than the one they were initialized with. This is why they cannot be stored in maps or other containers, because containers need to be able to modify the element type they contain.

As an illustration of this:

A anObject, anotherObject;
A *pointerToA=&anObject;
A &referenceToA=anObject;

// We can change pointerToA so that it points to a different object
pointerToA=&anotherObject;

// But it is not possible to change what referenceToA points to.
// The following code might look as if it does this... but in fact,
// it assigns anotherObject to whatever referenceToA is referring to.
referenceToA=anotherObject;
// Has the same effect as
// anObject=anotherObject;

Solution 4

actually you can use references in a map. i don't recommend this for big projects as it might cause weird compilation errors but:

    map<int, int&> no_prob;
    int refered = 666;
    no_prob.insert(std::pair<int, int&>(0, refered)); // works
    no_prob[5] = 777; //wont compile!!! 
    //builds default for 5 then assings which is a problem
    std::cout << no_prob[0] << std::endl; //still a problem
    std::cout << no_prob.at(0) << std::endl; //works!!

so you can use map but it will be difficult to guaranty it will be used correctly, but i used this for small codes (usually competitive) codes

Solution 5

A container that stores a reference has to initialize all its elements when constructed and therefore is less useful.

struct container
{
   string& s_;           // string reference
};

int main()
{
   string s { "hello" };
   //container {};       // error - object has an uninitialized reference member
   container c { s };    // Ok
   c.s_ = "bye";
   cout << s;            // prints bye
}

Also, once initialized, the storage for the container elements cannot be changed. s_ will always refer to the storage of s above.

View more solutions

Comments

[sbi]

Don't think of references as restricted pointers. Think of them as aliases to existing objects that aren't allowed to be left dangling.

[sbi]

Minor point: This MyObject& firstProblem = *((MyObject*)0); is already undefined behavior (you're not initalizing the reference with a valid object) and thus this alone is, according to the C++ standard, allowed to format your hard disk or do other bad things to you. (Nasal demons, anyone?) But that's just a very minor point and otherwise yours is an excellent answer. +1

[UncleBens]

Another minor point: it seems to me that default-constructibility is not a requirement (except some methods use default constructed instance for the default argument). (20.1.4.1) I think you meant copy-constructible.

[Matthieu M.]

Exact, for STL container in general it is not necessary (conceptually). For a map, not using a Default Constructible value would invalidate the use of the subscription operator (-> operator[]) though... and personally I get an error message in VC++2008 if I try to use a type that is not default constructible: "error C2512: 'Special::Special' : no appropriate default constructor available"

[bambams]

This sounds good to me except for the "containers need to be able to modify the element type they contain." This makes it sound like the map needs to be able to change the data type it stores, whereas really it just needs to be able to change the "element" itself.

[Jaywalker]

Do you think references take up any "memory"? I know pointers do.

[Sebastiaan M]

@Jaywalker: yes they do. In the generated assembly code they are implemented as pointers.

[Trent]

There's a few mistakes with the referenced document. For one references are not necessarily constant pointers (they may be implemented that way). See jefito's comments at the bottom.

[sp2danny]

It is explicitly unspecified in the standard whether they have storage or not. Usually they do, but sometimes it can be optimized away.