queue和priority_queue
一、queue的介绍和使用
1、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;
}
else
return;
}
}
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);
}
else
return;
}
}
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;
};
对正向迭代器进行封装就可以得到反向迭代器，先有正向再有反向
今日分享就到这里了~
