C++ STL中的容器适配器 stack、queue、priority

文章目录

• 
  

  一、适配器（adaptor）

• 
  

  二、容器适配器（container adaptor）

• • • 1、栈（stack）
    • 2、队列（queue）
    • - - - - - - - - - - - - - - -
    • （关于仿函数）
    • 3、优先队列（priority_queue）
• 简介：双端队列（deque）
• • • 1、设计初衷
    • 2、优势
    • 3、底层结构
    • 4、缺陷
    • 5、STL 选择 deque 作为 stack 和 queue 的底层默认容器的原因
    • 6、总结

一、适配器（adaptor）

在了解容器适配器之前，我们首先应该知道什么是适配器。

适配器是一种设计模式（设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结），该种模式是将一个类的接口转换成客户希望的另外一个接口。

举个具体的例子，在日常生活中，如果想要给我们的手机充电，直接使用 220V 的交流电是不合适的，因为 220V 的电压对手机来说太高了，于是我们会使用电源适配器（充电头），它将 220V 的交流电转换为适合手机的电压来给手机充电。

那么，这就方便我们理解什么是容器适配器了。

二、容器适配器（container adaptor）

在很多情况下，已有的容器（比如 vector、list、deque 等）虽然都能满足要求，但是它们的接口不完全适合或不应该全都暴露出来。

于是我们就会想，能不能也搞一个适配器，对已有的满足要求的容器进行适当的封装，只暴露适合的接口，这样就方便了，这就是容器适配器。

C++的STL提供了三种容器适配器，分别是栈、队列、优先队列（stack、queue 和 priority_queue）。

stack 可以由 vector、list、deque 封装而成。

queue 可以由 list、deque 封装而成。

priority_queue 可以由 vector、deque 封装而成。

推荐的 C/C++ 参考文档：http://www.cplusplus.com

下面将分别对这三种容器适配器进行说明。

自己在进行模拟实现时，为了防止跟库里的命名冲突，需要放到自己定义的命名空间里。

1、栈（stack）

stack 的特点：只能从容器的一端进行元素的插入和提取 *** 作，LIFO（后进先出）。

为了支持 stack 的基本 *** 作，stack 的底层容器可以是任何的标准容器类模板或者一些其他的专门设计的容器类，这些容器应该支持以下 *** 作：

1）empty：判空
2）size：获取有效元素个数
3）back：获取尾部元素
4）push_back：尾部插入元素
5）pop_back：尾部删除元素

这些接口被封装之后就是 stack 的 empty、size、top、push、pop 接口。

标准容器 vector、list、deque 都能实现以上 *** 作。

默认情况下，如果没有为 stack 的实例化指定底层容器，将使用 deque 。

模拟实现：

namespace MyLib
{
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		bool empty() const
		{
			return _con.empty();
		}

		size_t size() const
		{
			return _con.size();
		}

		const T& top() const
		{
			return _con.back();
		}

		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_back();
		}


	private:
		Container _con;
	};
}

2、队列（queue）

queue 的特点：只能从容器的一端插入元素，从另一端提取元素，FIFO（先进先出）。

为了支持 queue 的基本 *** 作，queue 的底层容器可以是标准容器类模板之一或者一些其他的专门设计的容器类，这些容器应该支持以下 *** 作：

1）empty：判空
2）size：获取有效元素个数
3）front：获取头部元素
4）back：获取尾部元素
5）push_back：尾部插入元素
6）pop_front：头部删除元素

这些接口被封装之后就是 queue 的 empty、size、front、back、push、pop 接口。

标准容器 list、deque 都能实现以上 *** 作。

默认情况下，如果没有为 queue 的实例化指定底层容器，将使用 deque 。

模拟实现：

namespace MyLib
{
	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		bool empty() const
		{
			return _con.empty();
		}

		size_t size() const
		{
			return _con.size();
		}

		const T& front() const
		{
			return _con.front();
		}

		const T& back() const
		{
			return _con.back();
		}

		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_front();
		}


	private:
		Container _con;
	};
}

- - - - - - - - - - - - - - - （关于仿函数）

仿函数（也叫函数对象）其实并不是函数，它是一个类，在行为上很像函数。

举个既简单又易于理解的例子：

