在循环中擦除unordered_map中的元素

Question

StackOverflow上有几个答案表明以下循环是一种很好的方法来擦除std::unordered_map满足某些谓词的元素pred:

std::unordered_map<...> m;
auto it = m.begin();
while (it != m.end())
{
    if (pred(*it))
        it = m.erase(it);
    else
        ++it;
}

我对C++ 11(而不是C++ 14)特别感兴趣,而cppreference.com上的以下不祥之处表明上述循环依赖于未定义的行为,并且可能在C++ 11中无效:

保留未擦除元素的顺序(这使得可以在迭代容器时擦除单个元素)(从C++ 14开始)

另请参见标题2356.无序关联容器中擦除的稳定性,其中包含对第754页的工作草案N3797第14项的请求的措辞更改(附加短语开头",并保留相对顺序......").

这个措辞与N3797有关.

按照指示修改[unord.req],p14:

-14- insert和emplace成员不应影响对容器元素的引用的有效性,但可能使容器的所有迭代器无效.擦除成员应仅使迭代器和对已擦除元素的引用无效,并保留未擦除元素的相对顺序.

如果我对cppreference.com的注释的解释是正确的,并且上面的循环依赖于C++ 11中的未定义行为,那么在C++ 11中解决这个问题的最有效方法是什么？

Answer 1

为了符合C++ 11,你很遗憾在解决这个问题上有点受限.你的选择基本归结为:

1. 迭代unordered_map并构建一个要删除的键列表,如下所示:

   //std::unordered_map<...> mymap;
   std::vector<decltype(mymap)::key_type> vec;
   for (auto&& i : mymap)
       if (/*compare i*/)
           vec.emplace_back(i.first);
   for (auto&& key : vec)
       mymap.erase(key);
   

2. 迭代对象并重置如果我们找到要删除的东西 - 我真的只推荐这个用于小数据集.那些觉得goto无条件坏的人,嗯,这个选择可以说是糟糕的.

   //std::unordered_map<...> mymap;
   reset:
   for (auto&& i : mymap)
       if (/*compare i*/) {
           mymap.erase(i.first);
           goto reset;
       }
   

3. 作为一个有点外出的选项,你也可以创建一个新的unordered_map并移动你想要保留的元素.当你有更多要删除而不是保留时,这可以说是一个不错的选择.

   //std::unordered_map<...> mymap;
   decltype(mymap) newmap;
   for (auto&& i : mymap)
       if (/*i is an element we want*/)
           newmap.emplace(std::move(i));
   mymap.swap(newmap);
   

Answer 2

使用erase_if（c ++ 20）而不是循环（请参阅https://en.cppreference.com/w/cpp/container/unordered_map/erase_if）

从映射中删除奇数键的示例：

std::unordered_map<int, char> data {{1, 'a'},{2, 'b'},{3, 'c'},{4, 'd'},
                                    {5, 'e'},{4, 'f'},{5, 'g'},{5, 'g'}};

const auto count = std::erase_if(data, [](const auto& item) {
    auto const& [key, value] = item;
    return (key & 1) == 1;
});

Answer 3

始终首先查阅 stl 算法

这似乎是想要的： http://www.cplusplus.com/reference/algorithm/remove_if/

有关概述： http: //www.cplusplus.com/reference/algorithm/

编辑 cppreference 在网站底部有一个类似的示例。它适用于 c++11 编译器。