【C++】STL学习——priority_queue（了解仿函数）

priority_queue介绍

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元
   素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭
   代器访问，并支持以下操作：

• empty()：检测容器是否为空
• size()：返回容器中有效元素个数
• front()：返回容器中第一个元素的引用
• push_back()：在容器尾部插入元素
• pop_back()：删除容器尾部元素

5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指
   定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构，但本身作为容器适配器无法遍历。

所谓优先级队列priority_queue，实际上就是我们学过的数据结构——堆，关于堆的特性及功能可参考——堆的模拟实现一文；而priority_queue跟上文介绍的stack和queue一样，都是容器适配器，都是由其他容器封装而来，但是对底层容器提出了更进一步的要求——底层容器需要支持随机访问迭代器。

迭代器种类

1. 输入迭代器 Input Iterators：

• 提供了对容器中元素的单向访问能力。
• 支持的操作包括：++（前进）、*（解引用以访问元素）、== 和 !=（比较迭代器是否相等或不等）。
• 输入迭代器只能向前移动，不能反向移动，也不能直接通过迭代器来修改元素的值（尽管可以通过解引用访问到的元素间接修改，但这通常不是迭代器的职责）。
• 典型示例：istream_iterator（用于从输入流中读取数据）。

2. 输出迭代器 Output Iterators：

• 提供了向容器中写入元素的能力。
• 支持的操作包括：++（前进）、*（解引用以写入元素）。
• 输出迭代器同样只能向前移动，且不能读取元素的值，主要用于输出操作。
• 典型示例：ostream_iterator（用于向输出流中写入数据）。

3. 前向迭代器 Forward Iterators：

• 是输入迭代器的超集，支持所有输入迭代器的操作，并且保证多次通过同一迭代器解引用得到的元素值相同（即迭代器稳定）。
• 仍然只能向前移动，但比输入迭代器更加灵活，如可以用于accumulate等算法中。
• 典型示例：forward_list（单向链表）的迭代器。

4. 双向迭代器 Bidirectional Iterators：

• 支持前向迭代器的所有操作，并增加了- -（后退）操作，允许迭代器在容器中前后移动。
• 典型示例：list和map（注意，map的迭代器是双向的，但只能遍历键值对，不能直接修改键）的迭代器。

5. 随机访问迭代器 Random Access Iterators：

• 提供了最强大的迭代器能力，支持双向迭代器的所有操作，并且增加了元素间的算术操作，如+n、-n、+=n、-=、<、<=、>、>=。
• 这类迭代器可以像指针一样，进行随机访问和快速遍历。
• 典型示例：vector、deque、string 的迭代器。

由于priority_queue需要随机访问迭代器，所以一般使用vector，或deque作为底层容器。

priority_queue实现

老样子，封在自己的命名空间里；由于priority_queue是容器适配器，底层也是使用了别的容器（vector或deque）所以实现方法和上篇的stack和queue是一样的，具体请参考stack和queue，而的区别就是priority_queue是堆，需要借助adjust_up和adjust_down维持堆的特性。而这两个调整方法也曾在堆模拟实现一文详细介绍过。需要请参考——堆的模拟实现。

我们这里真正需要关心的是：堆有大小堆之分，如何使用同一份代码解决这个问题呢？总不能手动去改代码中的比较逻辑吧。这里的解决办法就是本文将要介绍的——仿函数。