//定义一个类
struct F
{
	void operator()(int a, int b)
	{
		cout << a << endl; 
		cout << b << endl;
	}
};

//调用仿函数
F print;
print(3, 5);

仿函数没有任何成员变量，只有重载了运算符 () 的成员函数。

于是，一个类对象的成员函数的调用，看起来特别像真正的函数调用。

真正函数中的 print 是个函数名，而仿函数中的 print 是个对象名。

3、优先队列（priority_queue）

priority_queue 的特点：元素被赋予优先级。

当访问元素时，具有最高优先级的元素最先删除，Largest Out（最高级先出）。

优先级的具体标准可以由用户来定义。

priority_queue 通常采用堆数据结构来实现。

优先队列在底层容器上使用了堆算法将元素构造成堆的结构，因此 priority_queue 在本质上就是堆（heap）。

默认情况下 priority_queue 是最大堆。

为了支持 priority_queue 的基本 *** 作，priority_queue 的底层容器可以是任何的标准容器类模板或者一些其他的专门设计的容器类，这些容器应该可以通过随机访问迭代器访问，并支持以下 *** 作：

1）empty：判空
2）size：获取有效元素个数
3）front：获取头部元素
4）push_back：尾部插入元素
5）pop_back：尾部删除元素

这些接口被封装之后就是 priority_queue 的 empty、size、top、push、pop 接口。

标准容器 vector、deque 都能实现以上 *** 作。

默认情况下，如果没有为 priority_queue 的实例化指定底层容器，将使用 vector 。

为什么 STL 选择 vector 作为 priority_queue 的底层默认容器？
priority_queue 本质上是堆，（不管进行何种 *** 作，之后都）需要时刻保持堆的结构，使用的是堆算法，这需要底层容器支持频繁随机访问。

vector 显然是满足要求的，
deque 虽然也可以，但是随机访问速度较慢，不适合频繁随机访问，
因此，STL 选择 vector 作为 priority_queue 的底层默认容器。

使用例子：

//使用迭代器区间构造优先队列（最大堆）
priority_queue<int> pq(v.begin(), v.end());

//使用迭代器区间构造优先队列（最小堆）
priority_queue<int, vector<int>, greater<int>> pq(v.begin(), v.begin() + k);

//返回优先级最高（或最低）的元素
pq.top();

//删除优先级最高（或最低）的元素
pq.pop();

模拟实现：

其实，基本上就是在写堆（数据结构）的接口。

namespace MyLib
{
	//仿函数
	template<class T>
	struct less
	{
		bool operator()(const T& x, const T& y) const
		{
			return x < y;
		}
	};

	//仿函数
	template<class T>
	struct greater
	{
		bool operator()(const T& x, const T& y) const
		{
			return x > y;
		}
	};

