网站制作 客户刁难,自建网站推广的最新发展,房地产设计院,wordpress 好用的主题目录
容器适配器的理解
容器适配器的实现与使用
三类容器适配器
基本概述
示例代码 容器适配器的理解 容器适配器对底层容器进行封装#xff0c;不具备自己的数据结构 容器适配器的方法全都由底层容器实现#xff0c;不支持迭代器 容器适配器的实现与使用
// 容器适配器…目录
容器适配器的理解
容器适配器的实现与使用
三类容器适配器
基本概述
示例代码 容器适配器的理解 容器适配器对底层容器进行封装不具备自己的数据结构 容器适配器的方法全都由底层容器实现不支持迭代器 容器适配器的实现与使用
// 容器适配器的实现与使用#includeiostream
#includevector
#includedeque
#includelist
using namespace std;templatetypename T, typename ContainerdequeT
// typename ContainerdequeT表示默认底层容器为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()
{Stackint 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;Stackint, vectorint 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;Stackint, listint 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的节点其左子节点的下标为2i1其右子节点的下标为2i2 这些规律建立在内存连续的基础之上 示例代码
/*
stackpush入栈 pop出栈 top栈顶元素 empty判断栈空 size元素数量
queuepush入队 pop出队 front队头元素 back队尾元素 empty判断队空 size元素数量
priority_queuepush入队 pop出队 top队顶元素 empty判断队空 size元素数量
*/#includeiostream
#includevector // 向量容器
#includedeque // 双端队列
#includelist // 链表容器
#includestack // 栈
#includequeue // 队列、优先队列
using namespace std;int main()
{stackint 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;queueint 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_queueint 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
*/
