CODEWITHSUNDEEP
c++oopstl
Joachim
Joachim

Reputation: 3270

Merging a lot of containers with STL Algorithms

I have a lot of lists, vectors, sets ... (what ever you prefer) of pointers called RealAlgebraicNumberPtr to certain class. They are sorted.

I want to merge them and of course I want to do it fast and efficient.

What is the best choice? std::merge ? Or maybe std::set? I can provide both an < and == ordering.

Any ideas?

Upvotes: 0

Views: 246

Answers (2)

Bj&#246;rn Pollex
Bj&#246;rn Pollex

Reputation: 76808

std::merge is as efficient as it gets. Which underlying container you use depends on your requirements. std::vector has the smallest memory-overhead of all standard containers, so if your data are large, you should stick with that.

If you use std::vector, you should resize the target-vector before merging to avoid reallocations (you should be able to calculate the required size up-front), instead of using an std::back_inserter.

Upvotes: 0

sehe
sehe

Reputation: 393064

As mentioned, std::merge is ok.

Only for std::list, you can profit from the optimization that std::list::merge member function implements: it splices the list nodes from the source into the target. That way, the source list will become empty, but it will avoid resource (re)allocation

Re: std::set

you could in fact std::merge into a std::set to get unique values in one go. With generic merge, duplicate values are not filtered, but the result is sorted, so you could apply std::unique to the result. If you expect a lot of duplicates, you might be quicker using a std::set

Upvotes: 4

Related Questions