个人主页~

---

一、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;
};

对正向迭代器进行封装就可以得到反向迭代器，先有正向再有反向

---

今日分享就到这里了~