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

如何将这两个 vector FAST 合并到其中一个 vector 中(例如 v_one = v_one + v_two)并按 id 排序。

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

谢谢!

Answer 1

如果你想将它们合并到两个 vector 之一，我建议 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这是 Parallelism Extension 的 Microsoft 原型(prototype)。

---

编辑:

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