個(gè)人主頁：??在肯德基吃麻辣燙
分享一句喜歡的話：熱烈的火焰，冰封在最沉默的火山深處。

前言

本文章主要介紹容器適配器的功能，以及一個(gè)適配的場(chǎng)景。

一、什么是容器適配器？

容器適配器，按字面意思理解的話，就是用來對(duì)一個(gè)容器進(jìn)行匹配的。在C++STL中，容器有：vector，list，deque，map，set等。

而在C++STL中不把stack和queue納入容器的范圍而是納入容器適配器的范圍是因?yàn)椋?/p>

stack和queue沒有下標(biāo)隨機(jī)訪問等操作，只有普通的pop_front,push_back,pop_back()等操作，而這些函數(shù)在其他容器中完全可以有，棧和隊(duì)列的實(shí)現(xiàn)完全可以將其他容器的操作進(jìn)行復(fù)用，這就是stack和queue作為容器適配器的原因。
至于為什么用deque（雙端隊(duì)列）作為stack和queue的默認(rèn)適配容器，先看一看stack和queue的基本函數(shù)使用。

二、stack的基本函數(shù)和模擬實(shí)現(xiàn)

可以看到在stl庫(kù)開放的棧的接口中，僅有寥寥無幾的幾個(gè)接口，主要為：push，pop，size，empty，top。

由于棧的后進(jìn)先出的特性，

• 1.push是往棧頂進(jìn)行push元素。
• 2.pop是刪除棧頂元素。
• 3.size是計(jì)算當(dāng)前的棧有多少元素
• 4.empty是判斷棧是否為空
• 5.top是取棧頂元素

這幾個(gè)函數(shù)完全可以復(fù)用其他容器的函數(shù)。
所以棧其實(shí)可以用vector，list等容器進(jìn)行適配。

下面來模擬實(shí)現(xiàn)：

namespace dzt
{
	template<class T, class container = deque<T> >
	class stack
	{
	public:

		void push(const T& x)
		{
			_con.push_back(x);
		}

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

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

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

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


	private:
		container _con;
	};
}

為了和庫(kù)里面的stack不沖突，這里給了一個(gè)命名空間域dzt作為限定。

三、queue的基本函數(shù)和模擬實(shí)現(xiàn)

與stack類似，主要的函數(shù)有：
push，pop，front，back，size，empty。
由于隊(duì)列先進(jìn)先出的特性

• 1.push，向隊(duì)列尾部插入元素
• 2.pop，刪除隊(duì)頭元素
• 3.front，取隊(duì)頭元素
• 4.back，取隊(duì)尾元素
• 5.size，計(jì)算當(dāng)前隊(duì)列的元素個(gè)數(shù)
• 6.empty，判斷當(dāng)前隊(duì)列是否為空

下面來模擬實(shí)現(xiàn)queue

namespace dzt
{

	template<class T, class container = deque<T> >
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.insert(_con.end(),x);
		}
		void pop()
		{
			_con.erase(_con.begin());
		}

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

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

		//取隊(duì)頭
		T& front()
		{
			return _con.front();
		}
		
		//取隊(duì)尾
		T& back()
		{
			return _con.back();
		}
	private:
		container _con;
	};
}

四、deque

4.1deque的底層結(jié)構(gòu)

deque(雙端隊(duì)列)：是一種雙開口的"連續(xù)"空間的數(shù)據(jù)結(jié)構(gòu)，雙開口的含義是：可以在頭尾兩端進(jìn)行插入和刪除操作，且時(shí)間復(fù)雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。

deque并不是真正連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成的，實(shí)際deque類似于一個(gè)動(dòng)態(tài)的二維數(shù)組

deque的底層結(jié)構(gòu)如下：

• 1.使用一個(gè)中控指針數(shù)組來存儲(chǔ)各個(gè)位置的指針，而存儲(chǔ)的位置一般只在數(shù)組的中間部分，大多數(shù)指針指向的內(nèi)容都是一小塊連續(xù)的空間，并且這些連續(xù)的空間的大小都是一樣的。
• • start(iterator)記錄頭部數(shù)據(jù)，finish(iterator)記錄尾部數(shù)據(jù)，頭尾的插入刪除效率非常高，O(1)。

• cur記錄指向的連續(xù)空間的第一個(gè)位置，first和last是該空間的區(qū)間，node反指回中控?cái)?shù)組，方便找到下一個(gè)連續(xù)空間。

但是deque也有缺點(diǎn)，雖然它重載了[]訪問，但是在訪問中間元素時(shí)不夠極致，需要進(jìn)行計(jì)算。假設(shè)給定的下標(biāo)為i，計(jì)算過程如下：

• 1.i如果在第一個(gè)數(shù)組的范圍，直接訪問
• 2.如果不在，i-=第一個(gè)數(shù)組的size
• i/buffersize = 第i個(gè)數(shù)組的位置
• 此時(shí)i指向了第i個(gè)數(shù)組，再用i/buffersize = 第i個(gè)位置的元素。

相比于vector，deque的下標(biāo)訪問的效率不夠高，
相比于list，deque的中間位置插入刪除效率不夠高。

4.2使用deque適配stack和queue的原因

• deque作為棧和隊(duì)列的容器適配器而不是用vector/list的優(yōu)點(diǎn)：
• 1.deque的底層結(jié)構(gòu)是使用中控指針數(shù)組來存儲(chǔ)頭和尾等各個(gè)空間的地址，對(duì)頭尾的插入刪除效率極高O(1)
• 2.棧就需要push_back()和pop_back(),隊(duì)列需要支持pop_front()和push_back() ——— 戰(zhàn)勝了vector
• 3.每一小塊空間都是連續(xù)的，可以提高cpu高速緩存加載的效率。 ————戰(zhàn)勝了list
• 4.stack和queue都不需要[]隨機(jī)訪問，而deque的缺陷就是下標(biāo)隨機(jī)訪問的效率不夠高
• 5.這樣棧和隊(duì)列的需求完美迎合了deque的優(yōu)點(diǎn)，避開了deque的缺點(diǎn)

總結(jié)

本篇文章簡(jiǎn)單講述了deque容器的底層原理以及相比于vector和list的缺點(diǎn)，還有用deque作為stack和queue的適配器的原因。文章來源地址http://www.zghlxwxcb.cn/news/detail-602979.html

到了這里，關(guān)于【C++】STL之容器適配器——使用deque適配stack和queue的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！