当前位置：首页 > news >正文

STL库——deque/priority_queue

news 2025/9/3 5:52:59

ʕ • ᴥ • ʔ

づ♡ど

🎉 欢迎点赞支持🎉

个人主页：励志不掉头发的内向程序员；

专栏主页：C++语言；

文章目录

前言

一、deque 的简单介绍（了解）

1.1、deque 的原理介绍

1.2、deque 的设计缺陷

二、priority_queue 的介绍和使用

2.1、priority_queue 的介绍

2.2、priority_queue 的使用

2.3、priority_queue 的实现

总结

前言

我们从上一章节学习的 stack/queue 中我们知道了什么是容器适配器，但是我们对于它们的默认容器 deque 还是比较陌生，我们本章节就是来了解这个容器的作用以及完善我们 stack/queue 的内容的，我们一起来看看吧。

一、deque 的简单介绍（了解）

我们对于 deque 的学习不会像前面的那些容器一样要实现，因为它的实现很复杂，而且也没有什么必要，我们能够简单了解即可。

deque 叫做双端队列，虽然是这么叫的，但是其实和我们的队列没有什么关系，队列要求先进先出，但是 deque 无所谓。它本质是一个缝合怪，它缝合了 vector、list。我们简单看看它在标准库的各种成员函数就能看出来。

我们 deque 既有头插头删，又有尾插尾删，还有 [ ] 符重载。既包含了 list，又包含了 vector。

deque 产生的原因是因为我们 vector 和 list 的优缺点太过于明显。

vector优点：

尾插尾删效率不错，支持高效下标随机访问。
物理空间连续，所以高速缓存利用率高。

vector缺点：

空间需要扩容，扩容有一些代价（效率和空间浪费）。
头部和中间的插入删除效率低。

list优点：

按需申请释放空间，不需要扩容。
支持任意位置的插入删除。

list缺点：

不支持下标随机访问。

所以我们为了融合它们的优点，就有人想出用 deque 这个缝合怪。

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

但是这个设计其实也不是特别的成功，所以我们才不得不继续使用 vector 和 list。

1.1、deque 的原理介绍

我们 vector 是一个数组，它具有天然的优势，那就是下标的随机访问以及高速缓存的利用率等，但是缺点也就展露无遗。所以链表就搞出我们一块一块的独立的空间，这样我们想要插入数据就十分的方便，空间和空间是靠指针联系起来的。但是我们的物理空间不连续，我们的下标访问也就不支持了。

于是 deque 就决定搞出一段一段的数组，在这不同的小数组用一个叫做中控数组的数组相连，如果我们数据存满了也不用像 vector 一样全部扩容，而是直接开辟一个新数组出来，再用中控数组把它们连接在一起。

我们中控数组是一个指针数组。当我们中控数组满了就得扩容，然后把这些小数组拷贝到新的空间中去。

我们数据位置是这么计算的：

假设每个 buffer 数组大小是 N，求第 i 个数据

x = i / N // 算出是第几个 buffer 数组

y = i % N // 算出在 buffer 的第几个位置

ptr[ x ][ y ] // *(*(ptr + x) + y)

此时我们就可以通过下标快速的去访问 deque 的任意一个位置，虽然可能比 vector 慢一点，但是比起 list 来说就快多了。

我们想要了解明白它的结构，我们得理解清楚它的迭代器，它的迭代器有 4 个结构，也是 4 个指针。

first 和 last 分别指向 buffer 数组的开始和结束，cur 则代表我们在访问 buffer 数组的第几个数据，还有一个 node 的二级指针，这个指针是反过来指向我们中控数组上 buffer 数组存在的位置的。

它具体的结构是张这样的。

deque 中的主要成员变量就两个，是 start，finish。start 就 begin 返回的迭代器，finish就是 end 返回的迭代器。

它的迭代器遍历的执行流程。

我们一般在我们 cur 指向我们的末端之前，我们 ++ 都只要 cur++ 即可，当我们的 cur 指向我们数组末尾了，此时我们可以通过我们迭代器的二级指针 node 找到我们 buffer 数组在中控数组的位置，然后加到下一个数组。此时让我们的把迭代器更新，让我们的 first 和 cur 指向新数组的开始，而 last 指向我们这个数组的末尾，node 指向我们我们中控数组指向的位置，即可实现迭代器也就指向下一个位置了。

而 deque 的尾插就直接找到 finish 即可，如果我们 cur != last 就是还没满，我们直接让 cur++ 即可。如果满了就创建一个新的数组，然后用我们 finish 迭代器中的 node 找到我们中控数组的下一个数组位置，然后把新开辟的数组地址给我们中控数组，然后再更新 finish 指针即可。

我们 deque 的中控数组一般是不会把我们第一个 buffer 数组存到我们的第一个位置的，而是一般会存到中间位置，这样我们的前面可以给我们进行头插操作，我们头插和尾插没有什么区别，如果我们的start迭代器中 cur == first，此时我们依旧会开辟一个 buffer 数组，然后通过 start 的 node 去找到 start 在中控数组的位置（因为是存在中间，所以前面才有位置）。然后找到其前一个位置后将 buffer 数组的地址记录到中控数组上，然后更新我们的 start 迭代器即可。

