c++之如何计算 N 个有序集的交集

下面的例子展示了如何计算两个集合的交集。 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; 
} 

请您参考如下方法:

Does the STL provide tools that allow to do this not only for 2 but for N sets?

不。但是您可以通过提供 recursive Variadic template 轻松制作一个如下。
if constexpr 部分需要 c++17支持。不过例子很多， how you could do it for prior to c++17 .此外，由于递归调用，参数必须以相反的顺序传递，以获得您尝试的行为。
( See Online Demo )

#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兼容的。
( See Online Demo )

#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 .

( See Online Quick-bench )