一、适配器（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;
	}
};