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

Answer 2

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

从理论上讲，可以设计一种OutputIterator只计算元素的方法，以便set_union可以重用算法。这是否值得让您的迭代器完全按照 STL 期望的方式嘎嘎作响，这是一个不同的问题……重新实现set_union只进行计数可能会更容易。