在C++中，对大结构体的向量进行排序会很慢吗？

Question

我认为在对结构向量进行排序时，结构元素会被移动，或者会调用复制构造函数，这会带来一些开销，所以它应该很慢。

例如，

struct big_struct_t {
  // with many data members, just to name a few
  int val;
  vector<string> strs;
  ...
};

int main() {
  vector<big_struct_t> V;
  ... // populate V with 10k elements for example

  sort(V.begin(), V.end(), [](const big_struct_t& lhs, const big_struct_t& rhs) {
    return lhs.val < rhs.val;
  });
}

但在测试了上面的代码之后，似乎在排序过程中根本没有调用复制构造函数。所以我想知道它sort实际上是如何运作的？它根本不需要在向量内移动元素？

Answer 1

正如评论所说，性能std::sort高度依赖于元素。

\n

std::vector连续存储元素。更改元素顺序的唯一方法是通过复制、移动或交换它们来更改它们的值。

\n

std::sort通过比较和交换随机可访问范围（例如 a std::vector）中的元素来工作，因此，该范围也必须满足ValueSwappable。

\n

换句话说，元素必须具有名为 的成员函数swap，或者同时是MoveConstructible和MoveAssignable（以便std::swap使用）。编译器将自动生成移动构造函数和移动赋值运算符，除非您显式删除它们或结构体的成员导致它们被删除（例如std::mutex）。虽然您可以使用std::is_move_constructible和std::is_move_assignable进行检查，但通常不需要担心这一点。

\n

小修正（感谢 @Fran\xc3\xa7oisAndrieux）：只要对象具有复制构造函数和复制赋值运算符（不常见，但可能），它仍然可以是 MoveConstructible 和/或 MoveAssignable。看看他们的评论。

\n

由于std::sort将交换元素，因此交换结构实例的速度越快，算法运行的速度就越快。但是，你怎么知道这有多复杂？

\n

如果您的结构仅包含数字、指针和其他易于交换的成员，则交换应该非常快。这还包括大多数 STL 容器，例如std::vector、std::deque、std::list等，因为它们动态分配其元素并仅存储指向它们的指针。因此，交换它们就像（在内部）交换指向元素的指针一样简单。

\n

因此，只要你big_struct_t只包含可以快速交换的东西，std::swap也应该工作得很快。

\n

但是，您也可能有无法快速交换的成员，例如 C 数组或std::arrays，或者有太多成员。在这种情况下，您最好使用其他类型的容器。

\n

诸如此类的容器std::list能够对元素重新排序，而无需交换其内容，这导致这些容器之一上的排序操作的性能不依赖于元素。

\n

为了进行演示，我编写了一个快速基准测试。假设您有以下结构：

\n

struct big_struct_t {\n  int val;\n  std::vector<std::string> strs;\n\n  bool operator<(const big_struct_t& x) const {\n    return val < x.val;\n  }\n};\n\nstruct bigger_struct_t : big_struct_t {\n  std::array<std::uint8_t, 1024> kiloByteArray;\n};\n

\n

第一个交换起来非常简单。第二个则不然。让我们尝试对 1000和的std::vectors 和std::lists进行排序。big_struct_tbigger_struct_t

\n

template <typename T>\nstatic T newContainer() {\n  int i = 1000;\n  T v(i);\n\n  for (auto& struc : v)\n  {\n    struc.val = i;\n    struc.strs.emplace_back(std::to_string(i));\n    i--;\n  }\n\n  return v;\n}\n\nstatic void SortVectorOfBigStruct(benchmark::State& state) {\n  for (auto _ : state) {\n    state.PauseTiming();\n    auto v = newContainer<std::vector<big_struct_t>>();\n    state.ResumeTiming();\n    sort(v.begin(), v.end());\n    benchmark::DoNotOptimize(v);\n  }\n}\n\nBENCHMARK(SortVectorOfBigStruct);\n\nstatic void SortVectorOfBiggerStruct(benchmark::State& state) {\n  for (auto _ : state) {\n    state.PauseTiming();\n    auto v = newContainer<std::vector<bigger_struct_t>>();\n    state.ResumeTiming();\n    sort(v.begin(), v.end());\n    benchmark::DoNotOptimize(v);\n  }\n}\n\nBENCHMARK(SortVectorOfBiggerStruct);\n\nstatic void SortListOfBigStruct(benchmark::State& state) {\n  for (auto _ : state) {\n    state.PauseTiming();\n    auto l = newContainer<std::list<big_struct_t>>();\n    state.ResumeTiming();\n    l.sort();\n    benchmark::DoNotOptimize(l);\n  }\n}\n\nBENCHMARK(SortListOfBigStruct);\n\nstatic void SortListOfBiggerStruct(benchmark::State& state) {\n  for (auto _ : state) {\n    state.PauseTiming();\n    auto l = newContainer<std::list<bigger_struct_t>>();\n    state.ResumeTiming();\n    l.sort();\n    benchmark::DoNotOptimize(l);\n  }\n}\n\nBENCHMARK(SortListOfBiggerStruct);\n

\n

\n

fast-bench.com 上的基准测试。

\n

正如您所看到的，std::vector<bigger_struct_t>由于.std::vector<big_struct_t>std::array

\n

std::list<bigger_struct_t>对和进行排序std::list<big_struct_t>比 快得多std::vector<bigger_struct_t>，因为它们不必处理std::array.

\n

两者都比 慢得多std::vector<big_struct_t>，因此std::list除非需要，否则请避免使用。

\n

PS：我不确定为什么std::list<bigger_struct_t>比std::list<big_struct_t>. 也许基准有问题？注意：请参阅@Fran\xc3\xa7oisAndrieux\关于可能的罪魁祸首是缓存未命中的评论。

\n