namespace djs
{///仿函数template<class T>struct Less{bool operator()(const T& x, const T& y){return x < y;}};template<class T>struct Greater{bool operator()(const T& x, const T& y){return x > y;}};template<class T,class Container=vector<T>,class Compare=Less<T>>class priority_queue{public:void push(const T& x){assert(!empty());_con.push_back(x);//adjust_up(_con.size() - 1);//自己实现的push_heap(_con.begin(), _con.end());//使用库实现好的}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();//adjust_down(0);pop_heap(_con.begin(),_con.end());//使用库实现好的}bool empty(){return _con.empty();}T& top(){return _con[0];}private:void adjust_up(int child){int parent = (child - 1) / 2;Compare com;while (child > 0){//if (_con[parent] < _con[child])//大小比较if (com(_con[parent], _con[child]))//使用仿函数{swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(int parent){int child = parent * 2 + 1;Compare com;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])//大小比较if (child + 1 < _con.size() && (com(_con[child], _con[child + 1])))//使用仿函数{child++;}//if (_con[child]>_con[parent])if ((com(_con[parent], _con[child]))){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}private:Container _con;};}

仿函数

仿函数（Functor）是C++中的一个概念，它指的是那些可以被当作函数一样调用的对象。在C++中，这通常是通过重载operator()来实现的。仿函数不仅具有函数的特性（即可以被调用），而且它们还可以拥有状态（即数据成员），这使得它们比普通的函数更加灵活和强大。

堆有分大堆还是小堆，priority_queue通过仿函数解决大小堆的问题；我们看看priority_queue的结构。

可以看到第三个参数Compare，它就是所说的仿函数，可以通过传入参数的不同来创建的是大堆还是小堆。

• 类模板Compare的参数默为less，与之对应的还有greater，使用请包含头文件<functional>。
• less为大堆，greater为小堆；记忆时可以从父节点开始理解，比父节点小的为less，反之。

仿函数的使用

1. 定义仿函数：首先，你需要定义一个类，并在该类中重载operator()。这个操作符的返回类型和参数列表决定了仿函数使用对象和作用。
2. 使用仿函数：然后，你可以创建该类的对象，并像调用函数一样调用它（通过()操作符），函数对象是定义了成员函数operator()的类的实例。该成员函数允许以与函数调用相同的语法使用对象。
3. 仿函数有点类似C语言学习过的回调函数，作为参数参入，等到使用时再调用。

回调函数

回调函数就是⼀个通过函数指针调⽤的函数。如果你把函数的指针（地址）作为参数传递给另⼀个函数，当这个指针被⽤来调⽤其所指向的函数时，被调⽤的函数就是回调函数。回调函数不是由该函数的实现⽅直接调⽤，⽽是在特定的事件或条件发⽣时由另外的⼀⽅调⽤的，⽤于对该事件或条件进⾏响应。

库中的qsort就用到了回调函数。

Compare作为类模板，需要传入一个类，该类因包含对应的仿函数如：Less即建大堆，所以类中的仿函数operator()应该按建大堆的逻辑写。Greater为建小堆，operator()实现的逻辑也是如此。

• 仿函数指定为operator()的重载，不能是其它。
• 这里的Less,Greater我们自己模拟写，库里有
• 现成less和greater，使用时记得包含头文件<functional>

    template<class T>struct Less//大堆{bool operator()(const T& x, const T& y){return x < y;}};template<class T>struct Greater//小堆{bool operator()(const T& x, const T& y){return x > y;}};template<class T,class Container=vector<T>,class Compare=Less<T>>class priority_queue{void adjust_down(int parent){int child = parent * 2 + 1;Compare com;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])if (child + 1 < _con.size() && (com(_con[child], _con[child + 1]))){child++;}//if (_con[child]>_con[parent])if ((com(_con[parent], _con[child]))){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}};

从此我们就可以在使用Less还是Greater指明建的是小堆还是大堆了。

  //小堆     priority_queue<int, vector<int>, Greater<int>> pq1;//与sort不同，sort要传对象，priority_queue传类型就可以，会在用的地方创造对象//大堆     	priority_queue<int, vector<int>, Less<int>> pq2;

以adjust_down为例：
先创建一个Compare的对象，等需要进行建堆判断时调用该对象。

			Compare com;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])//直接大小比较if (child + 1 < _con.size() && (com(_con[child], _con[child + 1])))//使用仿函数}

具体过程可以通过调试观察。

作为STL的六大组件之一：仿函数的功能十分强大，如搭配算法库或功能库的一些函数如sort，按自己的需求重载operator()以达到自己的目的。