删除所有未找到的,即删除在集合中找不到的地图中的所有键/值

Question

我试过但未能得到以下工作std::algorithms:我有aa std::map<key_t,value_t> cache和a 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使用a std::pair<const Key, T>使复制/移动std::pairs不可能(注意const)
• 没有算法可以执行实际调用,std::map<>::erase()因为它会使当前迭代器无效
• 一个标准的方法来重新排序元素cache(例如简单的调用std::partition),然后删除最后一个元素因为点1而cache 无法工作

因此,您有两种可能性:

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

由于您只对第二个选项感兴趣,因此我们可以检查例如使用std::set_difference()它确实完全符合您的要求.
但是由于它的迭代器std::map和std::set指向不同种类的对象(std::pair和Key),我们必须小心我们的Comparator.
一种天真的方法就是提供一个带a const std::pair &和a 的函数const Key &.但这不适用于我的机器!(我不知道这是不是一个bug ... 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;
}