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

Answer 1

问题的原因

当您调用m.erase(0)示例时，it用键指向一个元素0- 因此it无效。m.erase(1)有效，因为当它第一次被调用时，it没有指向带有 key 的元素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)搜索间隔末尾时) 来搜索间隔末尾。