c++ - 删除所有未找到的，即删除映射中未在集合中找到的所有键/值

Question

我试过但未能使以下与 std::algorithms 一起使用: 我有一个 std::map<key_t,value_t> cache和一个 std::set<key_t> selected_items我想从 cache 中删除键/值对, 除了包含在 selected_items 中的键.

这是我在没有算法的情况下写的:

//This could really be written better with std::algorithms but time...
//Delete old
for (auto pair = cache.begin(); pair != cache.end(); ) {
    if (selected_items.find(pair->first) == selected_items.end())
        pair = cache.erase(pair);
    else
        ++pair;
}

要使用算法库，我想我需要使用 std::set_difference具有比较功能和 std::remove或 std::map::erase .但我无法连接各个部分，失败于:

1. 什么是正确的比较函数？
2. 我是否必须使用应删除的键生成一个临时集，或者我是否可以直接使用输出迭代器进行删除/删除？

我的代码应该是什么样子？

Answer 1

这其实是个很有意思的问题!原来这其中牵扯到几个难点……

• std::map使用 std::pair<const Key, T>这使得复制/移动 std::pairs不可能(注意 const )
• 没有算法可以执行对 std::map<>::erase() 的实际调用因为它会使当前迭代器无效
• 对cache 中的元素重新排序的标准方法(例如简单调用 std::partition )然后删除 cache 中的最后一个元素由于第 1 点无法工作

因此你有两种可能:

• 构建您自己的调用 erase 的循环适本地
• 使用<algorithm>和存储结果的第二个 map

由于您只对第二个选项感兴趣，我们可以检查例如使用std::set_difference()这确实完全符合您的要求。
但是自std::map 的迭代器以来和 std::set指向不同种类的对象( std::pair 和 Key )，我们必须小心我们的 Comparator .
一种天真的方法是简单地提供一个接受 const std::pair & 的函数。和一个 const Key & .但这在我的机器上不起作用!(我不知道这是否是一个错误...... Mac OS X 10.10.5)因为std::set_difference()决定有时调用 Comparator参数顺序相反......

长话短说，这里有一个解决方案 SFINAE和 std::set_difference() :

#include <map>
#include <set>
#include <iterator>
#include <algorithm>

using Key = int;
using Value = char;

using Pair = std::map<Key,Value>::value_type;

struct Comparator
{
    // Maybe use a custom comparator instead of '<' (see std::set documentation)
    template<class P, class K> auto operator()( const P &p, const K &k ) -> decltype(p.first < k)
    { return (p.first < k); }
    template<class P, class K> auto operator()( const K &k, const P &p ) -> decltype(k < p.first)
    { return (k < p.first); }
};

int main( void )
{
    std::map<Key,Value> cache = { {1, 'a'}, {2, 'b'}, {3, 'c'}, {4, 'd'} };
    std::set<Key> selected_items = { 2, 4 };

    std::map<Key,Value> new_cache;
    std::set_difference( cache.begin(), cache.end(),
                        selected_items.begin(), selected_items.end(),
                        std::inserter( new_cache, new_cache.end() ),
                        Comparator() );
    cache = std::move( new_cache ); // Don't use new_cache from here on

    return 0;
}