首页 > 代码库 > STL传递比较函数进容器的三种方式
STL传递比较函数进容器的三种方式
对于STL中的依靠比较排序的容器，均提供了一个模板参数来传递比较函数，默认的为std::less<>。
查阅Containers - C++ Reference可以看到典型的使用比较函数的容器有
template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue; template < class T, // set::key_type/value_type class Compare = less<T>, // set::key_compare/value_compare class Alloc = allocator<T> // set::allocator_type > class set; template < class Key, // map::key_type class T, // map::mapped_type class Compare = less<Key>, // map::key_compare class Alloc = allocator<pair<const Key,T> > // map::allocator_type > class map;
分别是优先队列、集合、映射，当然multiset和multimap也一样。
这里以优先队列为例，分别给出三种传递方式，将比较函数从默认的less<>（升序）改成降序。
这里先看看优先队列的构造函数源码
protected: _Container c; // the underlying container _Pr comp; // the comparator functor
priority_queue(const _Myt& _Right) : c(_Right.c), comp(_Right.comp) { // construct by copying _Right } explicit priority_queue(const _Pr& _Pred) : c(), comp(_Pred) { // construct with empty container, specified comparator }
1、函数指针
bool greaterInt(const int& lhs, const int& rhs) { return lhs > rhs; } priority_queue<int, vector<int>, bool(*)(const int&, const int&)> q(greaterInt);
典型C风格写法，有种调用C库的qsort的感觉，代码有点长，虽然可以在前面加一句typedef bool(*Compare)(const int&, const int&)来缩短单行代码，但代码总共还是很长
2、函数对象
template <typename T> struct Greater { bool operator()(const T& lhs, const T& rhs) const { return lhs > rhs; } }; priority_queue<int, vector<int>, Greater<int>> q;
注意，这里的q是采取默认构造。回顾之前的构造函数，字段comp在默认构造函数是直接用默认构造的，所以这里可以不写参数，而对于函数指针则不同，函数指针不是类，没有构造函数，所以必须添上参数。
那么，如果采用显式写法呢？
priority_queue<int, vector<int>, Greater<int>> q(Greater<int>());
编译器会提出警告
warning C4930: ‘std::priority_queue<int,std::vector<int,std::allocator<_Ty>>,Greater<int>> q(Greater<int> (__cdecl *)(void))‘:
prototyped function not called (was a variable definition intended?) 1> with 1> [ 1> _Ty=int 1> ]
这句代码不再是定义一个优先队列，而是声明一个函数指针，类似下面这种
Type q(Greater<int>());
函数重载是个语法糖，重载括号操作符的Greater<int>()(const int&, const int&)就像定义某个函数Greater_Int_XXX(const int&, const int&)，Greater<int>()自然就对应了Greater_Int_XXX。
如果继续测试下去（比如q.push(1);）可以发现编译无法通过，提示left of ‘.push‘ must have class/struct/union，证明了q在这里不是容器对象，而被当成了函数指针。
所以没必要画蛇添足，直接用默认构造就行了。
3、lambda表达式
auto comp = [](const int& lhs, const int& rhs) { return lhs > rhs; }; priority_queue<int, vector<int>, decltype(comp)> q(comp);
由于lambda表达式类型要无法手写出来，所以C++ 11提供了decltype关键字来取得类型。至于decltype的用法，本文不多做说明，网上资料很多。
比较
使用函数指针是最快的，因为无需构造对象或者lambda表达式，但是通用性不强，函数对象使用模板类只需改变模板参数就能适应不同类型，对特殊类型还可以做模板特化。而lambda表达式写起来比函数对象更为方便，适用于无需重复利用的比较函数。不过像==、!=、<、>、<=、>=等比较运算的函数对象都已经有现成的（见<functional> - C++ reference中的equal_to、not_equal_to、less、greater、less_equal、greater_equal），似乎lambda表达式一般用不着？
啊，说到这里，要绑定这三种不同的比较函数形式，用通用的function模板即可
typedef std::function<bool(const int& lhs, const int& rhs)> Compare;
typedef std::priority_queue<int, std::vector<int>, Compare> MyPriorQueue;
// 1. 函数指针
MyPriorQueue q1(greaterInt);
// 2. 函数对象
Greater<int> compFunctor;
MyPriorQueue q2(compFunctor);
// 3. lambda表达式
auto compLambda = [](const int& lhs, const int& rhs) { return lhs > rhs; };
MyPriorQueue q3(compLambda);
vector<pair<string, MyPriorQueue>> my_prior_queues = {
make_pair("函数指针", q1),
make_pair("函数对象", q2),
make_pair("lambda表达式", q3)
};
for (auto item : my_prior_queues)
{
auto& method = item.first;
cout << method << "\t";
auto& q = item.second;
q.push(1);
q.push(3);
q.push(2);
q.push(4);
q.push(0);
while (!q.empty())
{
cout << q.top() << " ";
q.pop();
}
cout << endl;
}
STL传递比较函数进容器的三种方式