CODEWITHSUNDEEP
c++sortingmergestlstdvector
Dominique
Dominique

Reputation: 17493

Are there descendants of std::vector who can merge and sort?

I'm working with std::vectors for a graphical program. Those vectors contain positions on the screen, and they are sorted. Now I'd like to merge them together and keep the actual sorting, while removing possible duplicates, something like this:

vector1 : [2, 6, 10]
vector2 : [1, 5, 6, 10]
result  : [1, 2, 5, 6, 10]

For a good understanding: I have already programmed myself the function to do the actual merging, based on basic std::vector functions, like at(), insert(), size(), but my function seems to be a performance gap (O(n2), I believe).

I'm looking for other std classes (std::vector descendants if possible, for the ease of programming), who contain merge() and sort(kind="unique") as basic methods.

Does anybody know if such classes exist in STL?

Upvotes: 2

Views: 176

Answers (1)

Ap31
Ap31

Reputation: 3314

STL has this concept of separation of containers and algorithms, so while std::vector indeed does not have members to sort or merge it, STL provides all the required algorithms via non-member function templates that handle iterators.

E.g. to sort a vector you would call

std::sort(vector1.begin(),vector1.end());

Check algorithm header for further reference, namely std::sort and std::merge.

To merge and remove duplicates you can use std::set_union, which is probably your best bet. Here is working code example.

Here is a tutorial on iterators, though for this specific task you would only need self-explanatory vector::begin() and vector::end().

For removing duplicates from a single container you would usually use std::unique() or std::unique_copy(), as @unwind mentioned.

There is one caveat with std::unique() and other "removing" algorithms like std::remove(), which stems from that "separation of containers and algorithms" that I mentioned: an algorithm has no means to actually remove elements from the container - it's been given an iterator or a range, but it has no idea about the actual type and implementation of the container.

So instead common approach is to just move the elements intended for removal to the end of the range, and then return the iterator to the first of these elements. Then you can call another function to do actual removal (notice how this time it will be a container method).

This is how it's done with std::unique():

vec.erase(std::unique(vec.begin(), vec.end()), vec.end());

std::unique_copy will not require this trick, but it will pretty much copy the whole vector, so it makes sense only if you intended to copy it anyway.

Upvotes: 4

Related Questions