如何计算N个已排序集合的交集？

Question

下面的示例展示了如何计算两个集合的交集。STL是否提供了工具，允许不仅针对两个集合，而是针对N个集合执行此操作？

#include <iostream>    
#include <algorithm>
#include <vector>

int main()
{
    std::vector<int> v1 = { 1,2,9,3,4,5 };
    std::vector<int> v2 = { 9,4,2,7,4,1 };
    std::vector<int> v(v1.size() + v2.size());
    std::vector<int>::iterator it;

    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    it = std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v.begin());

    v.resize(it - v.begin());
    std::cout << "Both sets have " << (v.size()) << " elements in common:\n";
    for (it = v.begin(); it != v.end(); ++it)
    {
        std::cout << *it << ' ';
    }
    std::cout << '\n';

    return 0;
}

- Gilfoyle

---

交集是可结合的，因此要找到v1、v2、v3的交集，只需调用std::set_intersection两次：result = (v1 * v2) * v3。 - pptaszni

Answer 1

STL提供的工具只能用于两个集合，而不能用于N个集合吗？

不是。但是您可以很容易地创建一个，只需提供类似于递归可变模板的内容即可。

if constexpr部分需要C++17支持。然而，有许多示例可以在C++17之前完成。此外，由于递归调用，参数必须相反地传递，以获得您想要的行为。

(查看在线演示)

#include <vector>
#include <algorithm>  // std::set_intersection
#include <iterator>   // std::back_inserter

template<typename Container, typename... Rest>
Container NSetIntersections(
    const Container& container1, const Container& container2, Rest&&... rest) noexcept
{
    if constexpr (sizeof...(Rest) == 0)
    {
        Container result;
        std::set_intersection(container1.begin(), container1.end(),
            container2.begin(), container2.end(), std::back_inserter(result));
        return result;
    }
    else
    {
        Container result;
        std::set_intersection(container1.begin(), container1.end(),
            container2.begin(), container2.end(), std::back_inserter(result));
        return NSetIntersections(result, std::forward<Rest>(rest)...);
    }
}

int main()
{
    // sorted vectors
    std::vector<int> v1 = { 1, 2, 3, 4, 5, 6 };
    std::vector<int> v2 = { 2, 3, 4, 7, 8, 9 };
    std::vector<int> v3 = { 3, 4, 7, 200 };
    std::vector<int> v4 = { 4, 100, 200, 300 };
    std::vector<int> v5 = { 4, 100, 200 };
    // call the function like
    const auto res1 = NSetIntersections(v2, v1);              // 2 3 4
    const auto res2 = NSetIntersections(v3, v2, v1);          // 3 4
    const auto res3 = NSetIntersections(v4, v3, v2, v1);      // 4
    const auto res4 = NSetIntersections(v5, v4, v3, v2, v1);  // 4
    return 0;
}

---

为了以自然的方式将参数传递给NSetIntersections函数，我建议遵循辅助函数的方式。此外，它还可以处理将单个参数（如果错误地）传递给NSetIntersections的情况，并且与c++11兼容。 (查看在线演示)

#include <vector>
#include <algorithm>  // std::set_intersection
#include <iterator>   // std::back_inserter

namespace helper { // helper NSetIntersections functions
    template<typename Container>
    Container NSetIntersections(const Container& container1) noexcept {
        return container1;
    }

    template<typename Container>
    Container NSetIntersections(const Container& container1, const Container& container2) noexcept
    {
        Container result;
        std::set_intersection(container1.begin(), container1.end(),
            container2.begin(), container2.end(), std::back_inserter(result));
        return result;
    }

    template<typename Container, typename... Rest>
    Container NSetIntersections(
        const Container& container1, const Container& container2, Rest&&... rest) noexcept
    {
        return helper::NSetIntersections(
            helper::NSetIntersections(container1, container2), std::forward<Rest>(rest)...);
    }
}

template<typename... Containers>
auto NSetIntersections(Containers&&... rest) noexcept
  -> decltype(helper::NSetIntersections(std::forward<Containers>(rest)...))
{
    return helper::NSetIntersections(std::forward<Containers>(rest)...);
}

现在，您可以像这样使用参数调用函数：

// sorted vectors
std::vector<int> v1 = { 1, 2, 3, 4, 5, 6 };
std::vector<int> v2 = { 2, 3, 4, 7, 8, 9 };
std::vector<int> v3 = { 3, 4, 7, 200 };
std::vector<int> v4 = { 4, 100, 200, 300 };
std::vector<int> v5 = { 4, 100, 200 };
// call the function like
const auto res1 = NSetIntersections(v1);                 // 1 2 3 4 5 6 
const auto res2 = NSetIntersections(v1, v2);             // 2 3 4 
const auto res3 = NSetIntersections(v1, v2, v3);         // 3 4 
const auto res4 = NSetIntersections(v1, v2, v3, v4);     // 4
const auto res5 = NSetIntersections(v1, v2, v3, v4, v5); // 4

---

顺便提一下：在 quick-bench.com 上进行的基准测试显示（对于 5 个已排序容器），如果我们进行 N 次 std::set_intersection，性能几乎相同。

(在线快速测试)

- JeJo

---

很棒的方法！我该如何将其移植到c++11？ - Gilfoyle

这个程序的性能与n路交叉口相比如何？ - Daniel

@Dani "n路口" 你是指这个吗？https://quick-bench.com/q/kT3NFFdkFQGUMEOSO1u5vAMzlew 如果是的话，看起来是一样的！ - JeJo

@orlp，你能提供相关的参考资料吗？我认为答案在意义上是正确的，它所做的与我们对 N 个数组执行 set_intersection 相同。除了不用调用 N 次 set_intersection 或者还有更好/更高效的方法吗？ - Const

@orlp，我认为你误解了DV的原因。请仔细阅读问题。问题不是关于复杂性，而是关于N个已排序容器的交集的解决方案。而这个答案提供了解决方案。如果你有更好的想法，请随时提供它作为答案！ - JeJo

Answer 2

您可以将所有需要求交集的向量放入另一个向量中，然后创建一个函数，通过循环计算v1和v2的交集，并将其与v3进行比较，再将其与v4进行比较，以此类推...

下面是一个为您完成这个任务的函数。

using V = std::vector<std::vector<int>>;

std::vector<int> intersections(V vectors)
{
   int largest = vectors[0].size();
   for (int i = 0; i < vectors.size(); i++)
   {
      std::sort(vectors[i].begin(), vectors[i].end());
      if (vectors[i].size() > largest)
         largest = vectors[i].size();
   }

   std::vector<int> res(largest);
   std::vector<int>::iterator it;
   for (int i = 0; i < vectors.size() - 1; i++)
   {
      it = std::set_intersection(vectors[i].begin(), vectors[i].end(),
         vectors[i + 1].begin(), vectors[i + 1].end(),
         res.begin()
      );
      res.resize(it - res.begin());
      vectors[i + 1].resize(res.size());
      std::copy(res.begin(), res.end(), vectors[i + 1].begin());
   }

   return res;
}

注意：我只做了一些非常基本的测试，但应该可以工作。

这是如何调用它的。

std::vector<int> v1 = { 1,2,9,3,5 };
std::vector<int> v2 = { 9,4,2,7,4,1 };
std::vector<int> v3 = { 4,2,7 };
V vectors = { v1,v2, v3 };

auto res = intersections(vectors);
for (int i = 0; i < res.size(); i++)
   std::cout << res[i] << std::endl;

- Marko Borković

---

你的想法很好。但是它的性能比使用N+1个容器的N次std::set_intersection要差得多。请看quick-bench.com上进行的在线基准测试。 - JeJo