518-C++STL(容器适配器)

朱雀 2022-09-10 03:13 157阅读 0赞

## C++STL(容器适配器) ##

**标准容器 - 容器适配器 => 我们有一种设计模式，就叫做适配器模式**

**stack容器适配器相当于就是栈把deque代理了一下**

**怎么理解这个适配器？**  
1.适配器底层没有自己的数据结构，它是另外一个容器的封装，它的方法全部由底层依赖的容器进行实现的  
2.没有实现自己的迭代器  
（在栈里放一堆元素，不能用迭代器去遍历这些元素，因为根本没有实现迭代器）

//适配器的模样
    template<typename T, typename Container=deque<T>>
    class Stack
    {
        
    public:
    	void push(const T &val) {
         con.push_back(val); }
    	void pop() {
         con.pop_back(); }
    	T top()const {
         return con.back(); }
    private:
    	Container con;//成员变量，底层的容器
    };

**Container:定制的容器，用户可以不用传，默认是使用deque**  
![在这里插入图片描述][046e7dcdc89d4a07b0e89647b88b859a.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
**stack的任何栈的逻辑都没有实现，只是借助底层的deque在实现栈的逻辑**  
![在这里插入图片描述][047221396a6e497fafeec0880a424ccb.png]

## stack代码应用 ##

**stack**:  
push入栈  
pop出栈  
top查看栈顶元素  
empty判断栈空  
size返回元素个数  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][3e043fb3938c4b8fbe1b463442ad7e45.png]  
**栈是先进后出，后进先出的结构**

## queue代码应用 ##

**queue也是一种容器适配器，也没有迭代器**  
**先进先出，后进后出的结构**  
**queue:**  
push入队  
pop出队  
front查看队头元素  
back查看队尾元素  
empty判断队空  
size返回元素个数  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][02f2e05a5501473bb6860197aec290cf.png]  
**优先级队列**  
（谁优先级大，谁就出队）  
priority\_queue:  
push入队  
pop出队  
top查看队顶元素  
empty判断队空  
size返回元素个数  
**默认**：大根堆  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
![在这里插入图片描述][3a051d74702d40e791783698d05c502a.png]  
**数据从大到小依次出队，数据越大，优先级越高。**

## 思考总结 ##

**stack => deque 为什么不依赖vector呢？？？**  
**queue => deque 为什么不依赖vector呢？？？**

**1.vector的初始内存使用效率太低了！没有deque好**  
queue< int > 或者stack< int >  
如果底层依赖的是 vector  
是从0-1-2-4-8 慢慢扩容  
而使用deque 的第二维就是默认大小是 4096/sizeof(int) = 1024  
**2.对于queue来说，需要支持尾部插入，头部删除，都保证时间复杂度是O(1) 如果queue依赖vector，头部删除，后面元素都要往前挪动，则其出队效率很低**  
**3.vector需要大片的连续内存，而deque只需要分段的内存，当存储大量数据（有大量碎片的情况)时，显然deque对于内存的利用率更好一些**

**priority\_queue => vector 为什么依赖vector？？？**  
底层默认把数据组成一个大根堆结构（堆顶的元素值是最大的），  
大根堆结构是在一个内存连续的数组上构建一个大根堆（大根堆是要以节点的下标进行计算父节点和左右孩子节点的位置关系的，需要的是连续的内存空间才能实现）  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]

[046e7dcdc89d4a07b0e89647b88b859a.png]: /images/20220829/ece822c002c44f7b89d910ec146bf27a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/5f63dffcf0904293b21a1193a5b37e41.png
[047221396a6e497fafeec0880a424ccb.png]: /images/20220829/18ff6d6b6e414ef7984c5f1d168da40c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/393b27f2602640c58627ebf350de3a68.png
[3e043fb3938c4b8fbe1b463442ad7e45.png]: /images/20220829/c42d54fa0fc64b3d9fea2b0d3798a284.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/f12032e6f40b4a1989ab4d08b8b5df1c.png
[02f2e05a5501473bb6860197aec290cf.png]: /images/20220829/5faf20bb3cfa4ac2930fd2b52eed0cd2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/66df13c3c0ec4f18a4cee128e9459c45.png
[3a051d74702d40e791783698d05c502a.png]: /images/20220829/8f35db4b28f74c828ba2b9bca0ab564f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220829/13185e13fcc34d6bad62ed7d368c1591.png