Does map::iterator yield lvalues ?

Question

In other words, when i is a map<K,V>::iterator, do the following provide the expected semantics (ie. it modifies the map):

*i = make_pair(k, v);
i->first = k;
i->second = v;

?

Update: The first two lines are invalid, since the return value of operator* is (convertible to?) a pair<const K, V>. What about the third line ?

Assuming a yes answer to the three, this would imply that:

• Either map<K,V> elements are stored as a pair<K,V> somewhere,
• Or there is some clever proxy class which map<K,V>::iterator::operator* returns. In this case, how is operator-> implemented ?

Answer 1

map is almost like a set of pairs. Yes, it's iterator is probably implemented as a pointer to a node with a pair<const K,V>. However your code is invalid, because the values are actually of type pair<const K, V> so you can't assign to first.

*i returns pair<const K, V>& or some proxy that behaves like this type (can't find a backup of the last claim in the standard). You can implement such proxies by overloading operator ->.

Answer 2

Firstly, technically the unary * operator evaluates to an lvalue in this case. However, the term lvalue in C basically designates something that has location (address) in storage (memory). In C++ terminology even functions are lvalues. So, again, in your example above the unary * yield an lvalue. You can take the address of that lvalue, if you wish to do so, i.e. you can evaluate &*i, &i->first and &i->second (assuming the built-in unary &).

Secondly, since you original example involves assignment, you must be actually talking about modifiable lvalues. You see, the property of being lvalue by itself has very little to do with being assignable. To use the built-in assignment operator, you need a modifiable lvalue. What you get from a dereferenced iterator is value_type of std::map. It is a pair with a const-qualified first member, as you know already. This automatically makes the first member non-modifiable, and this makes the entire pair non-modifiable by the built-in assignment operator. The second member of the pair is modifiable, as you observed yourself already.

So, once again, the dereference operator in this case returns an lvalue. This lvalue is non-modifiable as a whole, and its first member is non-modifiable as well. Its second member is a modifiable lvalue.

As for your assumption about how the elements of std::map are stored, I would say that in a typical implementation they will be stored as pair<const K, V> objects, i.e. exactly what the dereference operator evaluates to. Normally, the map does not need to modify the key portion of the pair after it is initialized, so it should not run into any problems with the fact that the first member of the pair is const-qualified.

Answer 3

map<K,V>::iterator i = my_map.begin();

*i = make_pair(k, v); // invalid, you cannot assign to a pair<const K,V>&
i->first = k; // invalid cannot write to const
i->second = v; // valid

Answer 4

I tried to track this down through the standard:

• For a map<Key,T> the value_type is pair<const Key,T> per 23.3.1/2

• The map class supports bidirectional iterators, per 23.3.1/1

• bidirectional iterator satisfies the requirements for forward iterators, per 24.1.4/1

• For a forward iterator a with value_type T, expression *a returns T& (not a type "convertible to T", as some other iterators do) (Table 74 in 24.1.3)

Therefore, the requirement is to return a reference to pair, and not some other proxy type.