假设我有一张 map ,其值如下所述:
std::map<int, std::set<int>> myMap;
key 0: 1,2,3,4,5,6,7,8,9,10
key 1: 1,2,3,4,5,6
key 2: 4,5,6,7
key 3: 6,7
现在,我想删除键 0 中存在于其后的其他键中的所有值。同样对于键 1 等等。 因此,最终输出 (myMap) 应如下所示:
key 0: 8,9,10
key 1: 1,2,3
key 2: 4,5
key 3: 6,7
据我所知,在 map 中按值搜索并不是那么容易。对于我的代码,由于我的数据非常大,因此按值搜索是不可行的。这会很费时。
有没有更好的方法来执行此操作而无需遍历以下每个键中的每个值来删除公共(public)值?
最佳答案
std::set<int> to_remove;
for(auto&& e:backwards(myMap)) {
std::set<int> r;
std::set_difference(
r.second.begin(), r.second.end(),
to_remove.begin(), to_remove.end(),
std::inserter(r)
);
std::copy(r.second.begin(), r.second.end(), std::inserter(to_remove));
r.second = std::move(r);
}
backwards
是:
template<class It>
struct range_t {
It b, e;
It begin() const { return b; }
It end() const { return e; }
};
template<class C>
auto backwards( C& c )
-> range_t< typename C::reverse_iterator >
{
return {c.rbegin(), c.rend()};
}
template<class C>
auto backwards( C const& c )
-> range_t< typename C::const_reverse_iterator >
{
return {c.rbegin(), c.rend()};
}
这使得向后迭代容器变得快速和容易。
这是 O(nlgn),而您的解决方案是 O(n^2lgn)。
关于c++ - 删除映射c++中其他键值中已经存在的那些值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52280591/