C++学习之路，从0到精通的征途：priority_queue类的模拟实现

目录

一.priority_queue的介绍

二.仿函数

1.仿函数的介绍

2.仿函数的特点

3.实现两个简单的仿函数

三.priority_queue的接口实现

1.成员变量

2.push

3.pop

4.top

5.size

6.empty

7.构造函数

四.代码总览

priority_queue.h

test.cpp

---

一.priority_queue的介绍

源文档

        在文档中可以看到，对于priority_queue类有三个模板参数，第一个模板参数接收优先队列中的数据类型，第二个模板参数为优先队列的容器适配器，默认为vector，第三个模板参数来接收控制优先级队列为大堆或小堆的仿函数，默认为less，即大堆。

        优先队列其实就可以看作之前学过的数据结构堆。

二.仿函数

1.仿函数的介绍

        仿函数（Functor）也被称作函数对象，它是一种行为类似于函数的对象。要实现仿函数，可通过定义一个类或结构体，并且在其中重载()运算符。如此一来，这个类的对象就能够像函数一样被调用。

2.仿函数的特点

<1>可定制性高：仿函数可依据需求定制其行为，通过重载()运算符实现不同的逻辑。这使得仿函数在算法中能根据具体需求灵活调整行为。

<2>可作为模板参数：在泛式编程里，仿函数可以当作模板参数使用，从而实现通用算法。

3.实现两个简单的仿函数

        以优先队列为例，如果我们想要控制优先队列为大堆或小堆，我们就要实现对应的仿函数：less与greater，优先队列中大堆对应less，小堆对应greater。

template<class T>
class less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};

三.priority_queue的接口实现

1.成员变量

template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
private:Container _con; // 容器适配器Compare com; // 在初始化列表构建仿函数对象
};

2.push

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

        在尾插后进行向下调整算法，由于向下调整与向上调整只在类内部使用，所以定义为私有的成员函数：

void adjustup(size_t child)
{size_t parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

        关于向下调整与向上调整算法的原理，在堆——从理论到代码的深度拆解中有进行讲解，可以前往学习，这里由于通过仿函数进行比较，对于父子结点之间的比较可以通过实例化的仿函数对象进行调用。 

        由于大堆对应less，小堆对应greater，向上和向下调整算法中的比较顺序也要相应调整。

3.pop

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

void adjustdown(size_t parent)
{size_t child = 2 * parent + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}

4.top

const T& top() const
{return _con[0];
}

5.size

size_t size() const
{return _con.size();
}

6.empty

bool empty() const
{return size() == 0;
}

7.构造函数

priority_queue()
{}// 迭代区间构造优先队列
// 遍历，逐个push
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{while (first != last){push(*first);++first;}
}

四.代码总览

priority_queue.h

#include<vector>namespace my_priority_queue
{template<class T>class less{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T>class greater{public: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:priority_queue(){}template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){push(*first);++first;}}void push(const T& x){_con.push_back(x);adjustup(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjustdown(0);}const T& top() const{return _con[0];}size_t size() const{return _con.size();}bool empty() const{return size() == 0;}private:void adjustup(size_t child){size_t parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjustdown(size_t parent){size_t child = 2 * parent + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}private:Container _con;Compare com; // 在初始化列表构建仿函数对象};
}

test.cpp

#include<iostream>
#include<deque>
using namespace std;#include"priority_queue.h"int main()
{my_priority_queue::priority_queue<int, deque<int>, my_priority_queue::greater<int>> pq1;pq1.push(1);pq1.push(0);pq1.push(8);pq1.push(-1);pq1.push(3);pq1.push(6);while (!pq1.empty()){cout << pq1.top() << " ";pq1.pop();}cout << endl;vector<int> v = { 1,0,8,-1,3,6 };my_priority_queue::priority_queue<int, vector<int>, my_priority_queue::less<int>> pq2(v.begin(), v.end());while (!pq2.empty()){cout << pq2.top() << " ";pq2.pop();}return 0;
}