目錄

一、容器適配器

deque原理

deque的缺陷

deque的優(yōu)勢(shì)

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

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

四、優(yōu)先級(jí)隊(duì)列的模擬實(shí)現(xiàn)

一、容器適配器

適配器是一種設(shè)計(jì)模式(設(shè)計(jì)模式是一套被反復(fù)使用的、多數(shù)人知曉的、經(jīng)過(guò)分類編目的、代碼設(shè)計(jì)經(jīng)驗(yàn)的總結(jié))，該種模式是將一個(gè)類的接口轉(zhuǎn)換成客戶希望的另外一個(gè)接口。

stack和queue中也可以存放元素，但在STL中并沒(méi)有將其劃分在容器的行列，而是將其稱為容器適配器，這是因?yàn)閟tack和queue只是對(duì)其他容器的接口進(jìn)行了包裝，STL中stack和queue默認(rèn)使用deque。

deque原理

deque(雙端隊(duì)列)：是一種雙開(kāi)口的"連續(xù)"空間的數(shù)據(jù)結(jié)構(gòu)，雙開(kāi)口的含義是：可以在頭尾兩端進(jìn)行插入和刪除操作，且時(shí)間復(fù)雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。
但是deque并不是真正連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成的，實(shí)際deque類似于一個(gè)動(dòng)態(tài)的二維數(shù)組。

deque的缺陷

與vector比較，deque的優(yōu)勢(shì)是：頭部插入和刪除時(shí)，不需要搬移元素，效率特別高，而且在擴(kuò)容時(shí)，也不需要搬移大量的元素，因此其效率是必vector高的。與list比較，其底層是連續(xù)空間，空間利用率比較高，不需要存儲(chǔ)額外字段。但是，deque有一個(gè)致命缺陷：不適合遍歷，因?yàn)樵诒闅v時(shí)，deque的迭代器要頻繁的去檢測(cè)其是否移動(dòng)到某段小空間的邊界，導(dǎo)致效率低下，而序列式場(chǎng)景中，可能需要經(jīng)常遍歷，因此在實(shí)際中，需要線性結(jié)構(gòu)時(shí)，大多數(shù)情況下優(yōu)先考慮vector和list，deque的應(yīng)用并不多，而目前能看到的一個(gè)應(yīng)用就是，STL用其作為stack和queue的底層數(shù)據(jù)結(jié)構(gòu)

deque的優(yōu)勢(shì)

stack是一種后進(jìn)先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，因此只要具有push_back()和pop_back()操作的線性結(jié)構(gòu)，都可以作為stack的底層容器，比如vector和list都可以；queue是先進(jìn)先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，只要具有push_back和pop_front操作的線性結(jié)構(gòu)，都可以作為queue的底層容器，比如list。但是STL中對(duì)stack和queue默認(rèn)選擇deque作為其底層容器，主要是因?yàn)椋?br> 1. stack和queue不需要遍歷(因此stack和queue沒(méi)有迭代器)，只需要在固定的一端或者兩端進(jìn)行操作。
2. 在stack中元素增長(zhǎng)時(shí)，deque比vector的效率高(擴(kuò)容時(shí)不需要搬移大量數(shù)據(jù))；queue中的元素增長(zhǎng)時(shí)，deque不僅效率高，而且內(nèi)存使用率高。
結(jié)合了deque的優(yōu)點(diǎn)，而完美的避開(kāi)了其缺陷。
dqque結(jié)論：
1.頭尾的插入刪除非常合適，相比vector和list而言，很適合去做stack和queue的默認(rèn)適配容器
2.中間插入刪除多用list
3.隨機(jī)訪問(wèn)多用vector

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

用deque做適配器

	template<class T, class container=deque<T>>
	//一般情況下默認(rèn)容器為deque適配
	//queue也是一樣
	//deque優(yōu)點(diǎn)：頭尾插刪隨機(jī)訪問(wèn)都行；
	//缺陷：operator[]計(jì)算稍顯復(fù)雜大量使用性能下降
	//中間插入刪除效率不高
	//底層角度迭代器會(huì)很復(fù)雜

template<class T, class container=deque<T>>class stack {
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

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

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

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

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

		size_t size() const
		{
			return _con.size();
		}
	private:
		container _con;
		//vector<T> _con;
	};

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

與stack一樣，采用deque做適配器文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-432083.html

	template<class T, class container = deque<T>>
	//適配器不能用vector因?yàn)椴恢С诸^插刪 	
	class queue {
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

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

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

		T& front()
		{
			return _con.front();
		}

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

		const T& front() const
		{
			return _con.front();
		}

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

		size_t size() const
		{
			return _con.size();
		}
	private:
		container _con;
	};

四、優(yōu)先級(jí)隊(duì)列的模擬實(shí)現(xiàn)

template<class T, class container = vector<T>>
	class priority_queue {
	public :
		//類似于堆

		priority_queue()
		{}
		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}
			//建堆
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			{
				adjust_down(i);
			}
		}
		


		void adjust_up(size_t child)
		{
			//向上調(diào)//O(lgN)
			size_t parent = (child - 1) / 2;
			while (child>0)
			{
				if (_con[child] > _con[parent])
				{
					std::swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
					break;
			}
		}
		void push(const T& x)
		{//向上調(diào)整
			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}

		void adjust_down(size_t parent)
		{
			//向下調(diào)整
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && _con[child + 1] > _con[child])
				{
					child++;
				}

				if (_con[child] > _con[parent])
				{
					std::swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					break;
			}
		}
		void pop()
		{
			//向下調(diào)整
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();

			adjust_down(0);
		}

		const T& top()
		{
			return _con[0];
		}

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

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

	private:
		vector<T> _con;
	};

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