使用std::sort计算交换

Question

是否有一种可移植的、开销最小的方法来计算C++中std::sort期间执行的交换操作的数量？我之所以这么做，是因为我需要计算用于排序列表的排列的符号，我想知道是否有一种方法可以重用std::sort，而不是编写自己的排序函数。

Answer 1

我试图通过制作一个包装器/自定义类型来重载std:：swap。。。然后遇到了一个事实，即对于超小型矢量，交换并不被称为。。。关注评论中的链接因此尝试2为move_constructor添加了一个计数器。

我不能说这是一个开销最小的解决方案，如果你需要确切数量的交换操作，你最好编写自己的排序函数。

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
struct A{
static int swap_count;
static int move_constructor_count;
int a;
A(int _a): a(_a) {}
bool operator<(const A& other) const{
return this->a < other.a;
}
A(const A&other): a(other.a) {move_constructor_count++;}
};
int A::swap_count = 0;
int A::move_constructor_count = 0;
namespace std{
template<>
void swap(A& lhs, A& rhs) {
A::swap_count++;
std::swap(lhs.a, rhs.a);
}
}

int main() {
std::default_random_engine gen;
std::uniform_int_distribution<int> dis(1,100);
std::vector<A> test;
for(int _=0;_<10;_++) test.emplace_back(dis(gen)); //fill a vector randomly
A::move_constructor_count = 0; // emplace calls move constructor
std::sort(test.begin(), test.end());
std::cout << "after sort1: swap count:" << A::swap_count << " move count: " << A::move_constructor_count << std::endl;

// arbitrary way to fill a large test vector
std::vector<A> test2;
for(int _=0;_<1000;_++) test2.emplace_back(dis(gen)); //fill a vector randomly

A::move_constructor_count = 0;
A::swap_count = 0;
std::sort(test2.begin(), test2.end());
std::cout << "after sort2: swap count:" << A::swap_count << " move count: " << A::move_constructor_count << std::endl;
}

给了我

after sort1: swap count:0 move count: 9
after sort2: swap count:1806 move count: 999