CODEWITHSUNDEEP
c++iteratorstdmap
KarenRei
KarenRei

Reputation: 609

Is this proper behavior? std::map iterator invalidation

#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 prints out:

1, 1
2, 2

Is this really what's supposed to happen, according to the standard? I'm not touching reverse_iter but the value it's pointing to is changing. I thought iterators in std::map were supposed to be safe against insertion. Yet it seems to be deciding that reverse_iter is not to stay pointing to the value I told it to, rather to "whatever happens to be at the end of the map at this point in time".

Update: further info, in case it matters: this doesn't seem to happen with forward iterators (in any situation I can seem to find), and my gcc version is 5.1.1-4.

Upvotes: 7

Views: 1110

Answers (4)

lalitm
lalitm

Reputation: 656

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

Upvotes: 0

Dimitrios Bouzas
Dimitrios Bouzas

Reputation: 42899

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

The problem arises when you dereference a reverse iterator. When you dereference a reverse_iterator the value you actually get is from the iterator before the one is stored inside the reverse_iterator. That might seem strange, but is there for good reasons, and it's unavoidable. This is so, in order to arrange for the past-the-end element of a range: An iterator pointing to a past-the-end element in a range, when reversed, is pointing to the last element (not past it) of the range (this would be the first element of the reversed range). And if an iterator to the first element in a range is reversed, the reversed iterator points to the element before the first element (this would be the past-the-end element of the reversed range).

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

*(--map.end());

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

Upvotes: 1

Vlad from Moscow
Vlad from Moscow

Reputation: 310940

According to the C++ Standard (23.2.4 Associative containers)

9 The insert and emplace members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

On the other hand (24.5.1 Reverse iterators)

1 Class template reverse_iterator is an iterator adaptor that iterates from the end of the sequence defined by its underlying iterator to the beginning of that sequence.

Though in the last quote there is said about class std::reverse_iterator the same is valid for reverse iterators of standard containers.

According to Table 97 — Reversible container requirements

rbegin() corresponds to reverse_iterator(end())

So in your example the reverse iterator still corresponds to end(). `

Upvotes: 4

Slava
Slava

Reputation: 44238

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

Reverse iterator stores an iterator to the next element than the one it actually refers to

the side effect would be that if you insert something before that iterator (incliding end()) you will see that new value when you dereference that reverse iterator. I do not think that reverse iterator is invalidated in this case.

Upvotes: 3

Related Questions