【C++练级之路】【Lv.10】【STL】priority

快乐���流畅：个人主页 个人专栏：《C语言》《数据结构世界》《进击的C++》 远方有一堆篝火，在为久候之人燃烧！

---

文章目录

• 一、仿函数
• • 1.1 仿函数的介绍
  • 1.2 仿函数的优势
  • 二、priority_queue
  • • 2.1 push
    • 2.2 pop
    • 2.3 top
    • 2.4 size
    • 2.5 empty
    • 三、反向迭代器
    • • 3.1 成员变量与默认成员函数
      • 3.2 operator*
      • 3.3 operator->
      • 3.4 operator++
      • 3.5 operator- -
      • 3.6 relational operators
      • 四、反向迭代器的适用
      • 4.1 vector
      • • 4.1.1 rbegin
        • 4.1.2 rend
        • 4.2 list
        • • 4.2.1 rbegin
          • 4.2.2 rend
          • 总结

            一、仿函数

            1.1 仿函数的介绍

            仿函数，是一种特殊类型的类，它重载了（）运算符，使得这个类的使用看起来像一个函数，因此它又称为函数对象。

            具体来说，仿函数就是将函数的特性赋予到类上，使得这个类有了类似函数的行为。

            1.2 仿函数的优势

            C++设计仿函数之初，其实就是想替代庞杂难懂的函数指针，将函数指针替换为简单易懂的仿函数。

            这里列举两个常用的仿函数——less和greater

            templatestruct less{bool operator()(const T& x, const T& y){return x  y;}};

            二、priority_queue

            细节：

            1. priority_queue也是容器适配器，默认容器使用vector
            2. 其底层数据结构是堆，并且默认情况为大堆

               如果不了解堆，可以先看往期【数据结构】【版本2.0】【树形深渊】——二叉树入侵

            3. 为了能方便调整大小堆，增加了仿函数的模板

            templateclass priority_queue{public:private:Container _con;};

            悄悄说一句：其实容器模板和仿函数模板位置互换，才更加合理！（平时不怎么会换默认容器，但是会经常换仿函数来控制大小堆）

            2.1 push

            入堆

            细节：

            1. 先尾插元素
            2. 再使用向上调整算法

            void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}

            向上调整算法

            细节：

            • 构造一个仿函数模板对象，再利用重载的（）运算符进行比较（当然，也可以使用匿名对象）

              void adjust_up(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}

              2.2 pop

              出堆

              细节：

              1. 先首尾元素互换
              2. 再尾删元素
              3. 最后使用向下调整算法

              void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}

              向下调整算法

              细节：

              • 构造一个仿函数模板对象，再利用重载的（）运算符进行比较（当然，也可以使用匿名对象）

                void adjust_down(int parent){Compare com;int child = parent * 2 + 1;while (child  
                2.3 top
                 
                获取堆顶元素
                 
                const T& top() const{return _con[0];}
                 
                2.4 size
                 
                获取堆中有效元素个数
                 
                size_t size() const{return _con.size();}
                 
                2.5 empty
                 
                判断堆是否为空
                 
                bool empty() const{return _con.empty();}
                 
                三、反向迭代器
                 
                其实，反向迭代器也是一种适配器，它是根据不同容器的正向迭代器，来生成对应的反向迭代器。
                 
                同时，反向迭代器追求一种对称美，rbegin()在end()，rend()在begin()。
                 
                3.1 成员变量与默认成员函数
                 
                细节：
                 
                仍然使用struct，标明公有属性
                成员变量是一个正向迭代器
                提供带参构造函数（其余的默认成员函数不用显式定义，浅拷贝即可）
                templatestruct __reverse_iterator{typedef __reverse_iterator self;Iterator _cur;__reverse_iterator(Iterator it): _cur(it){}};
                 
                3.2 operator*
                 
                细节：
                 
                迭代器先自减，再解引用返回
                返回引用，为了区别普通迭代器和const迭代器
                Ref operator*(){Iterator tmp = _cur;return *--tmp;}
                 
                3.3 operator->
                 
                细节：
                 
                直接调用operator*()，根据不同容器的数据取地址返回
                返回指针，为了区别普通迭代器和const迭代器
                Ptr operator->(){return &(operator*());}
                 
                3.4 operator++
                 
                细节：
                 
                反向迭代器的++，就是正向迭代器的- -
                为了区分前置和后置，后置参数加上int（无实际意义，以示区分）
                前置传引用返回，后置传值返回
                self& operator++(){--_cur;return *this;}self operator++(int){Iterator tmp = _cur;--_cur;return tmp;}
                 
                3.5 operator- -
                 
                细节：同上
                 
                self& operator--(){++_cur;return *this;}self operator--(int){Iterator tmp = _cur;++_cur;return tmp;}
                 
                3.6 relational operators
                 
                bool operator!=(const self& s){return _cur != s._cur;}bool operator==(const self& s){return _cur == s._cur;}
                 
                四、反向迭代器的适用
                 
                4.1 vector
                 
                templateclass vector{public:typedef T* iterator;typedef const T* const_iterator;typedef __reverse_iterator reverse_iterator;typedef __reverse_iterator const_reverse_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//...}
                 
                4.1.1 rbegin
                 
                reverse_iterator rbegin(){return reverse_iterator(end());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}
                 
                4.1.2 rend
                 
                reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}
                 
                4.2 list
                 
                templateclass list{public:typedef __list_node node;typedef __list_iterator iterator;typedef __list_iterator const_iterator;typedef __reverse_iterator reverse_iterator;typedef __reverse_iterator const_reverse_iterator;iterator begin(){return iterator(_head->_next);}const_iterator begin() const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end() const{return const_iterator(_head);}//...}
                 
                4.2.1 rbegin
                 
                reverse_iterator rbegin(){return reverse_iterator(end());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}
                 
                4.2.2 rend
                 
                reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}
                 
                总结
                 
                这次学习了仿函数的概念和基本用法，对于升降序、大小堆等转换具有极大便利。同时实现了新的容器适配器——priority_queue（优先级队列），实际上就是堆。并且也完美实现了同为适配器的反向迭代器，至此，对于适配器有了更深一步的了解和运用。
                     真诚点赞，手有余香