deque头插尾插效率十分高，它既没有 vector 那么高代价的扩容，也没有那么 list 细碎的开空间。deque 下标随机访问效率也不错，但是比不上 vector。

它也支持 insert 和 erase，但是它的效率会非常低，因为它也要移动数据。所以说如果有一个只需要头插头删和尾插尾删的结构去使用它，这样就可以充分利用 deque 容器的优势了。这就是为什么我们 stack/queue 要使用我们 deque 做默认容器的原因。

1.2、deque 的设计缺陷

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。

与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

二、priority_queue 的介绍和使用

2.1、priority_queue 的介绍

我们在看库中的 queue 时，可能就在下面看到它的身影了。

它也是是一个容器适配器，叫做优先级队列。它的成员函数和我们的 stack 非常像。

它的重点是它的 top 和 pop 不是取最后进入或者最先进入的数据，而是取优先级最高的数据。它这里默认是取数值越大的优先级越高。我们堆的底层是一个数组，所以我们默认适配容器就是我们的 vector。

2.2、priority_queue 的使用

它可以使用默认构造和迭代器构造。

int main()
{// 默认构造priority_queue<int> pq1;// 迭代器构造vector<int> a({ 1, 2, 3, 4, 5, 6, 7, 8, 9 });priority_queue<int> pq2(a.begin(), a.end());return 0;
}

同时它的特点就是先从优先级最高的取用。然后就是第二高的以此类推。

int main()
{priority_queue<int> pq;pq.push(3);pq.push(4);pq.push(1);pq.push(5);pq.push(0);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}return 0;
}

我想让他改变我们的优先级就得靠我们第三个参数了。

我们可以看到我们第三个参数默认是 less，如果想变成小堆就得传一个叫 greater<T> 在第三个参数。

int main()
{priority_queue<int, vector<int>, greater<int>> pq;pq.push(3);pq.push(4);pq.push(1);pq.push(5);pq.push(0);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}return 0;
}

2.3、priority_queue 的实现

我们依旧先来看看它的基本框架。

namespace zxl
{template<class T, class Container = std::vector<T>>class priority_queue{public:private:Container _con;};
}

再来实现它的各项接口。

namespace zxl
{template<class T, class Container = std::vector<T>>class priority_queue{public:void AdjustUp(int child){int parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void AdjustDown(int parent){int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1]){++child;}if (_con[parent] < _con[child]){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}

主要就是用到了我们的堆，其他的很简单，如果有小伙伴看不懂我们可以去看看数据结构的堆。这就是简单的优先级队列。

我们大家可能有的时候有想要改变我们优先级的比较方式，我们这里是写死的，但是库里面却不是这样的，我们想要完成库里面的功能，得用到一个叫仿函数的东西。

首先我们得知道，其实我们的仿函数就是一个类，我们这里写一个 Less 的类。在这个类里面我们得重载一个（）。这个（）是在函数后面的（）。

class Less
{
public:bool operator()(int x, int y){return x < y;}
};

我们的仿函数一般就是空类，类的大小就是1。我们再改造改造就可以改造成模板。

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

我们可以这样调用我们的仿函数。

int main()
{Less<int> LessFunc;cout << LessFunc(1, 2) << endl;return 0;
}

如果我不说，我们肯定很多人就认为这里的 LessFunc 是一个函数，这就是仿函数名字的由来，它本质是一个类，但是这个对象可以像函数一样使用。它本质其实是这样的。

int main()
{Less<int> LessFunc;cout << LessFunc.operator()(1, 2) << endl;return 0;
}

我们除了写 Less 外还可以写一个 Greater。

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

和 Less 一样，不过一个大于一个小于。它的作用主要就是改变我们的比较方式，我们通过仿函数来修改我们的优先级队列。

我们的基本框架就变成这样了。

namespace zxl
{template<class T, class Container = std::vector<T>, class Compare = Less<T>>class priority_queue{public:private:Container _con;};
}

而我们只需要修改我们有比较逻辑的两个成员函数即可。

void AdjustUp(int child)
{Compare com;int 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(int parent)
{Compare com;int child = parent * 2 + 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 = parent * 2 + 1;}else{break;}}
}

这样我们就实现了我们库中一样的效果了。

int main()
{zxl::priority_queue<int> pq;pq.push(4);pq.push(5);pq.push(1);pq.push(8);pq.push(0);while (!pq.empty()){std::cout << pq.top() << " ";pq.pop();}std::cout << std::endl;return 0;
}

int main()
{zxl::priority_queue<int, vector<int>, Greater<int>> pq;pq.push(4);pq.push(5);pq.push(1);pq.push(8);pq.push(0);while (!pq.empty()){std::cout << pq.top() << " ";pq.pop();}std::cout << std::endl;return 0;
}