c++ - 具有重复值的 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

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 或任何其他魔数(Magic Number)，也无需在输出 vector ，然后调整它的大小以再次删除它们。