时间戳

首页 > 解决方案 > 多套高效安全交汇

c++ - 多套高效安全交汇

问题描述

这是一个 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;
}

标签： c++set

解决方案

正如您在cppreference上所读到的，

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

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

作为验证的证明，我可以告诉你我已经复制了你的代码，编译它，运行它，对我来说它会打印出来23，所以你的正确结果只是一个巧合。

因此，看起来不得不暂时依赖另一个。

STL 似乎不包含交叉两个以上集合的解决方案，您甚至不能std::set_intersection以嵌套方式使用（例如result = my_set_intersection(set_1, my_set_intersection(set_2,set_3))，原因非常简单：算法的接口被迭代器“污染”，即它需要集合的开始和结束迭代器，而不是集合本身作为输入；它还返回一个迭代器。

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

推荐阅读