c++中容器擴充卡

什麼是容器擴充卡

擴充卡是一種設計模式(設計模式是一套被反複使用的、多數人知曉的、經過分類編目的、代碼設計經驗的總結)，該中模式是将一個類的接口轉換成客戶希望的另外一個接口。

stack模拟封裝

template<class T,class Container = deque<T>>
	class stack
	{
	public:
		stack()
		{}

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

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

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

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

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

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

queue模拟封裝

template<class T , class Container = deque<T>>
	class queue
	{
	public:
		queue()
		{}

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

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

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

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

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

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

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

		bool empty()const
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
           

• 每種容器都提供了一組接口，如果容器中的接口不能滿足需求，那麼重新編寫容器還是改變我們的需求
• 應該構造一個容器接口到需求接口之間的轉換器，稱為容器擴充卡。
• 容器擴充卡将原容器進行了一層封裝，底層基于普通容器，上層對外提供封裝後的新接口，滿足不同使用者的需求。常用的棧stack、隊列deque、優先級隊列priority_queue在STL中都有自己的容器擴充卡。
• 容器擴充卡對使用者是個黑盒，使用者無需知道容器擴充卡封裝的容器類型，而隻需了解容器擴充卡提供的接口。除了使用STL提供的容器擴充卡，也可以自己構造容器擴充卡，将STL中的容器進行封裝，對外提供所需的接口。
• 容器擴充卡可以封裝的容器類型根據容器擴充卡對外提供的接口和容器擴充卡的内部算法而定。但是任何容器擴充卡對底層容器都有一些通用的要求，例如，底層容器必須支援添加删除 和通路尾元素操作，是以array不能作為容器擴充卡的底層容器。
• 棧擴充卡和隊列擴充卡預設的底層容器是deque，優先隊列擴充卡預設的底層容器是vector。在建立容器擴充卡的對象時，也可以指定其他合理的容器作為容器擴充卡的底層容器。建立容器擴充卡對象的方式如下

棧：

stack<int> s;//預設使用deque

stack<int,vector<int>> s;//指定使用vector
           

隊列：

queue<int> q;//預設使用deque

queue<int,lise<int>> q；//指定使用list

優先隊列：

priority_queue<int> p;//預設使用vector

priority_queue<int,deque<int>> p;//指定使用deque

priority_queue<int,vector<int>,cmp>> p;//指定使用vector和權重比較函數cmp
           

注意事項

容器擴充卡和底層容器是組合的關系，插入容器擴充卡中的元素最終都儲存在底層容器中，容器擴充卡中的資料成員包括一個用于存儲元素的底層容器對象和一些輔助資料。

為什麼選擇deque作為stack和queue的底層預設容器

stack是一種後進先出的特殊線性資料結構，是以隻要具有push_back()和pop_back()操作的線性結構，都可 以作為stack的底層容器，比如vector和list都可以；queue是先進先出的特殊線性資料結構，隻要具有 push_back和pop_front操作的線性結構，都可以作為queue的底層容器，比如list。但是STL中對stack和 queue預設選擇deque作為其底層容器，主要是因為：

1. stack和queue不需要周遊(是以stack和queue沒有疊代器)，隻需要在固定的一端或者兩端進行操作。
2. 在stack中元素增長時，deque比vector的效率高；queue中的元素增長時，deque不僅效率高，而且内 存使用率高。