欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-31 17:32:21
...

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++ 自定义比较:仿函数、函数与重载操作符

            相关标签: 奇技淫巧