найти размер объединения двух наборов?
Есть ли способ найти размер объединения двух наборов.
Я знаю, могу это сделать
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
Есть ли какой-либо другой способ получить размер объединения из двух наборов более быстрым методом, мне просто нужно, чтобы размер не требовал формирования значений нового объединенного набора.
Если вы знаете более быстрый метод, пожалуйста, предложите.
Решение
Вы можете просто добавить счетчик в последнем аргументе для 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; }
};
Другие решения
Один очевидный способ — выполнить ту же итерацию set_union делает, но вместо того, чтобы копировать элементы, просто увеличьте счетчик. Это оставляет сложность времени неизменной, но полностью исключает использование пространства.
Теоретически, можно разработать OutputIterator который просто считает элементы так, чтобы set_union алгоритм может быть использован повторно. Стоит ли тратить время на то, чтобы заставить ваш итератор крякнуть именно так, как этого ожидает STL, — это другой вопрос … Повторная реализация set_union сделать просто подсчет может быть проще.