连接两个大 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”排序。

如何执行 FAST 将这两个向量合并到其中一个（例如 v_one = v_one + v_two）并按 [=15= 排序].

我认为我必须将其作为一个动作（排序和合并）来执行，而不是一个接一个地执行？

谢谢！

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 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 这是 Parallelism Extension 的 Microsoft 原型。

编辑：

删除重复项可以通过使用 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());

连接两个大 QVector 并对它们进行排序的最快方法 (C++/Qt)

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

c++

sorting

qt

concatenation

qvector