如果std::映射中不存在密钥，如何有效地从std::unordered_set中删除该密钥

Question

我有一个std::map和一个具有相同键的std::unordered_set。

我想从集合中删除地图中不存在的所有关键点。

我的想法是做以下事情：

#include <map>
#include <unordered_set>
int main()
{
std::map<uint64_t, std::string> myMap = { 
{1, "foo"},
{2, "bar"},
{3, "morefoo"},
{4, "morebar"} 
};
std::unordered_set<uint64_t> mySet = { 1, 2, 3, 4, 123 };
for (const auto key : mySet)
{
const auto mapIterator = myMap.find(key);
if (myMap.end() == mapIterator)
mySet.erase(key);
}
return 0;
}

然后每隔几秒钟在计时器回调中调用它，但是，当试图从mySet中删除密钥123时，上面的代码段抛出断言，声明：

列表迭代器不可递增。

问题是，即使它没有抛出异常，我觉得这个想法也远非优雅/最佳。我想知道是否有更好的方法来解决这个问题？

谢谢。

Answer 1

正如这个问题的答案所述，如何在迭代映射时从映射中移除？在for范围循环中迭代容器时，不能擦除容器中的元素，所以代码应该使用迭代器。由于已经提供了这样的答案，我不会重复

为了提高效率，您有一种非常错误的方法——您在std::map中进行查找，同时迭代std::unordered_set，这应该是相反的，因为std::unorederd_set提供了更快的查找时间(否则，使用它代替std::set是没有意义的(。一种可能的方法是创建一个副本：

auto copySet = mySet;
for( const auto &p : myMap )
copySet.erase( p.first );
for( const auto v : copySet )
mySet.erase( v );

这可能更有效，但这取决于您的数据。为容器选择适当数据类型的更好方法。

注意：我所说的错误方法是指仅针对您问题中出现的这种特定情况的效率，但这似乎是一个更大程序的一部分，此解决方案可能适合它，因为当此数据结构正常工作时，可能会有更重要的情况。

Answer 2

如评论中所述

for (const auto key : mySet)
{
const auto mapIterator = myMap.find(key);
if (myMap.end() == mapIterator)
mySet.erase(key);
}

将具有未定义的行为。从mySet中擦除元素123时，会使基于范围的for循环正在使用的迭代器无效。之后不允许递增迭代器。你可以做的是切换到一个常规的for循环，这样你就可以控制迭代器何时像一样递增

for (auto it = mySet.begin(); it != mySet.end();)
{
if (myMap.find(*it) == myMap.end())
it = mySet.erase(it);
else
++it;
}

现在您总是有一个有效的迭代器，因为erase将返回下一个有效迭代器。