c++ STL设置差异
C++ STL集合数据结构有集合差分运算符吗?
Does the C++ STL set data structure have a set difference operator?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
C++ STL集合数据结构有集合差分运算符吗?
Does the C++ STL set data structure have a set difference operator?
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
接受
或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论(10)
是的,有,它位于
中,名为:std::set_difference
。 用法是:最后,集合
result
将包含s1-s2
。Yes there is, it is in
<algorithm>
and is called:std::set_difference
. The usage is:In the end, the set
result
will contain thes1-s2
.是的,算法标头中有一个 set_difference 函数。
编辑:
仅供参考,集合数据结构能够有效地使用该算法,如其 文档。 该算法不仅适用于集合,还适用于已排序集合上的任何一对迭代器。
正如其他人提到的,这是一种外部算法,而不是一种方法。 想必这适合您的应用程序。
Yes, there is a set_difference function in the algorithms header.
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.
再次,助推救援:
setDifference 将包含 set0-set1。
Once again, boost to the rescue:
setDifference will contain set0-set1.
不是语言意义上的“运算符”,但标准库中有set_difference算法:
http://www.cplusplus.com/reference/algorithm/set_difference.html
当然,也存在其他基本集合操作 - (联合等),如“另请参阅”部分的建议链接文章的结尾。
Not an "operator" in the language sense, but there is the set_difference algorithm in the standard library:
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.
所选答案是正确的,但存在一些语法错误。
代替
使用
代替
使用
The chosen answer is correct, but has some syntax errors.
Instead of
use
Instead of
use
C++ 没有定义集合差分运算符,但您可以定义自己的运算符(使用其他响应中给出的代码):
C++ does not define a set difference operator but you can define your own (using code given in other responses):
不是一种方法,但有外部算法函数 set_difference
http://www.sgi.com /tech/stl/set_difference.html
Not as a method but there's the external algorithm function set_difference
http://www.sgi.com/tech/stl/set_difference.html
显然,确实如此。
SGI - set_difference
Apparently, it does.
SGI - set_difference
我在这里看到的所有答案都是 O(n)。 这不是更好吗?:
这似乎是正确的做法。 我不确定如何处理
Compare
的类型未完全指定其行为的情况,就像Compare
是std:: function
,但除此之外,这似乎工作正常,应该像 O((num Overlap) • log(lhs.size()
))。在
lhs
不包含*i
的情况下,可能可以通过执行 O(log(rhs.size())) 搜索
rhs
的下一个元素,即 >=lhs
的下一个元素。 这将优化lhs = {0, 1000}
和rhs = {1, 2, ..., 999}
的情况,以在对数时间内进行减法。All of the answers I see here are O(n). Wouldn't this be better?:
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 ifCompare
is astd::function<bool(int,int)>
, but aside from that, this seems to work right and should be like O((num overlapping) • log(lhs.size()
)).In the case that
lhs
doesn't contain*i
, it's probably possible to optimize further by doing an O(log(rhs.size()
)) search for the next element ofrhs
that's >= the next element oflhs
. That would optimize the case thatlhs = {0, 1000}
andrhs = {1, 2, ..., 999}
to do the subtraction in log time.我们可以使用
can we just use