CODEWITHSUNDEEP
c++stl
Joachim
Joachim

Reputation: 3260

STL set_union with big lists

there are two

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

I use them as sets thus are sorted and uniqued:

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

Now the two list are like the following:

a: 100
b: 200

Now I calculate the union:

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

The result is fine but what I want is not to copy the two lists into another list. Because the list will be very big and do not contain ints for real.

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

Does not work bot i actually want the result to be in a without calulating a big copy and do 

a = c;

aftterwards. An additional Problem is that if a = b = {100} then the result c is {100, 0}!

Any ideas?

Upvotes: 1

Views: 506

Answers (2)

sehe
sehe

Reputation: 393769

I think you simply want list::merge

std::list<int> a, b;

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

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

Depending on your actual data it might turn out faster like this

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

Upvotes: 2

Blastfurnace
Blastfurnace

Reputation: 18652

You can minimize copying with a std::set_difference followed by list::merge. Both are linear operations.

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

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

The b list isn't modified and the temporary c list is left empty.

Upvotes: 3

Related Questions