在 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 的性能高度依赖于元素。

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

std::sort 通过比较和交换 random-accessible 范围内的元素（例如 std::vector）来工作，因此也必须满足 ValueSwappable.

换句话说，元素必须有一个名为 swap 的成员函数，或者两者都是 MoveConstructible and MoveAssignable (in order for std::swap to be used). The compiler will automatically generate both move constructor and move assignment operator, unless you explicitly delete them or a member of your struct causes them to be deleted (such as std::mutex)。虽然您可以使用 std::is_move_constructible 和 std::is_move_assignable 来检查，但您通常不需要担心这一点。

SMALL CORRECTION（感谢@FrançoisAndrieux）：对象仍然可以是 MoveConstructible and/or MoveAssignable，只要它具有复制构造函数和复制赋值运算符（不寻常，但可能）。查看他们的评论。

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

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

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

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

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

为了演示，我写了一个快速基准测试。假设你有结构：

struct big_struct_t {
  int val;
  std::vector<std::string> strs;

  bool operator<(const big_struct_t& x) const {
    return val < x.val;
  }
};

struct bigger_struct_t : big_struct_t {
  std::array<std::uint8_t, 1024> kiloByteArray;
};

第一个很容易交换。第二个不是。让我们尝试对 1000 个 big_struct_t 和 bigger_struct_t.

中的 std::vectors 和 std::lists 进行排序

template <typename T>
static T newContainer() {
  int i = 1000;
  T v(i);

  for (auto& struc : v)
  {
    struc.val = i;
    struc.strs.emplace_back(std::to_string(i));
    i--;
  }

  return v;
}

static void SortVectorOfBigStruct(benchmark::State& state) {
  for (auto _ : state) {
    state.PauseTiming();
    auto v = newContainer<std::vector<big_struct_t>>();
    state.ResumeTiming();
    sort(v.begin(), v.end());
    benchmark::DoNotOptimize(v);
  }
}

BENCHMARK(SortVectorOfBigStruct);

static void SortVectorOfBiggerStruct(benchmark::State& state) {
  for (auto _ : state) {
    state.PauseTiming();
    auto v = newContainer<std::vector<bigger_struct_t>>();
    state.ResumeTiming();
    sort(v.begin(), v.end());
    benchmark::DoNotOptimize(v);
  }
}

BENCHMARK(SortVectorOfBiggerStruct);

static void SortListOfBigStruct(benchmark::State& state) {
  for (auto _ : state) {
    state.PauseTiming();
    auto l = newContainer<std::list<big_struct_t>>();
    state.ResumeTiming();
    l.sort();
    benchmark::DoNotOptimize(l);
  }
}

BENCHMARK(SortListOfBigStruct);

static void SortListOfBiggerStruct(benchmark::State& state) {
  for (auto _ : state) {
    state.PauseTiming();
    auto l = newContainer<std::list<bigger_struct_t>>();
    state.ResumeTiming();
    l.sort();
    benchmark::DoNotOptimize(l);
  }
}

BENCHMARK(SortListOfBiggerStruct);

Benchmark on quick-bench.com.

如您所见，由于 std::array.

，排序 std::vector<bigger_struct_t> 比 std::vector<big_struct_t> 慢 49 倍

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

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

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

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

In C++, sorting a vector of big struct would be slow?

c++

vector