c++ - 找到两组并集的大小？

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 的最后一个参数中。例如

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; }
};