C++ STL 集合数据结构有集合差分运算符吗?
10 回答
是的,它在<algorithm>
并且被称为:std::set_difference
. 用法是:
#include <algorithm>
#include <set>
#include <iterator>
// ...
std::set<int> s1, s2;
// Fill in s1 and s2 with values
std::set<int> result;
std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
std::inserter(result, result.end()));
最后,该集合result
将包含s1-s2
.
是的,算法标题中有一个set_difference函数。
编辑:
仅供参考,如其文档中所述,集合数据结构能够有效地使用该算法。该算法不仅适用于集合,还适用于排序集合上的任何一对迭代器。
正如其他人所提到的,这是一种外部算法,而不是一种方法。大概这对您的应用程序来说很好。
不是语言意义上的“运算符”,但标准库中有 set_difference 算法:
http://www.cplusplus.com/reference/algorithm/set_difference.html
当然,其他基本集合操作也存在 - (联合等),正如链接文章末尾的“另见”部分所建议的那样。
C++ 没有定义集合差分运算符,但您可以定义自己的(使用其他响应中给出的代码):
template<class T>
set<T> operator -(set<T> reference, set<T> items_to_remove)
{
set<T> result;
std::set_difference(
reference.begin(), reference.end(),
items_to_remove.begin(), items_to_remove.end(),
std::inserter(result, result.end()));
return result;
}
选择的答案是正确的,但有一些语法错误。
代替
#include <algorithms>
利用
#include <algorithm>
代替
std::insert_iterator(result, result.end()));
利用
std::insert_iterator<set<int> >(result, result.end()));
再次,助推救援:
#include <string>
#include <set>
#include <boost/range/algorithm/set_algorithm.hpp>
std::set<std::string> set0, set1, setDifference;
boost::set_difference(set0, set1, std::inserter(setDifference, setDifference.begin());
setDifference 将包含 set0-set1。
不是作为一种方法,而是有外部算法函数 set_difference
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
显然,确实如此。
我在这里看到的所有答案都是 O(n)。这不是更好吗?:
template <class Key, class Compare, class Allocator>
std::set<Key, Compare, Allocator>
set_subtract(std::set<Key, Compare, Allocator>&& lhs,
const std::set<Key, Compare, Allocator>& rhs) {
if (lhs.empty()) { return lhs; }
// First narrow down the overlapping range:
const auto rhsbeg = rhs.lower_bound(*lhs.begin());
const auto rhsend = rhs.upper_bound(*lhs.rbegin());
for (auto i = rhsbeg; i != rhsend; ++i) {
lhs.erase(*i);
}
return std::move(lhs);
}
这似乎做对了。我不确定如何处理Compare
's 类型未完全指定其行为的情况,如 if Compare
is a std::function<bool(int,int)>
,但除此之外,这似乎工作正常,应该像 O((num 重叠) •日志(lhs.size()
))。
在lhs
不包含的情况下,*i
可以通过 O(log( rhs.size()
)) 搜索rhs
>= 的下一个元素来进一步优化lhs
。这将优化这种情况lhs = {0, 1000}
并rhs = {1, 2, ..., 999}
在对数时间内进行减法。
我们可以用吗
set_difference(set1.begin(), set1.end(), set2.begin(). set2,end(),std::back_inserter(result)).