C++ STL集差异
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/283977/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
c++ STL set difference
提问by Steve
Does the C++ STL set data structure have a set difference operator?
C++ STL 集合数据结构有集合差运算符吗？
回答by PierreBdR
Yes there is, it is in <algorithm>and is called: std::set_difference. The usage is:
是的，它在<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()));
In the end, the set resultwill contain the s1-s2.
最后，该集合result将包含s1-s2.
回答by Mr Fooz
Yes, there is a set_differencefunction in the algorithms header.
是的，算法标题中有一个set_difference函数。
Edits:
编辑：
FYI, the set data structure is able to efficiently use that algorithm, as stated in its documentation. The algorithm also works not just on sets but on any pair of iterators over sorted collections.
仅供参考，集合数据结构能够有效地使用该算法，如其文档中所述。该算法不仅适用于集合，还适用于排序集合上的任何一对迭代器。
As others have mentioned, this is an external algorithm, not a method. Presumably that's fine for your application.
正如其他人所提到的，这是一种外部算法，而不是一种方法。大概这对您的应用程序没问题。
回答by philsquared
Not an "operator" in the language sense, but there is the set_difference algorithm in the standard library:
不是语言意义上的“运算符”，而是标准库中有 set_difference 算法：
http://www.cplusplus.com/reference/algorithm/set_difference.html
http://www.cplusplus.com/reference/algorithm/set_difference.html
Of course, the other basic set operations are present too - (union etc), as suggested by the "See also" section at the end of the linked article.
当然，其他基本集合操作也存在 - （联合等），如链接文章末尾的“另请参阅”部分所建议的那样。
回答by strickli
Once again, boost to the rescue:
再次，助推救援：
#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 will contain set0-set1.
setDifference 将包含 set0-set1。
回答by astraujums
C++ does not define a set difference operator but you can define your own (using code given in other responses):
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;
}
回答by astraujums
The chosen answer is correct, but has some syntax errors.
选择的答案是正确的，但有一些语法错误。
Instead of
代替
#include <algorithms>
use
用
#include <algorithm>
Instead of
代替
std::insert_iterator(result, result.end()));
use
用
std::insert_iterator<set<int> >(result, result.end()));
回答by Ben
All of the answers I see here are O(n). Wouldn't this be better?:
我在这里看到的所有答案都是 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);
}
That seems to do the right thing. I'm not sure how to deal with the case that Compare's type doesn't fully specify its behavior, as in if Compareis a std::function<bool(int,int)>, but aside from that, this seems to work right and should be like O((num overlapping) ? log(lhs.size())).
这似乎做对了。我不确定如何处理Compare's 类型没有完全指定其行为的情况，就像 ifCompare是 a 一样std::function<bool(int,int)>，但除此之外，这似乎工作正常，应该像 O((num重叠) ？日志（lhs.size()））。
In the case that lhsdoesn't contain *i, it's probably possible to optimize further by doing an O(log(rhs.size())) search for the next element of rhsthat's >= the next element of lhs. That would optimize the case that lhs = {0, 1000}and rhs = {1, 2, ..., 999}to do the subtraction in log time.
在lhs不包含的情况下，*i可能可以通过rhs.size()对 的下一个元素进行O(log( )) 搜索来进一步优化rhs>= 的下一个元素lhs。这将优化这种情况lhs = {0, 1000}并rhs = {1, 2, ..., 999}在对数时间内进行减法。
回答by Ian G
Not as a method but there's the external algorithm function set_difference
不是作为一种方法，而是有外部算法函数 set_difference
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
回答by LeppyR64
回答by user1830108
can we just use
我们可以用吗
set_difference(set1.begin(), set1.end(), set2.begin(). set2,end(),std::back_inserter(result)).
