在std :: sort()中完成的比较次数

Question

当使用n个整数对向量进行排序时,如何计算标准C++ STL排序函数中发生的比较次数？

Answer 1

一种快速,非侵入性的方法是使用lambda函数.如果您使用的是C++ 11或更高版本,则可以使用lambda,如下所示:

unsigned int numComparisons = 0U;
std::vector<unsigned int> someContainer;
// Fill container, etc.
std::sort( 
    std::begin(someContainer), 
    std::end(someContainer),
    [&numComparisons]( unsigned int lhs, unsigned int rhs ) 
    {
        ++numComparisons;
        return lhs < rhs;
    }
);

std::cout << numComparisons << " comparisons were performed in std::sort" << std::endl;