如何实现带计数器的谓词函数以统计排序算法的比较次数

你需要实现一个通用的谓词包装函数，将原始比较逻辑和外部计数器绑定，满足题目要求的调用形式且无需修改主函数代码，补全后的完整代码如下：

#include <vector>
#include <iostream>
#include <algorithm>
#include <utility> // 用于std::forward完美转发

template<typename Pred>
auto predicate_with_counter(Pred&& pred, size_t& counter) {
    counter = 0; // 初始化计数器，消除未初始化的脏值问题
    // 返回包装后的lambda可调用对象
    return [pred = std::forward<Pred>(pred), &counter] (auto&&... args) mutable -> decltype(auto) {
        ++counter; // 每次调用先累加比较次数
        // 转发参数调用原始谓词，返回原始结果
        return pred(std::forward<decltype(args)>(args)...);
    };
}

bool predicate1(double a, double b){
   return a > b;
}

int main(){
   using namespace std;
   size_t counter;
   vector<double> v1{2,4,0,-1,5};
   auto p1 = predicate_with_counter(predicate1, counter);
   sort(begin(v1), end(v1), p1);
   cout << "Number of comparisons in sorting of v1 : " << counter << endl;

   return 0;
}

核心实现要点 #

• 采用模板实现支持任意可调用类型的原始谓词，包括函数指针、lambda、自定义函数对象
• 返回的lambda通过值捕获保存原始谓词，通过引用捕获绑定外部计数器，保证每次比较都能修改外部的counter变量
• 调用包装后的谓词时先累加计数，再完美转发参数调用原始谓词，完全保留原始比较逻辑的行为
• 兼容C++14及更高版本标准，通用性强，可适配所有需要统计调用次数的可调用对象场景，不限于排序比较谓词。

内容的提问来源于stack exchange，提问作者mirza.o258