标准模板库STL——容器适配器-stack/queue/priority_queue

目录

容器适配器的理解

容器适配器的实现与使用

三类容器适配器

基本概述

示例代码

---

容器适配器的理解

容器适配器对底层容器进行封装，不具备自己的数据结构

容器适配器的方法全都由底层容器实现，不支持迭代器

容器适配器的实现与使用

// 容器适配器的实现与使用#include<iostream>
#include<vector>
#include<deque>
#include<list>
using namespace std;template<typename T, typename Container=deque<T>>
// typename Container=deque<T>表示默认底层容器为deque，也可由用户指定底层容器
class Stack
{
public:// 借助底层容器的方法void push(const T & val)  { con.push_back(val); } // push代理push_backvoid pop()                { con.pop_back(); }     // pop代理pop_backT top() const             { return con.back(); }  // top代理backsize_t size()             { return con.size(); }  // size代理sizebool empty() const        { return con.empty(); } // empty代理empty
private:Container con; // 底层容器
};int main()
{Stack<int> sta1;for(int i = 0; i < 20; i ++)sta1.push(rand()%100 + 1);cout << "使用默认底层容器deque实现栈Stack" << endl;cout << sta1.size() << "个随机整数如下：" << endl;while(! sta1.empty()){cout << sta1.top() << " ";sta1.pop();}cout << endl;cout << "--------------------------------------------" << endl;Stack<int, vector<int>> sta2;for(int i = 0; i < 20; i ++)sta2.push(rand()%100 + 1);cout << "指定底层容器为vector实现栈Stack" << endl;cout << sta2.size() << "个随机整数如下：" << endl;while(! sta2.empty()){cout << sta2.top() << " ";sta2.pop();}cout << endl;cout << "--------------------------------------------" << endl;Stack<int, list<int>> sta3;for(int i = 0; i < 20; i ++)sta3.push(rand()%100 + 1);cout << "指定底层容器为list实现栈Stack" << endl;cout << sta3.size() << "个随机整数如下：" << endl;while(! sta3.empty()){cout << sta3.top() << " ";sta3.pop();}cout << endl;return 0;
}/*
使用默认底层容器deque实现栈Stack
20个随机整数如下：
37 28 43 96 92 62 28 82 46 6 65 63 59 79 25 70 1 35 68 42  
--------------------------------------------
指定底层容器为vector实现栈Stack
20个随机整数如下：
95 36 100 68 13 70 39 72 27 48 96 19 17 22 83 93 54 3 5 92 
--------------------------------------------
指定底层容器为list实现栈Stack
20个随机整数如下：
79 30 42 24 60 38 58 63 45 48 69 54 12 42 65 74 34 23 12 4 
*/

三类容器适配器

// 1、栈stack

stack默认依赖deque

// 2、队列queue

queue默认依赖deque

// 3、优先队列priority_queue

priority_queue默认依赖vector

基本概述

// stack和queue都默认依赖deque的理由

1、初始时，vector内存使用效率低，deque内存使用效率高

2、对于queue来说，需要支持尾部入队和头部出队

依赖deque可将入队和出队的时间复杂度控制在O(1)

依赖vector入队O(1)，但是出队O(n)，会导致出队效率很低

3、当存储大量数据时，vector需要连续内存，内存利用率低

deque只需分段内存，内存利用率高

// priority_queue默认依赖vector的理由

priority_queue底层数据结构为大根堆（堆顶元素值最大）

vector内存连续可以更好地适应大根堆，理由如下：

如果堆节点的下标从0开始编号（堆顶节点的下标为0），

那么对于堆中某个下标为i的节点，其左子节点的下标为2i+1，其右子节点的下标为2i+2

这些规律建立在内存连续的基础之上

示例代码

/*
stack：push入栈 pop出栈 top栈顶元素 empty判断栈空 size元素数量
queue：push入队 pop出队 front队头元素 back队尾元素 empty判断队空 size元素数量
priority_queue：push入队 pop出队 top队顶元素 empty判断队空 size元素数量
*/#include<iostream>
#include<vector> // 向量容器
#include<deque>  // 双端队列
#include<list>   // 链表容器
#include<stack>  // 栈
#include<queue>  // 队列、优先队列
using namespace std;int main()
{stack<int> sta;for(int i = 0; i < 20; i ++)sta.push(rand()%100 + 1);cout << "栈stack" << endl;cout << sta.size() << "个随机整数如下：" << endl;while(! sta.empty()){cout << sta.top() << " ";sta.pop();}cout << endl;cout << "--------------------------------------------" << endl;queue<int> que;for(int i = 0; i < 20; i ++)que.push(rand()%100 + 1);cout << "队列queue" << endl;cout << que.size() << "个随机整数如下：" << endl;while(! que.empty()){cout << que.front() << " ";que.pop();}cout << endl;cout << "--------------------------------------------" << endl;priority_queue<int> pque;for(int i = 0; i < 20; i ++)pque.push(rand()%100 + 1);cout << "优先队列priority_queue" << endl;cout << pque.size() << "个随机整数如下：" << endl;while(! pque.empty()){cout << pque.top() << " ";pque.pop();}cout << endl;return 0;
}/*
栈stack
20个随机整数如下：
37 28 43 96 92 62 28 82 46 6 65 63 59 79 25 70 1 35 68 42  
--------------------------------------------
队列queue
20个随机整数如下：
92 5 3 54 93 83 22 17 19 96 48 27 72 39 70 13 68 100 36 95 
--------------------------------------------
优先队列priority_queue
20个随机整数如下：
79 74 69 65 63 60 58 54 48 45 42 42 38 34 30 24 23 12 12 4 
*/