Is this the right behavior? std :: map iterator invalid

Question

#include <iostream> #include <map> int main(int argc, char** argv) { std::map<int, int> map; map.emplace(1, 1); auto reverse_iter = map.rbegin(); std::cout << reverse_iter->first << ", " << reverse_iter->second << std::endl; map.emplace(2, 2); std::cout << reverse_iter->first << ", " << reverse_iter->second << std::endl; return 0; } 

This produces:

 1, 1 2, 2 

Is this really what should happen according to the standard? I do not touch reverse_iter, but the value that it indicates changes. I thought that iterators on std :: map should be safe from insertion. However, it seems that the reverse_iter solution should not point to the value that I said, but rather "no matter what happens at the end of the map at this point in time."

Update: additional information, in case it matters: it does not seem to happen with forward iterators (in any situation I can find), and my version of gcc is 5.1.1-4.

Answer 1

As stated here http://en.cppreference.com/w/cpp/container/map/rbegin

The reverse iterator stores an iterator for the next element than the one it actually refers to

a side effect will be that if you insert something before this iterator (uniform to end ()), you will see this new value when you spot this inverse iterator. I don't think the reverse iterator is invalid in this case.

Answer 2

According to the C ++ standard (23.2.4 associative containers)

9 Insert and emplace elements do not affect the validity of iterators and container references, and erasure members should only invalidate iterators and references to erased elements.

On the other hand (24.5.1 Reverse iterators)

1 An example of an inverse-iterator pattern is an iterator adapter that iterates from the end of the sequence defined by its base iterator to the beginning of this sequence.

Although the last quote says about the class std::reverse_iterator the same is true for reverse iterators of standard containers.

According to table 97 - requirements for reversible containers

rbegin() matches reverse_iterator(end())

So, in your example, the reverse iterator still matches end() . `

Answer 3

map.rbegin() returns an iterator equal to std::reverse_iterator(map.end());

The problem occurs when dereferencing the reverse iterator. When you reverse_iterator , you actually get the value from the iterator before it is stored inside reverse_iterator . This may seem strange, but there are good reasons, and it is inevitable. This is so as to arrange the end of the range element: An iterator pointing to the end element at the end, if not, points to the last element (and not past it) of the range (this will be the first element in the inverse range). And if the iterator of the first element in the range is reversed, the inverse iterator points to the element before the first element (this would be the element at the end of the inverse range).

That is, in your case, when dereferencing reverse_iter equivalent to doing:

 *(--map.end()); 

Therefore, after the second emplace last map element has changed and dereferencing (--map.end()) (i.e. your reverse_iter ), you will get the new last element on the map.

Answer 4

 std::map<int, int> map2; map2.emplace(2, 2); auto fiter = map2.begin(); std::cout << fiter->first << ", " << fiter->second << std::endl; map2.emplace(1, 1); std::cout << fiter->first << ", " << fiter->second << std::endl; fiter = map2.begin(); std::cout << fiter->first << ", " << fiter->second << std::endl; 

prints

 2, 2 2, 2 1, 1