优先使用函数对象自定义STL算法规则

作为一门面向对象的编程语言，使用 C++ 编写程序有一个缺点，即随着代码面向对象程度的提高，其执行效率反而会降低。例如，经实验证明几乎在所有情况下，直接操作一个 double 类型变量的执行效率，要比操作一个含 double 类型成员属性的类对象更高。

对于大多数读者来说，以上所说是很容易想通的，因为它符合我们对高级编程语言的认知。但本节要介绍的内容，一定程序上会打破这个认知。

前面章节中，我们学习了 STL 标准库中所有的排序算法，比如 sort()、stable_sort() 以及 nth_element() 等。不知读者有没有发现，这些排序算法都单独提供了带有 comp 参数的语法格式，借助此参数，我们可以自定义排序规则。

以 sort() 排序函数为例，其语法格式有以下 2 种：

//无 comp 参数
void sort (RandomAccessIterator first, RandomAccessIterator last);
//有 comp 参数
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

显然仅从使用语法上看，它们唯一的区别在于，第 2 种多了一个 comp 参数。

事实上，对于 STL 标准库中的每个算法，只要用户需要自定义规则，该算法都会提供有带 comp 参数的语法格式。

本质上讲，comp 参数用于接收用户自定义的函数，其定义的方式有 2 种，既可以是普通函数，也可以是函数对象。例如：

#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector
//以普通函数的方式实现自定义排序规则
inline bool mycomp(int i, int j) {
    return (i < j);
}
//以函数对象的方式实现自定义排序规则
class mycomp2 {
public:
    bool operator() (int i, int j) {
        return (i < j);
    }
};

int main() {
    std::vector<int> myvector{ 32, 71, 12, 45, 26, 80, 53, 33 };
    //调用普通函数定义的排序规则
    std::sort(myvector.begin(), myvector.end(), mycomp);
    //调用函数对象定义的排序规则
    //std::sort(myvector.begin(), myvector.end(), mycomp2());
   
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it) {
        std::cout << *it << ' ';
    }
    return 0;
}

程序执行结果为：

12 26 32 33 45 53 71 80

注意，为了提高执行效率，其函数都定义为内联函数（在类内部定义的函数本身就是内联函数）。至于为什么内联函数比普通函数的执行效率高，可阅读《C++ inline内联函数》一文。

要知道，函数对象可以理解为伪装成函数的对象，根据以往的认知，函数对象的执行效率应该不如普通函数。但事实恰恰相反，即便如上面程序那样，将普通函数定义为更高效的内联函数，其执行效率也无法和函数对象相比。

通过在 4 个不同的 STL 平台上，对包含 100 万个 double 类型数据的 vector 容器进行排序，最差情况下使用函数对象的执行效率要比普通内联函数高 50%，最好情况下则高 160%。

那么，是什么原因导致了它们执行效率上的差异呢？以 mycomp2() 函数对象为例，其 mycomp2::operator() 也是一个内联函数，编译器在对 sort() 函数进行实例化时会将该函数直接展开，这也就意味着，展开后的 sort() 函数内部不包含任何函数调用。

而如果使用 mycomp 作为参数来调用 sort() 函数，情形则大不相同。要知道，C++ 并不能真正地将一个函数作为参数传递给另一个函数，换句话说，如果我们试图将一个函数作为参数进行传递，编译器会隐式地将它转换成一个指向该函数的指针，并将该指针传递过去。

也就是说，上面程序中的如下代码：

std::sort(myvector.begin(), myvector.end(), mycomp);

并不是真正地将 mycomp 传递给 sort() 函数，它传递的仅是一个指向 mycomp() 函数的指针。当 sort() 函数被实例化时，编译器生成的函数声明如下所示：

std::sort(vector<int>::iterator first,
          vector<int>::iterator last,
          bool (*comp)(int, int));

可以看到，参数 comp 只是一个指向函数的指针，所以 sort() 函数内部每次调用 comp 时，编译器都会通过指针产生一个间接的函数调用。

也正是基于这个原因，C++ sort() 函数要比 C 语言 qsort() 函数的执行效率更高。读者可能会问，程序中 comp() 函数也是内联函数，为什么 C++ 不像函数对象那样去处理呢？具体原因我们无从得知，事实上也没必要关心，也许是编译器开发者觉得这种优化不值得去做。

除了效率上的优势之外，相比普通函数，以函数对象的方式自定义规则还有很多隐藏的优势。例如在某些特殊情况下，以普通函数的形式编写的代码看似非常合理，但就是无法通过编译，这也许是由于 STL 标准库的原因，也许是编译器缺陷所至，甚至两者都有可能。而使用函数对象的方式，则可以有效避开这些“坑”，而且还大大提升的代码的执行效率。

总之，以函数对象的方式为 STL 算法自定义规则，具有效率在内的诸多优势。当调用带有 comp 参数的 STL 算法时，除非调用 STL 标准库自带的比较函数，否则应优先以函数对象的方式自定义规则。