C++ multimap 迭代器失效

Question

我正在尝试弄清楚std::multimap迭代器的工作原理，因此我创建了一个简单的示例来展示我的问题实质。如果取消注释第1种情况，我期望迭代器指向键为1的第一个元素，但实际上它打印出所有与键0相关联的值（就像没有被删除一样），有时会崩溃，可能是因为迭代器无效。但是，如果取消注释第2种情况，则所有键为1的值都将被正确删除。

是否有任何方法可以知道在删除后multimap的下一个有效迭代器是什么？ （例如std::vector.erase(...)返回一个）

std::multimap<int, int> m;

for(int j=0; j<3; ++j) {
    for(int i=0; i<5; ++i) {
        m.insert(std::make_pair(j, i));
    }
}

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) {
    printf("%d %d\n", (*it).first, (*it).second);
    ++it;
    if( (*it).second == 3 ) {
        //m.erase(0);     //case 1
        m.erase(1);     //case 2
    }
}

- givi

---

为什么不用it->first，而是要用(*it).first？ - curiousguy

但这真的重要吗？它可以完成相同的事情，我有95％的把握它会编译成相同的代码。 - James Matta

@curiousguy 因为我喜欢写 (*it).first。 - givi

@JamesMatta "Does it really matter though?" 是的。"我有95%的把握它会编译成相同的代码。" 我有100%的把握它会产生相同的代码。但是，我有95%的把握额外的括号会降低可读性，因为它会显著减慢阅读速度。当我看到这个时，我不得不问自己“为什么不用it->？”这会进一步减慢程序理解的速度。 - curiousguy

@curiousguy：我想我能理解你的想法。我不介意，但我可以理解你的观点。如果我听起来有些轻率，请原谅。 - James Matta

@JamesMatta "我想我不介意，但我能理解你的观点。" 在这个特定的例子中，在这个小规模上，它并不是_真的_很重要。然而在更复杂的表达式中，它可能会有所不同。"如果我听起来轻率，请原谅我。" 不用道歉！ - curiousguy

Answer 1

问题的原因

当您在示例中调用 m.erase(0) 时，it 指向一个带有键值 0 的元素 - 因此 it 无效。 m.erase(1) 可以正常工作，因为第一次调用时，it 没有指向一个键值为 1 的元素，所以它不会受影响。在后续迭代中，没有带有键值为 1 的元素，因此不会删除任何内容，并且没有迭代器受到影响。

解决方案

multimap 没有返回下一个有效迭代器的 erase 方法。一种替代方法是在删除之后调用 it = m.upper_bound(deleted_key);。尽管如此，这是对数时间复杂度，可能对您的场景来说速度太慢了（erase(x) 和 upper_bound 将是两个对数操作）。

假设您想要删除迭代器当前指向的键值，则可以执行以下操作（否则，erase 当然也可以；未经测试）：

std::multimap<int, int>::iterator interval_start = m.begin();
for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end(); ++it) {
    if(interval_start->first < it->first) // new interval starts here
        interval_start == it;
    if( (*it).second == 3 ) {
        std::multimap<int, int>::iterator interval_end = it;
        while((interval_end != m.end()) && (interval_end->first == it->first)) {
            ++interval_end; // search for end of interval - O(n)
        }
        m.erase(interval_start, interval_end); // erase interval - amortized O(1)
        it = interval_end; // set it to first iterator that was not erased
        interval_start = interval_end; // remember start of new interval
    }
}

这个操作只使用了一次线性操作，其余的都是常数时间。如果你的映射很大，并且只有少量具有相同键的项，那么这可能会更快。然而，如果有许多具有相同键的项，则寻找间隔结尾的搜索最好使用upper_bound（在搜索间隔结尾时，时间复杂度为O(log n)而不是O(n)）。

- Björn Pollex

---

从 C++11 开始，multimap 的 erase 函数会返回下一个有效的迭代器。 - Felix Dombek

Answer 2

当您擦除迭代器时，迭代器将变为无效。相反，请记住下一个元素，然后再进行擦除操作。

std::map<int,int>::iterator next = m + 1;
m.erase
m = next;

- AndersK

---

我知道这个问题。但是，如果我删除当前迭代器位置后的多个值，它们可能仍然存在（这有点奇怪，也是问题所在）。 - givi

Answer 3

第一个答案

std::multimap<int, int> m;
//   ^^^^^^^^
std::map<int, int>::iterator it=m.begin(); 
//   ^^^

嗯……

第二个答案，关于编辑后的问题

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) {
    .... stuff ....
        m.erase(1); // container mutation
    .... stuff ....
}

当您在迭代容器时（任何容器），进行容器变异时要非常小心，因为您可能会使您依赖的迭代器无效。

所谓的“基于节点的容器”（list、set、map等）是关于迭代器失效最强大的容器：它们只会使指向已删除元素的迭代器失效（这些迭代器没有不失效的方法）。

在这种情况下，您应该检查您即将删除的元素实际上不是*it。

我不太确定您正在尝试做什么。

- curiousguy

---

这显然是不正确的 - 但由于它似乎可以编译，这意味着它们要么是相同类型，要么是隐式可转换的（我怀疑）。因此，这可能不是错误的原因。 - Björn Pollex

Answer 4

上面有些人已经回答了，你正在玩火。

此外，我认为你忘记了multimap是有序映射，所以你是从最小的键到最大的键进行迭代。因此，在第一种情况下，你在打印一些键后删除键，但在第二种情况下，你在去到它们之前删除。

- Oleksandr Pryimak

Answer 5

从你的代码来看，我认为你的++it引起了问题。你正在将它分配给可能已被删除的位置。将其移动到if语句和测试之后的末尾。像这样：

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) {
    printf("%d %d\n", (*it).first, (*it).second);
    if( (*it).second == 3 ) {
        //m.erase(0);     //case 1
        m.erase(1);     //case 2
    }
    ++it;
}

- kingcong3

---

将 ++it 移动到循环体的末尾的建议是好的，但解释完全没有意义。 "您正在将其分配给可能已被删除的位置。" 作者没有分配任何内容，“已删除的内容”与问题无关。 - Serge Dundich

Answer 6

（已编辑）

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) {
    printf("%d %d\n", (*it).first, (*it).second);
    ++it;
    if( (*it).second == 3 ) {
        //m.erase(0);     //case 1
        m.erase(1);     //case 2
    }
}

除了在另一个答案中已经涵盖的由于 multimap 的内容而可能发生的 m.erase 无效化 it 迭代器之外，当你在每次运行程序时，在 for 循环的最后一次迭代中解引用 m.end() 迭代器时，总是存在这样的问题，例如：if( (*it).second == 3 )。

我建议使用调试版本运行和调试。我几乎可以肯定，每个合理的标准库实现都应该包含 assert 来检测 end() 的解引用。

- Serge Dundich