找到两组并集的大小？

Question

有没有办法找到两个集合并集的大小。我知道可以做到这一点

vector < int > s3( s1.size() , s2.size() ); 
auto it=set_union( s1.begin() , s1.end() , s2.begin() ,s2.end(), s3.begin());
int size = it - s3.begin();

打印尺寸

示例

s1 = {2 4 5 6}   size 4

s2 = {1 4 5 9 10}  size 5

s3 = {1 2 4 5 6 9 10}  size 7

complexity of set_union is 2*(s1 size + s2 size)-1

有没有其他方法可以更快地获取两个集合并集的大小，我只需要大小而不希望形成新的并集集的值。如果您知道更快的方法，请提出建议。

Answer 1

一个明显的方法是执行与 set_union 相同的迭代，但不是复制元素，而是增加一个计数器。这使时间复杂度保持不变，但完全避免了 space 用法。

理论上，可以设计一个只计算元素的 OutputIterator，这样 set_union 算法就可以重用。是否值得让你的迭代器完全按照 STL 期望的方式嘎嘎作响是一个不同的问题......重新实现 set_union 只做计数可能更容易。

Answer 2

您可以将计数迭代器放在 set_union 的最后一个参数中。例如

int count = 0;
it=set_union( s1.begin() , s1.end() , s2.begin() ,s2.end(), boost::make_function_output_iterator([&count](int){ ++count; }));

或该输出迭代器的非增强等价物

struct counter {
    using difference_type = void;
    using value_type = void;
    using pointer = void;
    using reference = void;
    using iterator_category = std::output_iterator_tag;
    int count = 0;
    void operator&(int) { ++count }
    counter& operator++ { return *this; }
};

找到两组并集的大小？

find size of union of two sets?

c++

set

set-union