                                                    // 仿函数作为模板参数
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	private:
		// 向上调整算法
		void adjust_up(size_t child)
		{
			Compare com;
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{        // 调用仿函数
				if (com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		// 向下调整算法
		void adjust_down(size_t parent)
		{
			Compare com;
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{                                   // 调用仿函数
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					++child;
				}
					 // 调用仿函数
				if (com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

	public:
		priority_queue()
		{}


		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			:_con(first, last)
		{
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
			{
				adjust_down(i);
			}
		}

		void push(const T& val)
		{
			_con.push_back(val);
			adjust_up(_con.size() - 1);
		}

		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}

		const T& top() const
		{
			return _con[0];
		}

		size_t size() const
		{
			return _con.size();
		}

		bool empty() const
		{
			return _con.empty();
		}
		

	private:
		Container _con;
	};
}

有了仿函数的基本概念，这就好理解 priority_queue 中的两个仿函数 less 和 greater 了。

//仿函数less
template<class T>
struct less
{
	bool operator()(const T& x, const T& y) const
	{
		return x < y;
	}
};

//仿函数greater
template<class T>
struct greater
{
	bool operator()(const T& x, const T& y) const
	{
		return x > y;
	}
};

为了使代码通用，而不是只支持某种特定的类型，给 less 和 greater 都加上了模板参数。

加上了仿函数之后，就能更好地控制 priority_queue 是最大堆还是最小堆了。

在 priority_queue 中使用仿函数，就是为了控制优先级。

仿函数的具体逻辑可以按照自己的需求来实现，然后在定义一个优先队列对象时传参即可。

即上面所说的：优先级的具体标准可以由用户来定义。

简介：双端队列（deque）

deque 即 double ended queue，译为双端队列，是一个标准容器类模板。

虽然叫双端队列，但实际上它并不是队列。

它是一种双开口的具有“连续”空间且支持随机访问的数据结构。

双开口的含义：可以在头尾两端进行插入和删除 *** 作，且时间复杂度均为O(1) 。

1、设计初衷

先将 vector 和 list 对比一下：

vector
1）优点：支持下标的随机访问。

2）缺点：插入和删除 *** 作的效率低，尤其是头插和头删；空间满了需要扩容且扩容的代价较大，并且空间存在一定程度上的浪费。

list
1）优点：任意位置的插入和删除 *** 作的效率高，都是O(1) ；按需申请小块空间，不存在空间浪费。

2）缺点：不支持下标的随机访问。

vector 和 list 的优缺点可以说是正好相反的。

基于上述事实，deque 融合了 vector 和 list 的优点：
既有随机访问的特点，同时也有头插头删效率高的特点，这解决了 vector 头插头删效率低的问题，同时也解决了 list 不能随机访问的问题。

2、优势

将 deque 分别与 vector 和 list 做对比：

1）与 vector 相比，deque 的优势是：头插和头删时，不需要挪动元素，效率特别高；而且在扩容时，也不需要拷贝大量的元素，其效率是比 vector 高的。

2）与 list 相比，deque 的优势是：底层是（分段的）连续空间，空间利用率比较高，不需要存储额外字段。

deque 虽然具有上述优势，但是在实际中用得很少，并不是主流的数据结构。

至于为什么，了解它的底层结构和缺陷就知道了。

3、底层结构

deque 的底层并不是真正的一段连续的空间，而是由分段的连续空间组合而成的。

实际上，deque 类似于一个动态的二维数组。

为了维护其“整体连续”以及随机访问的假象，其迭代器的设计是比较复杂的。

deque 虽然支持随机访问，但是随机访问速度较慢，不适合频繁随机访问。

如果不明白或者想要了解更多，请自行搜索，最好边看图边理解。

4、缺陷

deque 有一个很大的缺陷：不适合遍历。

因为在遍历时，deque 的迭代器需要频繁地去检测其是否移动到
某段空间的边界，这会导致效率低下，而在序列式场景中，可能需要经常遍历。

还有一个缺陷：中间的插入和删除 *** 作效率低。

因此在实际应用中，当需要线性结构时，大多数情况下会优先考虑 vector 和 list 。

5、STL 选择 deque 作为 stack 和 queue 的底层默认容器的原因

经过上述讲解之后，这个问题也就不难回答了：

（1）deque 作为 stack 的底层容器：
与 vector 相比，其优势是：扩容代价不大，不需要拷贝数据，浪费空间也不多。

（元素增长时）
与 list 相比，其优势是：CPU高速缓存命中率高，而且申请和释放空间的次数少、代价低。

（元素增长或减少时）

deque 作为 queue 的底层容器：
与 list 相比，其优势是：CPU高速缓存命中率高，而且申请和释放空间的次数少、代价低。

（元素增长或减少时）

（2）stack 和 queue 都不需要遍历（因此它们都没有迭代器），只需要在固定的一端或者两端进行 *** 作。

（3）再结合 deque 自身的优缺点：适合一端或者两端频繁的插入和删除，不适合中间的插入和删除，也不适合遍历。

综上所述，deque 作为 stack 和 queue 的底层容器，正好充分发挥了它的优势，且完美避开了它的缺陷，可以说是完胜 vector 和 list 的。

因此，STL 选择 deque 作为 stack 和 queue 的底层默认容器。

6、总结

从某种角度上看，deque 是 vector 和 list 相互折衷后所产生的容器，它虽然拥有两者的优点，但是由于某些缺陷，实用性并不大，就显得“华而不实”了。

虽然如此，但 deque 仍有用武之地，比如作为 stack 和 queue 的底层默认容器。

更多文章：
C++ STL中 list 的模拟实现
C++ STL中 vector 的模拟实现
C++ STL中 string类的模拟实现