具有重复值的Set_Intersection

Question

我认为这里描述的set_intersection STL函数：相交/实际上不是数学意义上的集合交集。假设我给出的示例更改了行：

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

因此，我想得到102020英镑。但我只得到了独特的答案。STL中是否有真正的集合交叉口？

我知道合并和set_differences是可能的，顺便说一句。看看我是不是漏掉了一些明显的东西。

Answer 1

因此，我想得到102020英镑。但我只得到了独特的答案。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个元素的交集。

显然，如果在输入中不包含重复值，它就不会在输出中。如果您正确地将代码更改为包含所有输入值，它将按需要工作(实例化)。

cplusplus.com不是一个很好的参考，如果您查看交叉点，您将看到它清楚地说明了重复元素的行为：

如果某个元素在[first1，last1)中找到m次，在[first2，last2)中找到n次，那么第一个std::min(m, n)元素将从第一个范围复制到目标范围。

即使cplusplus.com的例子很糟糕，如果它是用惯用的现代C++编写的，那么引入您的bug也会更简单、更困难：

#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或任何其他魔术数字，也不必在输出向量中创建初始元素，然后调整其大小以再次删除它们。

Answer 2

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

如果你先对它进行排序，你应该得到你期望的答案。