个人主页~

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的使用

<code>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的模拟实现

<code>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，默认状态下为大堆

<code>#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个最大元素

<code>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反向迭代器

<code>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;

};

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

今日分享就到这里了~