为什么 std::sort 构造对象？

Question

我创建了以下 class 来理解 std::sort 的行为：

class X {
public:
  X(int i) : i_(i) { }
  X(X&& rhs) noexcept : i_(std::move(rhs.i_)) { mc_++; }
  X& operator=(X&& rhs) noexcept {
    i_ = std::move(rhs.i_); ao_++; return *this;
  }
  void swap(X& rhs) noexcept { std::swap(i_, rhs.i_); sw_++; } 
  friend bool operator<(const X& lhs, const X& rhs) {
    return lhs.i_ < rhs.i_;
  }
  static void reset() { mc_ = ao_ = sw_ = 0; }
private:
  int i_;
  static size_t mc_, ao_, sw_; // function-call counters
};
// void swap(X& lhs, X& rhs) { lhs.swap(rhs); }

和运行以下基准代码：

int main() {
  std::vector<X> v;
  for (int i = 0; i < 1000000; i++) v.emplace_back(i);

  std::mt19937 g(0xa41bc9); // fixed seed to compare measurements
  std::shuffle(v.begin(), v.end(), g);

  X::reset();
  std::sort(std::begin(v), std::end(v));
}

在线 IDE 中的完整代码在这里：https://wandbox.org/permlink/nbwRKptakgCSHK4f。

测得的特定函数的调用次数如下（全部带有-O2或/O2标志）：

   function:   move ctor    operator=        swap
  GCC 7.1.0:   5,007,335   11,700,048           0
clang 4.0.0:   4,932,061    9,973,899           0
 MSVC 19.11:   8,580,356   21,521,211           0

如果我取消注释 swap 函数，情况会好转：

   function:   move ctor    operator=        swap
  GCC 7.1.0:     999,999    3,685,376   4,007,336
clang 4.0.0:      72,554      254,885   4,859,507
 MSVC 19.11:     906,593    6,173,685   7,673,763

但是，移动构造函数（加析构函数）和移动赋值运算符的调用仍然很多。困扰我的是效率。例如，编译器可以内联 swap 和 operator= 的调用， ~~但我猜编译器可能不会 "inline" （优化掉） construction/destruction对象~~.

为什么 construction/assignment of objects 用于排序？ 就地排序（通常 std::sort 做）可以纯粹通过比较和交换来实现操作。

更新

我的假设是错误的。优化对象 creation/destruction 似乎完全合法，例如 in:

X temp = std::move(x1); x1 = std::move(x2); x2 = std::move(temp);

因此，这样的代码可以像自定义代码一样高效swap。在线示例：https://godbolt.org/g/ud4u9U - 没有移动构造函数/赋值运算符的调用，尽管这些都不是微不足道的，并且它们的功能内联到 main.

Answer 1

std::sort() 是一种混合算法。虽然 vanilla quicksort 可以仅使用 swap() 操作（来自 std::partition()），但真正的排序方法很可能也使用插入、堆、and/or 合并排序。对于这些排序算法，将对象移开（通过移动构造）、将对象移动到当前 "hole" 并最终将不合适的对象移开通常更有效。只保留一个临时对象可能是合理的，但很可能该算法使用了一些函数并且保留临时对象有点不切实际（尽管我之前没有考虑过并且可能值得尝试).

今年早些时候我的Quicker Sorting talk got recorded at the Italian C++ Conference：它详细介绍了快速排序的细节。

结果是：如果你想对对象进行排序，你最好确保 copy/move 构造、copy/move 赋值、析构和 swap() 是快速的。我可以想象保留一个临时对象可以减少构造和销毁的需要，但任务将保留。专门的 破坏性 移动也可能会提高性能，但我还没有试验过（还）。

为什么 std::sort 构造对象？

Why std::sort construct objects?

c++

sorting

swap

move-constructor

move-assignment-operator