C++ 多映射迭代器失效

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

Answer 1

问题原因

当您在示例中调用 m.erase(0) 时，它 指向具有键 0 的元素 - 所以 它无效。 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
    }
}

这里使用一次线性运算，其余都是常数时间。如果您的 map 非常大，并且您只有很少的项目具有相同的键，这可能会更快。但是，如果您有许多具有相同键的项目，则使用 upper_bound 搜索间隔结束可能更好(O(log n) 而不是 O(n) 搜索区间结束时)。