这是正确的行为吗？ std::map 迭代器失效

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;
}

打印出来：

1, 1
2, 2

根据标准，这真的应该发生吗？我没有触及 reverse_iter 但它指向的值正在改变。我认为 std::map 中的迭代器应该可以安全地防止插入。然而，它似乎决定 reverse_iter 不再指向我告诉它的值，而是指向 "whatever happens to be at the end of the map at this point in time".

更新：更多信息，以防万一：前向迭代器似乎不会发生这种情况（在我似乎能找到的任何情况下），我的 gcc 版本是 5.1.1-4。

Answer 1

此处引用 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

副作用是，如果您在该迭代器之前插入一些内容（包括 end()），您将在取消引用该反向迭代器时看到该新值。我不认为在这种情况下反向迭代器是无效的。

Answer 2

根据 C++ 标准（23.2.4 关联容器）

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.

另一方面（24.5.1 反向迭代器）

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.

虽然在最后一个引用中提到了 class std::reverse_iterator 这同样适用于标准容器的反向迭代器。

根据 Table 97 — 可逆容器要求

rbegin()对应reverse_iterator(end())

因此在您的示例中，反向迭代器仍然对应于 end()。 `

Answer 3

map.rbegin() returns 等于 std::reverse_iterator(map.end());

的迭代器

取消引用反向迭代器时会出现问题。当您取消引用 reverse_iterator 时，您实际获得的值是在迭代器存储在 reverse_iterator 之前从迭代器中获得的。这可能看起来很奇怪，但这是有充分理由的，而且这是不可避免的。这是这样的，为了安排一个范围的尾后元素：指向范围内尾后元素的迭代器，当反转时，指向的最后一个元素（不超过它）范围（这将是反转范围的第一个元素）。如果指向范围中第一个元素的迭代器被反转，则反转迭代器指向第一个元素之前的元素（这将是反转范围的尾部元素）。

也就是说，在您的情况下，取消引用 reverse_iter 等同于：

*(--map.end());

因此，在第二个 emplace 之后，地图的最后一个元素已更改并取消引用 (--map.end())（即您的 reverse_iter），您将获得地图中新的最后一个元素。

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;

打印

2, 2
2, 2
1, 1

这是正确的行为吗？ std::map 迭代器失效

Is this proper behavior? std::map iterator invalidation

c++

iterator

stdmap