Fastest way to concatenate two large QVector's and sort them (C++/Qt)

Question

What is the best (fastest) way to concatenate two large already sorted QVector's in one large sorted QVector?

I have the following code:

class Square
{
    .....
    qint32 id; //public
    .....
}

QVector <Square> v_one; //size 10000+
QVector <Square> v_two; //size 10000+

I have v_one and v_two already sorted by "id".

How do I perform a FAST merge of these two vectors into one of them (e.g. v_one = v_one + v_two) with sorting by id.

I think I have to do this as one action (sorting and merging), not one after another?

Thank you!

Answer 1

If you want to merge them in one of the two vectors, I'd suggest std::inplace_merge:

auto size_one = v_one.size();
v_one += v_two;
std::inplace_merge(v_one.begin(), v_one.begin() + size_one, v_one.end(), 
  [](Square const &a, Square const &b) -> bool
  { return a.id < b.id; });

For parallel execution: The experimental C++ Extensions for Parallelism, ISO/IEC TS 19570:2015 has std::experimental::parallel::inplace_merge which will probably be part of the standard some time in the future. You can find an implementation for the parallel merge algorithms in the CodePlex Parallel STL project which is the Microsoft prototype of the Parallelism Extension.

---

Edit:

Removing duplicates can be achieved by using std::unique.

auto new_end = std::unique(v_one.begin(), v_one.end(), 
  [](Square const &a, Square const &b) -> bool
  { return a.id == b.id; });
v_one.erase(new_end, v_one.end());