Если количество элементов относительно большой процент от диапазона возможных int с, вы можете получить приличную производительность из того, что по сути является упрощенным «хеш-соединением» (если использовать терминологию БД) .
(Если число целых чисел относительно небольшое по сравнению с диапазоном возможных значений, это, вероятно, не лучший подход.)
По сути, мы создаем гигантское растровое изображение, затем устанавливаем флаги только для индексов, соответствующих входным данным int s, и, наконец, восстанавливаем результат на основе этих флагов:
#include <vector>
#include <algorithm>
#include <iostream>
#include <time.h>
template <typename ForwardIterator>
std::vector<int> IntSetUnion(
ForwardIterator begin1,
ForwardIterator end1,
ForwardIterator begin2,
ForwardIterator end2
) {
int min = std::numeric_limits<int>::max();
int max = std::numeric_limits<int>::min();
for (auto i = begin1; i != end1; ++i) {
min = std::min(*i, min);
max = std::max(*i, max);
}
for (auto i = begin2; i != end2; ++i) {
min = std::min(*i, min);
max = std::max(*i, max);
}
if (min < std::numeric_limits<int>::max() && max > std::numeric_limits<int>::min()) {
std::vector<int>::size_type result_size = 0;
std::vector<bool> bitmap(max - min + 1, false);
for (auto i = begin1; i != end1; ++i) {
const std::vector<bool>::size_type index = *i - min;
if (!bitmap[index]) {
++result_size;
bitmap[index] = true;
}
}
for (auto i = begin2; i != end2; ++i) {
const std::vector<bool>::size_type index = *i - min;
if (!bitmap[index]) {
++result_size;
bitmap[index] = true;
}
}
std::vector<int> result;
result.reserve(result_size);
for (std::vector<bool>::size_type index = 0; index != bitmap.size(); ++index)
if (bitmap[index])
result.push_back(index + min);
return result;
}
return std::vector<int>();
}
void main() {
// Basic sanity test...
{
std::vector<int> v1;
v1.push_back(2);
v1.push_back(2000);
v1.push_back(229013);
v1.push_back(-2243);
v1.push_back(-530);
std::vector<int> v2;
v1.push_back(2);
v2.push_back(243);
v2.push_back(90120);
v2.push_back(329013);
v2.push_back(-530);
auto result = IntSetUnion(v1.begin(), v1.end(), v2.begin(), v2.end());
for (auto i = result.begin(); i != result.end(); ++i)
std::cout << *i << std::endl;
}
// Benchmark...
{
const auto count = 10000000;
std::vector<int> v1(count);
std::vector<int> v2(count);
for (int i = 0; i != count; ++i) {
v1[i] = i;
v2[i] = i - count / 2;
}
std::random_shuffle(v1.begin(), v1.end());
std::random_shuffle(v2.begin(), v2.end());
auto start_time = clock();
auto result = IntSetUnion(v1.begin(), v1.end(), v2.begin(), v2.end());
auto end_time = clock();
std::cout << "Time: " << (((double)end_time - start_time) / CLOCKS_PER_SEC) << std::endl;
std::cout << "Union element count: " << result.size() << std::endl;
}
}
Это печатает ...
Time: 0.402
... на моей машине.
Если вы хотите получить входные данные int s от чего-то другого, кроме std::vector<int>, вы можете реализовать свой собственный итератор и передать его в IntSetUnion.