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
就可以。
原文链接
上一篇: slot插槽
下一篇: 搭建vue的开发环境