【C++】STL—容器适配器介绍

末蓝、 2022-12-22 04:35 171阅读 0赞

### 文章目录 ###

*  1、容器适配器
 *   *  1.1 什么是适配器
     *  1.2 STL标准库中stack和queue的底层结构
     *  1.3 deque的简单介绍
 *  2、stack的介绍和使用
 *   *  2.1 stack的介绍
     *  2.2 stack的使用
     *  2.3 stack的模拟实现
 *  3、queue的介绍和使用
 *   *  3.1 queue的介绍
     *  3.2 queue的使用
     *  3.3 queue的模拟实现
 *  4、priority\_queue的介绍和使用
 *   *  4.1 priority\_queue的介绍
     *  4.2 priority\_queue的使用
     *  4.3 priority\_queue的模拟实现

# 1、容器适配器 #

## 1.1 什么是适配器 ##

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center]

## 1.2 STL标准库中stack和queue的底层结构 ##

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和queue只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque（双端队列）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 2]

## 1.3 deque的简单介绍 ##

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 3]  
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 4]  
详细过程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 5]  
**deque的优缺点**：  
1、与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。  
2、与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。  
3、deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

# 2、stack的介绍和使用 #

## 2.1 stack的介绍 ##

stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 6]

## 2.2 stack的使用 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 7]

## 2.3 stack的模拟实现 ##

#pragma once
    
    #include <vector>
    
    namespace bite
    {
        
    	template<class T>
    	class stack
    	{
        
    	public:
    		stack()
    		{
        }
    
    		void push(const T& x)
    		{
        
    			_con.push_back(x);
    		}
    
    		void pop()
    		{
        
    			_con.pop_back();
    		}
    
    		T& top()
    		{
        
    			return _con.back();
    		}
    
    		const T& top()const
    		{
        
    			return _con.back();
    		}
    
    		int size()const
    		{
        
    			return _con.size();
    		}
    
    		bool empty()const
    		{
        
    			return _con.empty();
    		}
    	private:
    		std::vector<T> _con
    	};
    }

# 3、queue的介绍和使用 #

## 3.1 queue的介绍 ##

队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 8]

## 3.2 queue的使用 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 9]

## 3.3 queue的模拟实现 ##

#pragma once
    
    #include <list>
    
    namespace bite
    {
        
    	template<class T>
    	class queue
    	{
        
    	public:
    		queue()
    		{
        }
    		void push(const T& x)
    		{
        
    			q.push_back(x);
    		}
    
    		void pop()
    		{
        
    			q.pop_front();
    		}
    
    		T& front()
    		{
        
    			return q.front();
    		}
    
    		const T& front()const
    		{
        
    			return q.front();
    		}
    
    		T& back()
    		{
        
    			return q.back();
    		}
    
    		const T& back()const
    		{
        
    			return q.back();
    		}
    
    		size_t size()const
    		{
        
    			return q.size();
    		}
    
    		bool empty()const
    		{
        
    			return q.empty();
    		}
    	private:
    		std::list<T> q;
    	};
    }

# 4、priority\_queue的介绍和使用 #

## 4.1 priority\_queue的介绍 ##

优先级队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。

## 4.2 priority\_queue的使用 ##

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority\_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority\_queue。注意：默认情况下priority\_queue是大堆。

## 4.3 priority\_queue的模拟实现 ##

#pragma once
    
    #include <vector>
    namespace bite
    {
        
    	template<class T,class Con=vector<T>,class CMP=less<T>>
    	class priority_queue
    	{
        
    	public:
    		priority_queue()
    		{
        }
    
    		template<class Iterator>
    		priority_queue(Iterator first, Iterator last)
    			: _con(first, last)
    		{
        
    			int root = ((_con.size() - 2) >> 1);
    			while (root >= 0)
    			{
        
    				_AdjustDown(root);
    				root--;
    			}
    		}
    
    		void push(const T& x)
    		{
        
    			_con.push_back(x);
    			_AdjustUp();
    		}
    
    		void pop()
    		{
        
    			if (empty())
    				return;
    
    			swap(_con.front(), _con.back());
    			_con.pop_back();
    			_AdjustDown(0);
    		}
    
    		const T& top()const
    		{
        
    			return _con.front();
    		}
    
    		size_t size()const
    		{
        
    			return _con.size();
    		}
    
    		bool empty()const
    		{
        
    			return _con.empty();
    		}
    
    	private:
    		//´´½¨Ð¡¶Ñ
    		void _AdjustDown(size_t parent)
    		{
        
    			size_t child = parent * 2 + 1;
    			size_t size = _con.size();
    
    			CMP cmp;
    			while (child < size)
    			{
        
    				if (child + 1 < size&&cmp(_con[child], _con[child + 1]))
    					child += 1;
    				if (CMP()(_con[parent], _con[child]))
    				{
        
    					swap(_con[parent], _con[child]);
    					parent = child;
    					child = parent * 2 + 1;
    				}
    				else
    					break;
    			}
    		}
    
    		void _AdjustUp()
    		{
        
    			size_t child = _con.size() - 1;
    			size_t parent = ((child - 1) >> 1);
    
    			while (child)
    			{
        
    				if (CMP()(_con[parent], _con[child]))
    				{
        
    					swap(_con[parent], _con[child]);
    					child = parent;
    					parent = ((child - 1) >> 1);
    				}
    				else
    					break;
    			}
    		}
    	private:
    		Con _con;
    	};
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/62b838b2a97042b1a38f928777462195.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/37a74ca378654fe293f8cf8267285fda.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/3dff663a4f7f4ee19b183bb2297929e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/6c0653d1c4314973a02cf4fb2b1a21b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/4655944eff034c288e75ddab59ac6934.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/873e559f141640658a63cb8a78153df7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221120/d8b10ecedca14e9a88b6018f7e214f24.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221120/58c965eae3ba42fc8db8ca57d54e8667.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221120/5e3bf5158f1743f6a55b5105fd82b182.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221120/bee25477e73f4570bf17ece9b830f970.png