c++ - C++ std::map 和 std::set 是否删除复制值并因此使迭代器无效

Question

我正在考虑在二叉搜索树中实现移除。我知道 std::map 和 std::set 通常作为 RBTree 实现。但无论如何，如果它是某种 BST，那么在删除/删除具有 2 个子节点的节点时，我们通常将其与其后继(或前任)交换。许多教科书表明这只是复制继任者的键和值。但是这个拷贝不是透明的。例如，如果值是另一个容器，我有未完成的迭代器，那么删除一些 OTHER 键，值现在可以使我对一个我没有明确更改的容器的迭代器无效。我们可以将后继节点重新链接到应该删除的节点所在的树中，而不是复制键值。这将维护节点的状态。

假设我有一张 vector 图:

std::map<int, vector<int> > mymap;
// Add root
mymap.insert(make_pair(2, vector<int>()));
// Add left child
mymap.insert(make_pair(1, vector<int>()));
// Add right child
mymap.insert(make_pair(3, vector<int>()));
mymap[3].push_back(10);
// I get an iterator to the vector stored in the node with key=3
vector<int>::iterator it = mymap[3].begin();

// I now remove element 2 from the map.  
mymap.erase(2);

// If the successor's (i.e. 3's) key,value were *copied* to 2's node
// and then 3's node was deleted this would invalid iterators 
vector<int>::iterator it2 = mymap[3].begin();

// These could/should be different if remove copied the successor
cout << &*it << " " << &*it2 << endl;

当然，包含 3 的节点可以在树中“重新链接”以代替 2 的节点，然后删除 2 的节点。这将保持键值的正确状态。

我编写了这个测试用例，它似乎是重新链接而不是复制。这种行为是否在任何地方定义？

类似地，如果我有一个 vector 的 vector (即 vector > 并且我将一个迭代器保存到“内部” vector 之一中的一个元素，但随后由于插入另一个 vector 而调整外部 vector 的大小，那么我的迭代器是无效的，即使我没有从技术上修改那个内部 vector 。失效的“传递”属性是在某处阐明的还是“显而易见的”/“隐含的”，我只是玩游戏的速度慢？

Answer 1

基于节点的容器(映射、集合、列表)的删除操作只会使迭代器和对被删除元素的引用无效，但不会使任何其他迭代器无效。

当您按值删除时，这通常是直截了当的，但是当您按迭代器删除时，这在循环遍历整个容器的常见情况下确实需要小心。即:

for (auto it = my_set.begin(); it != my_set.end(); )
{
     if (should_we_erase(it)) { my_set.erase(it++); }
     else                     { ++it;               }
}

请密切注意我们如何确保在删除迭代器后不使用迭代器!在删除分支中，我们首先通过后增量将it设置为一个新的有效迭代器，然后在原始迭代器(即后增量表达式的值)处删除。或者，我们可以将其写为 it = my_set.erase(it);，因为 erase 操作返回下一个(有效的)迭代器。一个非常常见的新手错误是将 ++it 放在循环头中，然后最终对无效迭代器执行算术运算。

相比之下，vector 和 deque 在更多的操作中使更多的迭代器和引用无效。

迭代器和引用的失效作为标准库规范的一部分得到了很好的记录，任何自重的文档或教程都会非常清楚地说明某些东西何时以及如何失效。