如何修复std::multimap删除指定键多余元素后遍历无输出问题？

原问题代码 #

#include <map>
#include <iostream>
 
int main()
{
    std::multimap <int, int> map;
 
    // insert the values in multimap
    map.insert(std::make_pair(1, 10));
    map.insert(std::make_pair(2, 20));
    map.insert(std::make_pair(2, 30));
    map.insert(std::make_pair(2, 40));
    map.insert(std::make_pair(3, 50));
    map.insert(std::make_pair(4, 60));
    map.insert(std::make_pair(4, 70));
     
    int key = 2;   
    bool fo = false;
    for (auto itr = map.begin(); itr != map.end(); itr++)   
    {
      if (itr -> first == key)       
      {  
        if(fo)
        {
          map.erase(itr);
        }
        fo = true;
      }
    }

     for (auto itr = map.begin(); itr != map.end(); itr++)   
     {
                std::cout << itr -> first << "  "
                 << itr -> second << std::endl;
     }

    return 0;
}

错误原因 #

调用map.erase(itr)后，当前迭代器itr会直接失效，后续执行itr++属于未定义行为，会破坏容器内部结构，导致最终遍历循环无法正常输出内容。

修复方案 #

方案一：利用erase返回值更新迭代器 #

修改遍历逻辑，删除元素时用erase返回的下一个有效迭代器替换当前迭代器，避免失效问题：

#include <map>
#include <iostream>
 
int main()
{
    std::multimap <int, int> map;
 
    map.insert(std::make_pair(1, 10));
    map.insert(std::make_pair(2, 20));
    map.insert(std::make_pair(2, 30));
    map.insert(std::make_pair(2, 40));
    map.insert(std::make_pair(3, 50));
    map.insert(std::make_pair(4, 60));
    map.insert(std::make_pair(4, 70));
     
    int key = 2;   
    bool fo = false;
    for (auto itr = map.begin(); itr != map.end();)   
    {
      if (itr -> first == key)       
      {  
        if(fo)
        {
          itr = map.erase(itr); // 用erase返回的有效迭代器更新
        }
        else
        {
          fo = true;
          ++itr; // 保留第一个元素，直接移动到下一个迭代器
        }
      }
      else
      {
        ++itr;
      }
    }

     for (auto itr = map.begin(); itr != map.end(); ++itr)   
     {
        std::cout << itr -> first << "  " << itr -> second << std::endl;
     }

    return 0;
}

方案二：使用equal_range高效处理（推荐） #

std::multimap的equal_range方法可直接获取指定键对应的所有元素的迭代器范围，只需保留第一个元素，删除从第二个到范围末尾的元素，无需遍历整个容器，效率更高：

#include <map>
#include <iostream>
 
int main()
{
    std::multimap <int, int> map;
 
    map.insert(std::make_pair(1, 10));
    map.insert(std::make_pair(2, 20));
    map.insert(std::make_pair(2, 30));
    map.insert(std::make_pair(2, 40));
    map.insert(std::make_pair(3, 50));
    map.insert(std::make_pair(4, 60));
    map.insert(std::make_pair(4, 70));
     
    int key = 2;
    auto range = map.equal_range(key);
    if (range.first != range.second)
    {
        // 跳过第一个元素，删除从第二个到末尾的所有同键元素
        ++range.first;
        map.erase(range.first, range.second);
    }

     for (auto itr = map.begin(); itr != map.end(); ++itr)   
     {
        std::cout << itr -> first << "  " << itr -> second << std::endl;
     }

    return 0;
}

预期输出 #

两种方案都会得到如下输出：

1  10
2  20
3  50
4  60
4  70

内容的提问来源于stack exchange，提问作者ElemehnoP