<分区>
我创建了以下类来理解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=
的调用可以被编译器内联,但我猜编译器可能不会“内联”(优化掉)构造/对象的破坏。
为什么要在排序中使用对象的构造/赋值?就地排序(通常是 std::sort
做的)可以完全通过比较和交换操作来实现.
更新
我的假设是错误的。优化对象创建/销毁似乎是完全合法的,例如:
X temp = std::move(x1);
x1 = std::move(x2);
x2 = std::move(temp);
因此,这样的代码可以像自定义 swap
一样高效。在线示例:https://godbolt.org/g/ud4u9U - 没有移动构造函数/赋值运算符的调用,尽管这些都不是微不足道的,并且它们的功能内联到 main
中。