?適配器

?適配器是一種設計模式(設計模式是一套被反復使用的、多數人知曉的、經過分類編目的、代碼設計經驗的總結)，該種模式是將一個類的接口轉換成客戶希望的另外一個接口。例如：
容器適配器讓一種已存在的容器類型采用另一種不同的抽象類型的工作方式實現。也就是對一種容器封裝來實現其他的容器。知道了容器適配器接下來先來講stack。

?stack容器適配器

??stack的介紹

?1.stack應用在后進先出的上下文環境中，只能在容器的一端進行入數據和出數據。
? 2.stack的底層容器可以是任何標準的容器類模板或者一些其他特定的容器類，這些容器類應該支持以下操作：
empty：判空操作
back：獲取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部刪除元素操作
?3.標準容器vector、deque、list均符合這些需求，默認情況下，如果沒有為stack指定特定的底層容器，默認情況下使用deque。

??stack的使用

?主要的接口
有了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;//判空

??stack的模擬實現

我們可以用vector來模擬實現。

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的介紹

1. 隊列是一種容器適配器，專門用于在FIFO上下文(先進先出)中操作，其中從容器一端插入元素，另一端提取元素。
2. 隊列作為容器適配器實現，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數來訪問其元素。元素從隊尾入隊列，從隊頭出隊列。
3. 底層容器可以是標準容器類模板之一，也可以是其他專門設計的容器類。該底層容器應至少支持以下操作:
   empty：檢測隊列是否為空
   size：返回隊列中有效元素的個數
   front：返回隊頭元素的引用
   back：返回隊尾元素的引用
   push_back：在隊列尾部入隊列
   pop_front：在隊列頭部出隊列
4. 標準容器類deque和list滿足了這些要求。默認情況下，如果沒有為queue實例化指定容器類，則使用標準容器deque。

??queue的使用

跟stack差不多這里就簡單的使用一下

??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;	};}

?deque容器

?vector優點：尾插尾刪的效率高，支持隨機訪問，cpu高速緩存命中率很高
缺點：空間不夠，增容代價大，一般增2倍，但增容后我只用了很少的一段空間那其他的空間就浪費了。中間和頭部的插入刪除效率低O(N)，需要挪動數據，
?list優點：1.按需申請空間，不會造成空間浪費
2.任意位置的插入刪除效率都高
缺點：不支持隨機訪問， CPU高速緩存命中率低

改進：用中控數組-指針數組

這就是deque，雙端隊列和隊列沒有關系。在deque中，中控數組叫map,開的數組叫緩沖區。
deque(雙端隊列)：是一種雙開口的"連續"空間的數據結構，雙開口的含義是：可以在頭尾兩端進行插入和刪除操作，且時間復雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。

它不是正真連續的空間，底層結構如上圖。deque要支持隨機訪問叫要實現迭代器，它的迭代器很復雜簡單了解。

這里就不多講解，感興趣的可以看侯捷老師的《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是大堆。

    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;

?默認是大的優先級高，如果要變成小的優先級高，需要再傳一個模板參數greater

??priority-queue的模擬實現

初始結構，下面都是按大堆實現的

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

?首先實現尾插

當插入一個數就和parent比較，比parent大就向上調整.
標準庫給的“<”是大堆，我們在模擬的時候也用“<”.

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邊都還滿足堆這是在向下調整

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

?測試一下

那如果要是按低的優先級來該怎么辦呢？這是就要用到仿函數了。

?仿函數就是像函數一樣可以使用。

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

就是類里面重載了運算符。有了仿函數就可以把上面的代碼在改進改進，在多傳一個模板參數

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

?

本篇文章到這就結束了，歡迎大家一起交流！