STL传递比较函数进容器的三种方式-白红宇

STL传递比较函数进容器的三种方式

阅读量：4350 次

发布时间：2019-06-07

本文共 3700 字，大约阅读时间需要 12 分钟。

对于STL中的依靠比较排序的容器，均提供了一个模板参数来传递比较函数，默认的为std::less<>。

查阅可以看到典型的使用比较函数的容器有

template 
     
      ,  class Compare = less
      
        > class priority_queue;template < class T,                        // set::key_type/value_type           class Compare = less
       
        ,        // set::key_compare/value_compare           class Alloc = allocator
        
               // set::allocator_type           > class set;template < class Key,                                     // map::key_type           class T,                                       // map::mapped_type           class Compare = less
         
          ,                     // map::key_compare           class Alloc = allocator
          
           
             > // 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

, bool(*)(const int&, const int&)> q(greaterInt);

典型C风格写法，有种调用C库的qsort的感觉，代码有点长，虽然可以在前面加一句typedef bool(*Compare)(const int&, const int&)来缩短单行代码，但代码总共还是很长

2、函数对象

template 
     
      struct Greater{    bool operator()(const T& lhs, const T& rhs) const    {        return lhs > rhs;    }};priority_queue

, Greater

> q;

注意，这里的q是采取默认构造。回顾之前的构造函数，字段comp在默认构造函数是直接用默认构造的，所以这里可以不写参数，而对于函数指针则不同，函数指针不是类，没有构造函数，所以必须添上参数。

那么，如果采用显式写法呢？

priority_queue

, Greater

> q(Greater

());

编译器会提出警告

warning C4930: 'std::priority_queue
     
      
       <_Ty>>,Greater
       
        > q(Greater
        
          (__cdecl *)(void))':                 prototyped function not called (was a variable definition intended?)1>          with1>          [1>              _Ty=int1>          ]

这句代码不再是定义一个优先队列，而是声明一个函数指针，类似下面这种

Type q(Greater
     
      ());

函数重载是个语法糖，重载括号操作符的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

, decltype(comp)> q(comp);

由于lambda表达式类型要无法手写出来，所以C++ 11提供了decltype关键字来取得类型。至于decltype的用法，本文不多做说明，网上资料很多。

比较

使用函数指针是最快的，因为无需构造对象或者lambda表达式，但是通用性不强，函数对象使用模板类只需改变模板参数就能适应不同类型，对特殊类型还可以做模板特化。而lambda表达式写起来比函数对象更为方便，适用于无需重复利用的比较函数。不过像==、!=、<、>、<=、>=等比较运算的函数对象都已经有现成的（见中的equal_to、not_equal_to、less、greater、less_equal、greater_equal），似乎lambda表达式一般用不着？

啊，说到这里，要绑定这三种不同的比较函数形式，用通用的function模板即可

typedef std::function
     
       Compare;    typedef std::priority_queue

, Compare> MyPriorQueue; // 1. 函数指针 MyPriorQueue q1(greaterInt); // 2. 函数对象 Greater

compFunctor; MyPriorQueue q2(compFunctor); // 3. lambda表达式 auto compLambda = [](const int& lhs, const int& rhs) { return lhs > rhs; }; MyPriorQueue q3(compLambda); vector

> 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; }