?適配器

?適配器是一種設(shè)計(jì)模式(設(shè)計(jì)模式是一套被反復(fù)使用的、多數(shù)人知曉的、經(jīng)過(guò)分類編目的、代碼設(shè)計(jì)經(jīng)驗(yàn)的總結(jié))，該種模式是將一個(gè)類的接口轉(zhuǎn)換成客戶希望的另外一個(gè)接口。例如：
容器適配器讓一種已存在的容器類型采用另一種不同的抽象類型的工作方式實(shí)現(xiàn)。也就是對(duì)一種容器封裝來(lái)實(shí)現(xiàn)其他的容器。知道了容器適配器接下來(lái)先來(lái)講stack。

?stack容器適配器

??stack的介紹

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

??stack的使用

?主要的接口
有了string,vector,list的基礎(chǔ)再玩這個(gè)stack就會(huì)很簡(jiǎn)單。

?數(shù)據(jù)結(jié)構(gòu)有棧的詳細(xì)講解，這里就不詳細(xì)使用了。

stack<int> st;	//入棧	st.push(1);	st.push(2);	st.push(3);	st.push(4);	st.pop();//出棧	cout << st.top() << endl;//取棧頂數(shù)據(jù)	cout << st.empty() << endl;//判空

??stack的模擬實(shí)現(xiàn)

我們可以用vector來(lái)模擬實(shí)現(xiàn)。

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. 隊(duì)列是一種容器適配器，專門(mén)用于在FIFO上下文(先進(jìn)先出)中操作，其中從容器一端插入元素，另一端提取元素。
2. 隊(duì)列作為容器適配器實(shí)現(xiàn)，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數(shù)來(lái)訪問(wèn)其元素。元素從隊(duì)尾入隊(duì)列，從隊(duì)頭出隊(duì)列。
3. 底層容器可以是標(biāo)準(zhǔn)容器類模板之一，也可以是其他專門(mén)設(shè)計(jì)的容器類。該底層容器應(yīng)至少支持以下操作:
   empty：檢測(cè)隊(duì)列是否為空
   size：返回隊(duì)列中有效元素的個(gè)數(shù)
   front：返回隊(duì)頭元素的引用
   back：返回隊(duì)尾元素的引用
   push_back：在隊(duì)列尾部入隊(duì)列
   pop_front：在隊(duì)列頭部出隊(duì)列
4. 標(biāo)準(zhǔn)容器類deque和list滿足了這些要求。默認(rèn)情況下，如果沒(méi)有為queue實(shí)例化指定容器類，則使用標(biāo)準(zhǔn)容器deque。

??queue的使用

跟stack差不多這里就簡(jiǎn)單的使用一下

??queue的模擬實(shí)現(xiàn)

?stack可以使用vector實(shí)現(xiàn)，但是不能實(shí)現(xiàn)queue。vector的頭插頭刪需要挪動(dòng)數(shù)據(jù)效率會(huì)變低所以標(biāo)準(zhǔn)庫(kù)中沒(méi)有提供頭插頭刪的接口。queue就可以用list來(lái)模擬實(shí)現(xiàn)。

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優(yōu)點(diǎn)：尾插尾刪的效率高，支持隨機(jī)訪問(wèn)，cpu高速緩存命中率很高
缺點(diǎn)：空間不夠，增容代價(jià)大，一般增2倍，但增容后我只用了很少的一段空間那其他的空間就浪費(fèi)了。中間和頭部的插入刪除效率低O(N)，需要挪動(dòng)數(shù)據(jù)，
?list優(yōu)點(diǎn)：1.按需申請(qǐng)空間，不會(huì)造成空間浪費(fèi)
2.任意位置的插入刪除效率都高
缺點(diǎn)：不支持隨機(jī)訪問(wèn)， CPU高速緩存命中率低

改進(jìn)：用中控?cái)?shù)組-指針數(shù)組

這就是deque，雙端隊(duì)列和隊(duì)列沒(méi)有關(guān)系。在deque中，中控?cái)?shù)組叫map,開(kāi)的數(shù)組叫緩沖區(qū)。
deque(雙端隊(duì)列)：是一種雙開(kāi)口的"連續(xù)"空間的數(shù)據(jù)結(jié)構(gòu)，雙開(kāi)口的含義是：可以在頭尾兩端進(jìn)行插入和刪除操作，且時(shí)間復(fù)雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。

它不是正真連續(xù)的空間，底層結(jié)構(gòu)如上圖。deque要支持隨機(jī)訪問(wèn)叫要實(shí)現(xiàn)迭代器，它的迭代器很復(fù)雜簡(jiǎn)單了解。

這里就不多講解，感興趣的可以看侯捷老師的《stl源碼剖析》。

?deque卻沒(méi)有那么牛逼
優(yōu)缺點(diǎn)：
1.它最大優(yōu)點(diǎn)就是做stack和queue的默認(rèn)適配器，stack和queue只在頭尾操作，
2.它中間插入刪除還是要挪動(dòng)數(shù)據(jù)，很麻煩效率低
3.deque是糅合了vector和list，它沒(méi)有vector隨機(jī)訪問(wèn)效率高，任意位置的插入刪除效率沒(méi)有l(wèi)ist高。

?priority-queue

??priority-queue的使用

優(yōu)先級(jí)隊(duì)列默認(rèn)使用vector作為其底層存儲(chǔ)數(shù)據(jù)的容器，在vector上又使用了堆算法將vector中元素構(gòu)造成堆的結(jié)構(gòu)，因此priority_queue就是堆，所有需要用到堆的位置，都可以考慮使用priority_queue。注意：默認(rèn)情況下priority_queue是大堆。

    priority_queue<int> pq;//默認(rèn)是大堆	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;

?默認(rèn)是大的優(yōu)先級(jí)高，如果要變成小的優(yōu)先級(jí)高，需要再傳一個(gè)模板參數(shù)greater

??priority-queue的模擬實(shí)現(xiàn)

初始結(jié)構(gòu)，下面都是按大堆實(shí)現(xiàn)的

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

?首先實(shí)現(xiàn)尾插

當(dāng)插入一個(gè)數(shù)就和parent比較，比parent大就向上調(diào)整.
標(biāo)準(zhǔn)庫(kù)給的“<”是大堆，我們?cè)谀M的時(shí)候也用“<”.

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);			//從尾開(kāi)始調(diào)			AdjustUp(_con.size()-1);		}

?pop，如果直接pop就不能還保持是堆的結(jié)構(gòu)，先把堆頂?shù)臄?shù)和最后一個(gè)數(shù)交換在刪除這個(gè)數(shù)，此時(shí)2邊都還滿足堆這是在向下調(diào)整

先從0處開(kāi)始，選出左右2個(gè)孩子中大的和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);		}

?其他的接口就簡(jiǎn)單了

const T& top()const		{			return _con[0];//取堆頂?shù)臄?shù)據(jù)		}		size_t size()const		{			return _con.size();		}		bool empty()const		{			return _con.empty();		}

?測(cè)試一下

那如果要是按低的優(yōu)先級(jí)來(lái)該怎么辦呢？這是就要用到仿函數(shù)了。

?仿函數(shù)就是像函數(shù)一樣可以使用。

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

就是類里面重載了運(yùn)算符。有了仿函數(shù)就可以把上面的代碼在改進(jìn)改進(jìn)，在多傳一個(gè)模板參數(shù)

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);			//從尾開(kāi)始調(diào)			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];//取堆頂?shù)臄?shù)據(jù)		}		size_t size()const		{			return _con.size();		}		bool empty()const		{			return _con.empty();		}	private:		Container _con;	};}

?

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