删除所有未找到的内容，即删除未在集合中找到的地图中的所有 key/values

Question

我试过但未能使以下内容与 std::algorithms 一起使用：我有一个 std::map<key_t,value_t> cache 和一个 std::set<key_t> selected_items，我想从 cache 中删除 key/value 对，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。但我无法连接各个部分，失败于：

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

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

Answer 1

如果您的两个容器在 key_t 上使用相同的排序顺序，您可以只遍历两个容器并删除一个容器中的元素（如果另一个容器中没有元素），而无需搜索它。 O(N) 复杂度。

不幸的是，none 标准算法可以为您执行删除操作，因为它们适用于迭代器。要使用迭代器删除它的容器对象是必需的。

Answer 2

天真的尝试：

#include <iostream>
#include <map>
#include <set>

int main() {
    std::map<int, int> m = {{1, 2}, {3, 4}, {4, 5}};
    std::set<int> s = {1, 3, 5};
    for (auto it = begin(m); it != end(m); ){
        if (s.count(it->first))
            m.erase(it++);
        else
            ++it;
    }
    for (auto &e : m){
        std::cout << e.first << ' ' << e.second << '\n';
    }
}

结合@MaximEgorushkin 的想法：

#include <iostream>
#include <map>
#include <set>

void erase_elements_from_map_that_are_not_in_set(
    std::map<int, int> &m, std::set<int> &s){   
    auto sit = begin(s);
    for (auto it = begin(m); it != end(m) && sit != end(s); ){
        while (*sit < it->first){
            ++sit;
            if (sit == end(s))
                return;
        }
        if (*sit == it->first)
            m.erase(it++);
        else
            ++it;
    }
}
int main() {
    std::map<int, int> m = {{1, 2}, {3, 4}, {4, 5}};
    std::set<int> s = {1, 3, 5};
    erase_elements_from_map_that_are_not_in_set(m, s);
    for (auto &e : m){
        std::cout << e.first << ' ' << e.second << '\n';
    }
}

您可能需要将 while 循环中的 < 替换为 s 和 m 的通用比较函数。

关于STL算法，你可以在第一个例子中使用std::find而不是count，但这很尴尬。我不知道这里有任何其他使用 STL 算法的方法，我认为不需要它们。如果您经常需要，可以将代码放在您自己的 erase_elements_from_map_that_are_not_in_set 函数中。

Answer 3

这听起来像是 erase-remove idiom 的情况：

typedef std::map<int,std::string> cache_t;
typedef std::set<cache_t::key_type> set_t;

void update_cache(cache_t& cache, const set_t& selected_items)
{
    auto test = [selected_items](const cache_t::value_type& x){
        return selected_items.find(x.first) == selected_items.end();
    };
    cache.erase(std::remove_if(cache.begin(), cache.end(), test), cache.end());
}

但这在此处是不可能的，因为错误消息表明：

32883794.cc:16:64:   required from here
/usr/include/c++/4.8/bits/stl_pair.h:170:8: error: assignment of read-only member ‘std::pair<const int, std::basic_string<char> >::first’
  first = std::forward<first_type>(__p.first);

问题是我们从 map 中只获得了 pair<const int key_t, value_t> 的 iterator，所以不能移动它的元素。

应该可以使用 std::copy_if 创建 cache 的新实例，但与使用循环的方法相比，这可能会产生大量内存开销。

Answer 4

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

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

因此你有两种可能：

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

由于您只对第二个选项感兴趣，我们可以检查例如std::set_difference() 的使用确实完全符合您的要求。
然而因为 std::map 和 std::set 的迭代器指向不同种类的对象（std::pair 和 Key），我们有小心我们的 Comparator.
一种天真的方法是简单地提供一个接受 const std::pair & 和 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;
}

删除所有未找到的内容，即删除未在集合中找到的地图中的所有 key/values

Delete all not found i.e. delete all key/values in map not found in set

c++

stl-algorithm

c++11