Set_Intersection 具有重复值

Question

我认为这里描述的 set_intersection STL 函数：http://www.cplusplus.com/reference/algorithm/set_intersection/ 在数学意义上并不是真正的集合交集。假设给出的示例我更改了行：

int first[] = {5,10,15,20,20,25};
int second[] = {50,40,30,20,10,20};

我想得到 10 20 20 作为结果。但我只得到独特的答案。 STL中有真集交集吗？

我知道合并和 set_differences 的组合是可能的，顺便说一句。只是检查我是否遗漏了一些明显的东西。

Answer 1

set_intersection 要求对两个范围进行排序。在您提供的数据中，second 未排序。

如果你先排序，你应该会得到你预期的答案。

Answer 2

I would like to get 10 20 20 as a result. But I only get unique answers. Is there a true set intersection in STL?

std::set_intersection 随心所欲。

您可能得到错误的答案，因为您没有正确更新代码。如果将集合更改为包含 6 个元素，则需要更新对它们进行排序的行：

std::sort (first,first+5);   // should be first+6
std::sort (second,second+5); // should be second+6

并且还将对 set_intersection 的调用更改为使用 first+6 和 second+6。否则你只对每个集合的前5个元素进行排序，并且只得到前5个元素的交集。

显然，如果您不在输入中包含重复值，它就不会出现在输出中。如果您正确更改代码以包含所有输入值，它将按您的需要工作 (live example)。

cplusplus.com 不是一个好的参考，如果您查看 http://en.cppreference.com/w/cpp/algorithm/set_intersection，您会发现它清楚地说明了重复元素的行为：

If some element is found m times in [first1, last1) and n times in [first2, last2), the first std::min(m, n) elements will be copied from the first range to the destination range.

即使 cplusplus.com 中的示例很糟糕，如果它是用惯用的现代 C++ 编写的，那么引入错误会更简单，也更难：

#include <iostream>     // std::cout
#include <algorithm>    // std::set_intersection, std::sort
#include <vector>       // std::vector

int main () {
  int first[] = {5,10,15,20,20,25};
  int second[] = {50,40,30,20,10,20};

  std::sort(std::begin(first), std::end(first));
  std::sort(std::begin(second), std::end(second));

  std::vector<int> v;
  std::set_intersection(std::begin(first), std::end(first),
                        std::begin(second), std::end(second),
                        std::back_inserter(v));                                               

  std::cout << "The intersection has " << v.size() << " elements:\n";
  for (auto i : v)
    std::cout << ' ' << i;
  std::cout << '\n';
}

这会自动处理正确数量的元素，而无需明确说明 5 或 6 或任何其他幻数，也无需在输出向量中创建初始元素然后调整大小以再次删除它们。

Set_Intersection 具有重复值

Set_Intersection with repeated values

c++

stl

intersection