C++ 自定义比较：仿函数、函数与重载操作符

cpp 模板泛型编程

cpp 比 c 方便不少不光因为其支持面向对象支持class，同样还因为其支持泛型编程，有方便的STL库。泛型要比宏强大的多，是一种设计更巧妙的编译期动态机制，类型安全，使得一些通用算法的封装变得十分方便。模板操作的是类型，特化的时候编译器会做类型推导，这是模板一个核心特征。
根据C++标准，当一个模板不被用到时它就不应该被具体化。对于cpp 编译器是如何特化，编译成最终代码，用到了 惰性求值 和 模式匹配。这篇文章简单介绍了这两个原理：学习Haskell。
对于实际的使用，记住下面两点：

• 函数模板的模板参数是隐式的，编译器根据传入值的类型来推导模板参数的类型，函数模板的参数不能有默认值。
• 类模板的模板参数是显式的，使用一个类模板时必须指明其使用的参数，类模板的模板参数可以有默认值。

这里主要说一下 C++ 标准库，尤其是 STL 涉及比较操作时的常用比较器。这里是STL源代码。

对 sort, stable_sort 传定制比较函数

传入函数编译器来做类型推导，进行模板特化。看sort函数的模板声明：

// 可以看出，排序要求容器支持随机访问迭代器，类似于数组的那种下标偏移访问
// 这里 _Compare 是类型， __comp 是实例，调用 sort 需要传入的就是 __comp 实例
template <class _RandomAccessIter, class _Compare>
inline void sort(_RandomAccessIter __first, _RandomAccessIter __last,
                 _Compare __comp)

一个例子如下：

typedef struct tagNode {
    int index;
    int value;
} Node;

bool comp(const Node &a, const Node &b)
{
    return a.value > b.value;
}

int main()
{
    Node a[5] = { {1, 11}, {3, 33}, {2, 22}, {5, 55}, {4, 44} };
    // 编译器会进行类型推导做模板特化 <class _RandomAccessIter, class _Compare>
    sort(a, a + 5, comp);
    return 0;
}

对 map, set, priority_queue 传入仿函数

仿函数functor的英文解释为something that performs a function，即其行为类似函数的东西。C++中的仿函数是通过在类中重载()运算符实现，使你可以像使用函数一样来创建类的对象。要求传入仿函数的地方也很好理解，一般C++模板，尖括号<>里面放的是类型，自然这需要比较器的时候传入的也是比较器的类型，这就是用到仿函数的地方。
首先，看一下 STL 源码的模板声明：

// map 和 set 底层存储结构式都是红黑树
// Forward declarations of operators == and <, needed for friend declarations.
template <class _Key, class _Tp,
          class _Compare __STL_DEPENDENT_DEFAULT_TMPL(less<_Key>),
          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class map;

template <class _Key, class _Compare __STL_DEPENDENT_DEFAULT_TMPL(less<_Key>),
          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Key) >
class set;

// priority_queue 有优先级，要求元素可比较。queue 和 priority_queue 默认的底层存储结构也不同
// queue 默认用的是 deque 双端队列，priority_queue 用的是 vector
// priority_queue 实现使用的默认比较是 operator< ,是最大堆数据结构，即队列头元素值最大
template <class _Tp,
          class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(deque<_Tp>) >
class queue;

template <class _Tp,
          class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(vector<_Tp>),
          class _Compare
          __STL_DEPENDENT_DEFAULT_TMPL(less<typename _Sequence::value_type>)
class priority_queue;  // 注意点：如果自己传入自己的仿函数比较，那么第二个存储类型也要传入不能缺省

对于 priority_queue 用法，这篇文章里的例子很不错STL里的priority_queue用法。
一个注意点就是：如果使用自定义比较，使用仿函数，那么使用时必然也要传入第二个模板类型参数，要么都缺省，要么都传入。下面给一个例子：

#include <queue>
#include <cstdio>

using namespace std;

typedef struct tagNode
{
    int index;
    int value;
} Node;

/* 针对某种类型的自定义比较仿函数，cpp 中 struct 相当于全部 public 的 class */
struct classcomp
{
    /* const 这里编译没有约束，但是对于明确的不可变参加上更严谨 */
    bool operator() (const Node& a, const Node& b) const
    {
        return a.value > b.value;
    }
};

int main()
{
    Node a[5] = { {1, 11}, {3, 33}, {2, 22}, {5, 55}, {4, 44} };

    // classcomp 必须是针对 Node 类型的比较仿函数，第二个缺省存储结构也不能少
    priority_queue<Node, vector<Node>, classcomp> priQue;

    for(unsigned int i = 0; i < sizeof(a)/sizeof(a[0]); ++i) {
        priQue.push(a[i]);
    }
    while(!priQue.empty()) {
        const Node& topNode = priQue.top();
        // Node topNode = priQue.top() // 也可以结构体直接 = 号赋值，底层相当于 memcpy, Linux 内核就有这么用的
        // const Node *ptopNode = &priQue.top(); // 如果不想拷贝，cpp 推荐用引用, 即上面的写法
        printf("index is %d, value is %d\n", topNode.index, topNode.value);
        priQue.pop();
    }
    return 0;
}

重载 < 运算符

重载<运算符，这种方式通用性会比较强，这种方式使得复杂结构变得像基本数据类型一样可比较了。这样就不用传比较器了，因为默认的比较器这时已经生效了。对于 cpp 代码，重载运算符不管对于 struct 还是 class 都是很方便的，都是在自己定义的结构体或类类型里加一个重载的函数即可。这种方法缺点也是比较明显的，如果有两个模板容器对同一自定义数据结构(结构体或者类)需要不同的比较器，那么重载 < 这种方法就没有上面的自定义比较器(比较函数或者仿函数)适用了。
同样给个例子：

#include <queue>
#include <cstdio>

using namespace std;

// 重载运算符 让cpp代码的表达力有很大提升，比如map重载[]可以翻遍用[]获取指定key的value
// 还有如果定义了一些矩阵运算什么的，重载 * 就更加方便灵活了

struct Node
{
    int index;
    int value;
    /* 注意点：这里的 const 不可少编译约束 */
    bool operator < (const Node& compNode) const
    {
        return this->value < compNode.value;
    }
};


int main()
{
    Node a[5] = { {1, 11}, {3, 33}, {2, 22}, {5, 55}, {4, 44} };

    priority_queue<Node> priQue; //Node 类型重载了 < ,变得像 int 等基本数据类型一样可比较了

    for(unsigned int i = 0; i < sizeof(a)/sizeof(a[0]); ++i) {
        priQue.push(a[i]);
    }
    while(!priQue.empty()) {
        const Node& topNode = priQue.top();
        printf("index is %d, value is %d\n", topNode.index, topNode.value);
        priQue.pop();
    }
    return 0;
}

总结

对于 cpp 中需要自定义比较时，如果以后的操作比较都是定的，可以用重载，否则还是用自定义比较函数和仿函数。还有就是STL 中优先级队列priority_queue, 自定义仿函数是模板的第三个类型，如果自定了那么第二个模板参数也要传入，一般用vector就可以。

原文链接

C++ 自定义比较：仿函数、函数与重载操作符