Самый быстрый способ объединить два больших QVector и отсортировать их (C++/Qt)

Question

Какой лучший (самый быстрый) способ объединить два больших уже отсортированных QVector в одном большом отсортированном QVector?

У меня есть следующий код:

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

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

У меня есть v_one и v_two уже отсортированные по "id".

Как выполнить БЫСТРО слияние этих двух векторов в одной из них (например, v_one = v_one + v_two) с сортировкой по id.

Я думаю, что я должен делать это как одно действие (сортировка и слияние), а не один за другим?

Спасибо!

Answer 1

Если вы хотите, чтобы объединить их в одном из двух векторов, я предложил бы 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; }); 

Для параллельного выполнения: Экспериментальная C++ Extensions for Parallelism, ISO/IEC TS 19570:2015 имеет std::experimental::parallel::inplace_merge, который, вероятно, будет частью стандарта некоторое время в будущее. Вы можете найти implementation for the parallel merge algorithms в CodePlex Parallel STL project, который является прототипом Microsoft расширения параллелизма.

---

Edit:

Удаление дубликатов может быть достигнуто с помощью 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());