STL set_union с большими списками

Question

есть два

list<int> a (4,100);
list<int> b (4,200);

Я использую их как наборы, таким образом сортируются и уникальны:

a.sort();
a.unique();
b.sort();
b.unique();

Теперь два списка похожи на следующие:

a: 100
b: 200

Теперь я вычисляю объединение:

list <int> c(a.size() + b.size());
set_union(a.begin(), a.end(), b.begin(), b.end(), c.begin());

Результат хороший, но я хочу не копировать два списка в другой список. Потому что список будет очень большим и не будет содержать целые числа.

set_union(a.begin(), a.end(), b.begin(), b.end(), a.begin());

Не работает, но я на самом деле хочу, чтобы результат был в без вычисления большой копии и сделал

a = c;

aftterwards. Дополнительная проблема заключается в том, что если a = b = {100}, то результат c {100, 0}!

Есть идеи?

Answer 1

Вы можете минимизировать копирование с помощью std::set_difference, за которым следует list::merge.Оба являются линейными операциями.

std::list<int> a, b, c;

std::set_difference(b.begin(), b.end(), a.begin(), a.end(), back_inserter(c));
a.merge(c);

Список b не изменяется, а временный список c остается пустым.

Answer 2

Я думаю, что вы просто хотите list::merge

std::list<int> a, b;

a.sort();
a.unique();
b.sort();
b.unique();

a.merge(b);
a.unique();

В зависимости от ваших фактических данных, может получиться быстрее, как это

a.sort();
b.sort();
a.merge(b);
a.unique();