两套以上高效安全交叉

Question

这是一个 C++ 程序，它使用

std::set_intersection

两次来计算 3 个集合的交集（然后打印结果）。它产生了预期的结果

3

但是：

1. 在第二次调用 set_intersection 时传入“newset”作为源集和目标集是否安全？据我了解，通过 begin() 和 end() 我传递了对这些集合的引用，所以我最终可能会意外地覆盖我的输入吗？

2. 这里有更有效的方法吗？我应该按大小升序迭代我的集合吗？与多次调用 std::set_intersection 相比，滚动我自己的多集交集是否有任何优势？

#include <algorithm>
#include <iostream>
#include <set>

int main()
{
    std::set<int> set_1 = {1,2,3}, set_2 = {2,3}, set_3 = {3}, newset;
    
    std::set_intersection(set_1.begin(), set_1.end(),
                  set_2.begin(), set_2.end(),
                  std::inserter(newset, newset.begin()));

    std::set_intersection(newset.begin(), newset.end(),
                  set_3.begin(), set_3.end(),
                  std::inserter(newset, newset.begin()));

    for(std::set<int>::iterator it = newset.begin(); it != newset.end(); it++){
        std::cout << *it;
    }
    std::cout << std::endl;
    
    return 0;
}

Answer 1

正如您可以阅读cppreference，

[...] 结果范围不能与任一输入范围重叠。

所以你处于未定义的行为领域。

作为验证这一点的证明，我可以告诉你，我已经复制了你的代码，编译了它，运行了它，对我来说它打印了

23

，所以你的正确结果只是一个巧合。

所以看来只能暂时依赖另外一个了。

STL 似乎不包含两个以上集合相交的解决方案，你甚至不能以嵌套方式使用

std::set_intersection

（例如

result = my_set_intersection(set_1, my_set_intersection(set_2,set_3))

，原因很简单：算法的接口是“被污染的”） “通过迭代器，即它采用集合的开始和结束迭代器，而不是集合本身作为输入；并且它还返回一个迭代器。

Porbically Boost 有一些有用的东西，但我还没有找到。

Answer 2

问题1：

不安全，正如@Enrico所说，它与输入范围之一重叠。

问题2：

你可以尝试参考一个经典问题的思路：使用priority_queue合并k个排序列表（或者称为堆，或者使用std::set代替，因为你需要查找某个元素是否存在）。集合合并问题的思想与此类似，您可以将复杂度从 O(nk) 提高到 O(nlogk)，其中 n 是所有元素的数量，并且传输成本非常低。也许 3 组会是有效的，因为 3 太小，无法体现该算法的优势，但是当 k 远大于 3 时，原始方法会比这个慢得多。

注意，在分析时间复杂度时，虽然很多集合操作的成本是 O(logn)，但迭代整个集合不是 O(nlogn)，而是 O(n)。

Answer 3

我能想到的最有效的方法是可读且易于理解。

std::swap

通过

std::set

初始化或插入操作减少了一些开销。

#include <algorithm>
#include <set>
#include <vector>

template<typename External>
std::set<External> intersectSets(const std::vector<std::set<External>>& partialResults)
{
  // Uses suggested sort to reduce the total number of operations if there happens to be a set with no or very few values compared to the rest.
  std::sort(
    partialResults.begin(), 
    partialResults.end(), 
    [](std::vector<External>& a, 
       std::vector<External>& b)
    {
      return a.size() > b.size();
    });

  if(partialResults.size() > 0)
  {
    std::set<External> results{ partialResults[0] };
    for(uint32_t i = 1; i < partialResults.size(); i++)
    {
      std::set<External> intersect{};
      std::set_intersection(
        results.begin(), 
        results.end(), 
        partialResults[i].begin(), 
        partialResults[i].end(), 
          std::inserter(intersect, intersect.begin()));
      std::swap(results, intersect);
    }
    return results;
  }
  return std::set<External>{};
}