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

标签 c++ c++11 stl-algorithm

我试过但未能使以下与 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::removestd::map::erase .但我无法连接各个部分,失败于:

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

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

最佳答案

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

  • 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::pairKey ),我们必须小心我们的 Comparator .
一种天真的方法是简单地提供一个接受 const std::pair & 的函数。和一个 const Key & .但这在我的机器上不起作用!(我不知道这是否是一个错误...... Mac OS X 10.10.5)因为std::set_difference()决定有时调用 Comparator参数顺序相反......

长话短说,这里有一个解决方案 SFINAEstd::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;
}

关于c++ - 删除所有未找到的,即删除映射中未在集合中找到的所有键/值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32883794/

相关文章:

c++ - 如何找到 key 大于 val 的映射的第一个元素

c++ - 如何使用visual studio c++绘制图表

c++ - boost.log v2,如何获取当前日志文件名

c++ - const char myStr[] = "hello"和 const char* myStr = "hello"有什么区别

c++ - 可变参数模板之谜

c++ - 在 Mac 上编译 C++11 代码?

c++ - 类模板中文字运算符的Friend声明

unit-testing - 单元测试移动/复制构造函数的策略?

c++ - 了解 std::transform 以及如何打败它

c++ - C++ 11中的最小和最大可变参数模板变体?