C++ : STL容器（适配器）之stack、queue剖析

一、stack、queue的接口

（一）stack 接口说明

• stack()
  • 构造空的栈
• empty()
  • 检测stack是否为空
• size()
  • 返回stack中元素的个数
• top()
  • 返回栈顶元素的引用
• push()
  • 将元素val压入stack中
• pop()
  • 将stack中尾部的元素弹出

（二）queue 接口说明

• empty：
  • 检测队列是否为空
• size：
  • 返回队列中有效元素的个数
• front：
  • 返回队头元素的引用
• back：
  • 返回队尾元素的引用
• push_back：
  • 在队列尾部入队列
• pop_front：
  • 在队列头部出队列

二、stack、queue的模拟实现

（一）stack、queue是容器适配器

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

stack、queue底层默认容器–deque

1、deque概念及原理

deque(双端队列)：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个
动态的二维数组，其底层结构如下图所示：

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问
的假象，落在了deque的迭代器身上

2、stl中deque迭代器的实现（部分）

在stl源码实现中，下面截取了迭代器的部分，有很多知识值得学习。

1、普通迭代器和const迭代器实现技巧

我们知道const对象的实现就是不能修改值，因此只需要在实现迭代器时针对一下->和*的返回值即可，源码库中使用两个模板参数巧妙的解决这个问题。

2、非类型模板参数

在模板进阶中我们会讲到非类型模板参数的使用，使用size_t作为参数相当于一个宏的使用。
template <class T, class Ref, class Ptr, size_t BufSiz>

3、重载的复用

先实现重载符号 += 接着的 +、-、-=都采用了复用的方式，使得代码更简洁。
在实现++、–时，先实现前置++，前置–，再实现后置++，后置–，这里也可以复用

#pragma once
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
	typedef __deque_iterator<T, T&, T*, BufSiz>             iterator;
	typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;

	typedef T value_type;
	typedef Ptr pointer;
	typedef Ref reference;
	typedef T** map_pointer;
	typedef ptrdiff_t difference_type;
	typedef __deque_iterator self;

	//构造函数
	//有参构造
	__deque_iterator(T* x, map_pointer y)
		: cur(x), first(*y), last(*y + buffer_size()), node(y) {}
	//默认构造
	__deque_iterator() : cur(0), first(0), last(0), node(0) {}
	//拷贝构造
	__deque_iterator(const iterator& x)
		: cur(x.cur), first(x.first), last(x.last), node(x.node) {}

	//更新结点信息
	void set_node(map_pointer new_node) {
		node = new_node;
		first = *new_node;
		last = first + difference_type(buffer_size());
	}

	//运算符重载
	reference operator*() const { return *cur; }
	pointer operator->() const { return &(operator*()); }
	self& operator++() {
		++cur;
		if (cur == last) {
			set_node(node + 1);
			cur = first;
		}
		return *this;
	}

	self operator++(int) {
		self tmp = *this;
		++*this;
		return tmp;
	}

	self& operator--() {
		if (cur == first) {
			set_node(node - 1);
			cur = last;
		}
		--cur;
		return *this;
	}

	self operator--(int) {
		self tmp = *this;
		--*this;
		return tmp;
	}

	self& operator+=(difference_type n) {
		difference_type offset = n + (cur - first);
		if (offset >= 0 && offset < difference_type(buffer_size()))
			cur += n;
		else {
			difference_type node_offset =
				offset > 0 ? offset / difference_type(buffer_size())
				: -difference_type((-offset - 1) / buffer_size()) - 1;
			set_node(node + node_offset);
			cur = first + (offset - node_offset * difference_type(buffer_size()));
		}
		return *this;
	}

	self operator+(difference_type n) const {
		self tmp = *this;
		return tmp += n;
	}

	self& operator-=(difference_type n) { return *this += -n; }

	self operator-(difference_type n) const {
		self tmp = *this;
		return tmp -= n;
	}

	reference operator[](difference_type n) const { return *(*this + n); }

	bool operator==(const self& x) const { return cur == x.cur; }
	bool operator!=(const self& x) const { return !(*this == x); }
	bool operator<(const self& x) const {
		return (node == x.node) ? (cur < x.cur) : (node < x.node);
	}


	//成员变量
private:
	T* cur;
	T* first;
	T* last;
	map_pointer node;
};

（二）stack的模拟实现

通过stack的实现可以看出，stack的实现是基于deque。栈的实现就是将双端队列进行包装，这个过程就像是deque是交流电，而stack就是这个插头，为用户提供需要的接口。

#pragma once
#include<vector>
#include<list>
#include<deque>
using namespace std;

namespace wgm {
	template<class T, class Container = deque<T>>
	class stack {
	public:
		void push(const T& val) {
			_con.push_back(val);
		}

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

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

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


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

	private:
		Container _con;
	};
}

（三）queue的模拟实现

和stack类似，在它的参数列表中也有一个参数类型Container(容器），它也存在默认参数deque。这里的参数不能传入vector,因为vector不支持头部出元素的pop_front操作。

#pragma once
#include<vector>
#include<list>
#include<deque>
using namespace std;

namespace wgm {
	template<class T, class Container = deque<T>>
	class queue {
	public:
		void push(const T& val) {
			_con.push_back(val);
		}

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

		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();
		}

	private:
		Container _con;
	};
}

三、优先队列

（一）优先队列的概念

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大（小）的。实际上，这就和之前学过的数据结构堆的性质一样。

（二）优先队列的接口说明

• empty()：
  • 检测容器是否为空
• size()：
  • 返回容器中有效元素个数
• front()：
  • 返回容器中第一个元素的引用
• push_back()：
  • 在容器尾部插入元素
• pop_back()：
  • 删除容器尾部元素

（三）优先队列的模拟实现

#pragma once
#include<vector>
#include<iostream>
using namespace std;

namespace wgm {
	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 {
	public:
#define FATHER(i) (((i) - 1) / 2)
#define LEFT(i) (((i) * 2) + 1)
#define RIGHT(i) (((i) * 2) + 2)
		void AdjustUp(int i)
		{
			Compare cmp;
			while (FATHER(i) >= 0 && Compare()(_con[FATHER(i)], _con[i])) {
				swap(_con[i], _con[FATHER(i)]);
				i = FATHER(i);
			}
		}

		void AdjustDown(int i)
		{
			while (LEFT(i) < _con.size()) {
				int l = LEFT(i), r = RIGHT(i), ind = i;
				Compare cmp;
				if (cmp(_con[ind], _con[LEFT(i)])) ind = LEFT(i);
				if (RIGHT(i) < _con.size() && cmp(_con[ind], _con[RIGHT(i)])) ind = RIGHT(i);
				if (ind == i) break;
				swap(_con[i], _con[ind]);
				i = ind;
			}
		}

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

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

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

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

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

	private:
		Container _con;
	};
}

四、结束语

这个部分相对于之前学的容器要简单，只不过这个双端队列的实现源码还是挺有意思的，可以尝时着实现实现。