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

Question

当对包含 n 个整数的 vector 进行排序时，如何计算标准 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;