c++ - 为什么从 map 中删除操作不会使迭代器无效

Question

我想知道为什么根据谓词从循环内的映射进行删除操作会使迭代器处于有效状态，但对于 vector 则不然

Answer 1

Vector::erase 使第一个被删除元素之后的所有元素的迭代器无效。这是有道理的，因为 vector 将其数据存储在数组中。当一个元素被删除时，它之后的所有元素都需要一起移动，例如

int test[] = {0, 1, 2, 3, 4, 5};
                             ^

在上面我们有一个指向值 5 的迭代器，这是我们想要的，但是，元素 1 被删除了，我们现在有:

0, 2, 3, 4, 5 
               ^

迭代器指向数组末尾，这是一个问题。

使用std::map，数据存储在二叉树中，所以当一个元素被删除时，一些节点的左/右指针会被修改，但它们在内存中的位置没有改变。因此，任何指向尚未被删除的元素的现有迭代器仍然有效。