C++ STL容器适配器使用指南

适配器

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

C++ STL容器适配器使用指南

容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。也就是对一种容器封装来实现其他的容器。知道了容器适配器接下来先来讲stack。

stack容器适配器

stack的介绍

C++ STL容器适配器使用指南

1.stack应用在后进先出的上下文环境中，只能在容器的一端进行入数据和出数据。

2.stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

empty：判空操作

back：获取尾部元素操作

push_back：尾部插入元素操作

pop_back：尾部删除元素操作

3.标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

stack的使用

主要的接口

C++ STL容器适配器使用指南

有了string,vector,list的基础再玩这个stack就会很简单。

数据结构有栈的详细讲解，这里就不详细使用了。

stack<int> st;
	//入栈
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	st.pop();//出栈
	cout << st.top() << endl;//取栈顶数据
	cout << st.empty() << endl;//判空

C++ STL容器适配器使用指南

stack的模拟实现

我们可以用vector来模拟实现。

C++ STL容器适配器使用指南

namespace gpy
{
	template<class T>
	class stack
	{
	public:
		stack(){}
		void push(const T& x)
		{
			_v.push_back(x);
		}
		void pop()
		{
			_v.pop_back();
		}
		T& top()
		{
			return _v.back();
		}
		size_t size()const
		{
			return _v.size();
		}
		bool empty()const
		{
			return _v.empty();
		}
	private:
		std::vector<T> _v;
	};
}

queue

queue的介绍

C++ STL容器适配器使用指南

队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。

队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

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

标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

queue的使用

C++ STL容器适配器使用指南

跟stack差不多这里就简单的使用一下

C++ STL容器适配器使用指南

queue的模拟实现

stack可以使用vector实现，但是不能实现queue。vector的头插头删需要挪动数据效率会变低所以标准库中没有提供头插头删的接口。queue就可以用list来模拟实现。

namespace gpy
{
	template <class T>
	class queue
	{
	public:
		queue(){}
		void push(const T& x)
		{
			_lt.push_back(x);//queue的push就是list的尾插
		}
		void pop()
		{
			_lt.pop_front();//queue的pop就是list的头删
		}
		T& front(){return _lt.front();}
		const T& front()const{ return _lt.front(); }
		T& back(){ return _lt.back(); }
		const T& back()const{ return _lt.back(); }
		size_t size()const{ return _lt.size(); }
		bool empty()const{ return _lt.empty(); }
	private:
		std::list<T> _lt;
	};
}

C++ STL容器适配器使用指南

deque容器

C++ STL容器适配器使用指南

vector优点：尾插尾删的效率高，支持随机访问，cpu高速缓存命中率很高缺点：空间不够，增容代价大，一般增2倍，但增容后我只用了很少的一段空间那其他的空间就浪费了。中间和头部的插入删除效率低O(N)，需要挪动数据，list优点：

1.按需申请空间，不会造成空间浪费

2.任意位置的插入删除效率都高

缺点：不支持随机访问， CPU高速缓存命中率低

改进：用中控数组-指针数组

C++ STL容器适配器使用指南

这就是deque，双端队列和队列没有关系。在deque中，中控数组叫map,开的数组叫缓冲区。 deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

C++ STL容器适配器使用指南

它不是正真连续的空间，底层结构如上图。deque要支持随机访问叫要实现迭代器，它的迭代器很复杂简单了解。

C++ STL容器适配器使用指南

这里就不多讲解，感兴趣的可以看侯捷老师的《stl源码剖析》。

deque却没有那么牛逼优缺点：

1.它最大优点就是做stack和queue的默认适配器，stack和queue只在头尾操作，

2.它中间插入删除还是要挪动数据，很麻烦效率低

3.deque是糅合了vector和list，它没有vector随机访问效率高，任意位置的插入删除效率没有list高。

priority-queue

priority-queue的使用

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

C++ STL容器适配器使用指南

  priority_queue<int> pq;//默认是大堆
	pq.push(10);
	pq.push(5);
	pq.push(13);
	pq.push(4);
	pq.push(9);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;

C++ STL容器适配器使用指南

默认是大的优先级高，如果要变成小的优先级高，需要再传一个模板参数greater

C++ STL容器适配器使用指南

priority-queue的模拟实现

初始结构，下面都是按大堆实现的

namespace gpy
{
	template <class T,Container =vector<T>>
	class  priority_queue
	{
	public:
		priority_queue(){}
	
	private:
		Containter _con;
	};
}

首先实现尾插

C++ STL容器适配器使用指南

当插入一个数就和parent比较，比parent大就向上调整.

C++ STL容器适配器使用指南

标准库给的“<”是大堆，我们在模拟的时候也用“<”.

void AdjustUp(size_t child)
		{
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				if (_con[parent] < _con[child])
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void push(const T& x)
		{
			_con.push_back(x);
			//从尾开始调
			AdjustUp(_con.size()-1);
		}

pop，如果直接pop就不能还保持是堆的结构，先把堆顶的数和最后一个数交换在删除这个数，此时2边都还满足堆这是在向下调整

C++ STL容器适配器使用指南

先从0处开始，选出左右2个孩子中大的和parent比较，比parent大的就交换。

void AdjustDown(size_t parent)
		{
			size_t child = parent * 2 + 1;
			
			while (child<_con.size())
			{
				//选出大的孩子
				if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				{
					++child;
				}
				if (_con[parent] < _con[child])
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void pop()
		{
			swap(_con[0],_con[_con.size()-1]);
			_con.pop_back();
			AdjustDown(0);
		}

其他的接口就简单了

const T& top()const
		{
			return _con[0];//取堆顶的数据
		}
		size_t size()const
		{
			return _con.size();
		}
		bool empty()const
		{
			return _con.empty();
		}

测试一下

C++ STL容器适配器使用指南

那如果要是按低的优先级来该怎么办呢？这是就要用到仿函数了。

仿函数就是像函数一样可以使用。

template<class T>
struct Less
{
	bool operator()(const T& l, const T& r)
	{
		return l < r;
	}
};

bool Less1(int l, int r)
{
	return l < r;
}

C++ STL容器适配器使用指南

就是类里面重载了运算符。有了仿函数就可以把上面的代码在改进改进，在多传一个模板参数

namespace gpy
{
	template<class T>
	struct less
	{
		bool operator()(const T& l, const T& r)
		{
			return l < r;
		}
	};


	template<class T>
	struct greater
	{
		bool operator()(const T& l, const T& r)
		{
			return l > r;
		}
	};
	template <class T,  class Container = vector<T>,class Compare = less<T>>
	class  priority_queue
	{
	public:
		Compare com;
		void AdjustUp(size_t child)
		{
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if (com(_con[parent],_con[child]))
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void AdjustDown(size_t parent)
		{
			size_t child = parent * 2 + 1;
			
			while (child<_con.size())
			{
				//选出大的孩子
				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				if (child+1 < _con.size() && com(_con[child],_con[child+1]))
				{
					++child;
				}
				//if (_con[parent] < _con[child])
				if (com(_con[parent],_con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void push(const T& x)
		{
			_con.push_back(x);
			//从尾开始调
			AdjustUp(_con.size()-1);
		}
		void pop()
		{
			swap(_con[0],_con[_con.size()-1]);
			_con.pop_back();
			AdjustDown(0);
		}
		const T& top()const
		{
			return _con[0];//取堆顶的数据
		}
		size_t size()const
		{
			return _con.size();
		}
		bool empty()const
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

C++ STL容器适配器使用指南