如何计算 N 个有序集的交集？

Question

下面的例子展示了如何计算两个集合的交集。STL 是否提供了不仅可以为 2 组而且可以为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;
}

Answer 1

STL 是否提供了不仅可以2为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)...);
}

现在你可以像这样使用 args 调用函数：

// 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。

（见在线快速工作台）