个人主页~
queue和priority_queue
一、queue的介绍和使用1、queue的介绍2、queue的使用3、queue的模拟实现 二、priority_queue的介绍和使用1、priority_queue的介绍2、priority_queue的使用3、priority_queue的模拟实现 三、仿函数1、仿函数的特征2、仿函数的使用 ex、有关于list反向迭代器
一、queue的介绍和使用
1、queue的介绍
queue详解
队列是一种容器适配器，专门用在先进先出操作中，从容器一端插入元素，另一端提取元素
队列作为容器适配器实现，就是将特定容器封装成其底层容器类，queue提供一组特定的成员函数来访问其元素，元素从队尾入队列，队头出队列
底层容器至少要支持empty判空、size大小、front队头、back队尾、push_back尾插、pop_front头删操作
vector是没有办法满足以上操作的，但deque和list是可以的
2、queue的使用
| 函数声明 | 接口说明 |
|---|---|
| queue | 构造空队列 |
| empty | 检测队列是否为空 |
| size | 返回队列中有效数字个数 |
| front | 返回队头元素的引用 |
| back | 返回队尾元素的引用 |
| push | 在队尾将元素入队 |
| pop | 将队头元素出队列 |
void test_queue(){std::queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);std::cout << q.size() << std::endl;std::cout << q.back() << std::endl;while (!q.empty()){std::cout << q.front() << " ";q.pop();}}
3、queue的模拟实现
namespace little_monster{template<class T,class Container = std::deque<T>>class queue{public:queue() {}void push(const T& x) {_c.push_back(x); }void pop() {_c.pop_front(); }T& back() {return _c.back(); }const T& back()const {return _c.back(); }T& front() {return _c.front(); }const T& front() const {return _c.front(); }size_t size() const {return _c.size(); }bool empty() const {return _c.empty(); }private:Container _c;};}
当然queue的第二个模版参数只能为deque和list，vector是不行的，因为pop_front不是vector的成员
二、priority_queue的介绍和使用
1、priority_queue的介绍
文档介绍
优先队列priority_queue是一种容器适配器，根据严格的弱排序标准，会变为降序队列
类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素
优先队列被实现为容器适配器，提供一组特定的成员函数来访问其元素，元素从特定容器的尾部弹出
底层容器需要支持empty、size、front、push_back、pop_back操作
标准容器vector、deque满足上述要求，但默认一般为vector
需要支持随机访问迭代器，以便始终在内部保持堆结构，容器适配器在需要时自动调整结构
2、priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置都可以考虑使用priority_queue，默认状态下为大堆
| 函数声明 | 接口说明 |
|---|---|
| priority_queue()/priority_queue(first,last) | 构造一个空的优先级队列 |
| empty | 判空 |
| top | 返回堆顶元素 |
| push | 在堆中插入元素 |
| pop | 删除堆顶元素 |
#include <queue>#include <functional>//里边有greater比较方式void TestPriorityQueue(){// 默认情况下，创建的是大堆，其底层按照小于号比较std::vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };std::priority_queue<int> q1;for (auto& e : v)q1.push(e);// 如果要创建小堆，将第三个模板参数换成greater比较方式std::priority_queue<int, std::vector<int>, std::greater<int>> q2(v.begin(), v.end());while(!q1.empty()){std::cout << q1.top() << " ";q1.pop();}std::cout << std::endl;while(!q2.empty()){std::cout << q2.top() << " ";q2.pop();}std::cout << std::endl;}
如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中自己重载符号，就比如说日期类就要重载>、<，按照我们定义的方式进行比较
手感火热做道题
数组中的第K个最大元素
class Solution {public: int findKthLargest(vector<int>& nums, int k) { // 将数组中的元素先放入优先级队列中 priority_queue<int> p(nums.begin(), nums.end()); // 将优先级队列中前k-1个元素删除掉 for (int i = 0; i < k - 1; ++i) { p.pop(); } return p.top(); }};3、priority_queue的模拟实现
优先级队列就是一个封装好的堆
#pragma once#include <vector>namespace little_monster{template <class T>struct less{bool operator()(const T& left, const T& right){return left < right;}};template <class T>struct greater{bool operator()(const T& left, const T& right){return left > right;}};template<class T, class Container = std::vector<T>, class Compare = less<T>>class priority_queue{public:priority_queue():_c(){}template <class Iterator>priority_queue(Iterator first, Iterator last): _c(first, last){int count = _c.size();int root = ((count - 2) >> 1);for (; root >= 0; root--){AdjustDown(root);}}void push(const T& x){_c.push_back(x);AdjustUp(_c.size() - 1);}void pop(){if (empty())return;std::swap(_c.front(), _c.back());_c.pop_back();AdjustDown(0);}size_t size() const{return _c.size();}bool empty() const{return _c.empty();}const T& top() const{return _c.front();}private:void AdjustDown(int parent){size_t child = 2 * parent + 1;while (child < _c.size()){if (child + 1 < _c.size() && Compare()(_c[child], _c[child + 1])){++child;}if (Compare()(_c[parent], _c[child])){std::swap(_c[child], _c[parent]);parent = child;child = parent * 2 + 1;}elsereturn;}}void AdjustUp(int child){size_t parent = ((child - 1) >> 1);while (child){if (Compare()(_c[parent], _c[child])){std::swap(_c[parent], _c[child]);child = parent;parent = ((child - 1) >> 1);}elsereturn;}}private:Container _c;};}
我们自己定义less和greater以控制是大堆还是小堆，封装在一个结构体中，作为priority_queue的第三个模版参数
主要的就是向上调整算法和向下调整算法，与之前C语言学过的一样，稍有改变
三、仿函数
1、仿函数的特征
优先级队列中的less和greater叫做仿函数
重载圆括号运算符：仿函数的核心在于它重载了圆括号"()"运算符，这使得类的实例能够接收参数，并返回一个值
灵活性和状态保存：与普通函数相比，仿函数具有更大的灵活性，因为它可以包含成员变量，这意味着在多次调用仿函数时，它可以保持并更新这些状态信息，从而影响其行为或返回值
2、仿函数的使用
仿函数实际上就是重载括号，使用起来跟函数指针类似，它不仅能够像函数一样被调用，又具有类和对象的特性，像我们之前如果写向上调整算法以及向下调整算法，大堆和小堆是需要到算法中修改代码的，但是有了仿函数就可以直接重载（）然后直接调整是less还是greater就好了
ex、有关于list反向迭代器
template<class Iterator, class Ref, class Ptr>class ReverseIterator{public:typedef ReverseIterator<Iterator, Ref, Ptr> Self;ReverseIterator(Iterator it):_it(it){}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}Ref operator*(){Iterator cur = _it;return *(--cur);}Ptr operator->(){return &(operator*());}bool operator!=(const Self& s){return _it != s._it;}bool operator==(const Self& s){return _it == s._it;}private:Iterator _it;};对正向迭代器进行封装就可以得到反向迭代器，先有正向再有反向
今日分享就到这里了~
