1.容器適配器

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

比如說我們?nèi)粘Ｉ钪杏玫某潆娖?，就是一種電源適配器，本質(zhì)就是對電流電壓 轉(zhuǎn)換成我們需要的大小。

2. stack模擬實(shí)現(xiàn)

stack滿足只能在一端插入和刪除就行，我們的底層用vector的話可以滿足這個(gè)條件，底層用list同樣也可以滿足這個(gè)條件。

既然如此，我們就不需要原生實(shí)現(xiàn)棧，直接用vector或者list封裝轉(zhuǎn)換一下不就好了。

如果是用vector實(shí)現(xiàn)棧，就是數(shù)組棧，用list實(shí)現(xiàn)棧，就是鏈?zhǔn)綏！?/p>

2.1 準(zhǔn)備工作

我們把棧的所有實(shí)現(xiàn)都放在stack.h里，在test.cpp里測試。

在stack.h里，包含會(huì)用到的頭文件，用命名空間namespace與庫里面的stack分隔開。

#pragma once
#include <iostream>
#include <list>
#include <vector>
using namespace std;
 
namespace lyj
{
 
}

在namespace里用模板。

namespace lyj
{
	template<class T, class Container>
	class stack
	{
	private:
		Container _con;
	};
}

第一個(gè)模板參數(shù)T是棧要存的數(shù)據(jù)類型，第二個(gè)模板參數(shù)Container是底層實(shí)現(xiàn)的類型，用Container適配轉(zhuǎn)換出stack，傳vector就封裝vector實(shí)現(xiàn)，傳list就封裝list實(shí)現(xiàn)。

2.2 棧的接口實(shí)現(xiàn)

構(gòu)造函數(shù)我們不用寫，因?yàn)開con肯定是自定義結(jié)構(gòu)，所以會(huì)調(diào)用自己的構(gòu)造函數(shù)。

我們把尾當(dāng)作棧頂。

namespace lyj
{
	template<class T, class Container>
	class stack
	{
	public:
		void push(const T& x) //插入
		{
			_con.push_back(x);
		}
		void pop() //刪除
		{
			_con.pop_back();
		}
 
		const T& top() const //獲取棧頂元素
		{
			return _con.back();
		}
 
		size_t size() const //獲取有效個(gè)數(shù)
		{
			return _con.size();
		}
 
		bool empty() const //判空
		{
			return _con.empty();
		}
 
	private:
		Container _con;
	};
}

就非常方便簡潔。

在test.cpp中使用一下我們寫的這個(gè)stack。記得包含頭文件#include "stack"

#include "stack.h"
void test1()
{
	lyj::stack<int, vector<int>> st;//注意參數(shù)
	st.push(1);
	st.push(2);
	st.push(3);
}
int main()
{
	test1();
	return 0;
}

上面顯示就是底層是vector的棧，數(shù)組棧，然后我們插入了一些數(shù)據(jù)。

我們再演示一下底層是list的棧，鏈?zhǔn)綏?，只需要把第二個(gè)參數(shù)換成list<int>就行。

void test2()
{
	lyj::stack<int, list<int>> st;
	st.push(1);
	st.push(2);
	st.push(3);
}

此時(shí)，棧的底層發(fā)生了巨大的變化，我們可以把數(shù)據(jù)存在vector實(shí)現(xiàn)的棧里面，也可以存在list實(shí)現(xiàn)的棧里面。

我們也可以給第二個(gè)參數(shù)Container給缺省值。

template<class T, class Container = vector<T>>

3.queue模擬實(shí)現(xiàn)

queue要滿足在一端插入，在另一端刪除，我們的底層用list的話可以滿足這個(gè)條件，但是此時(shí)vector就不滿足這個(gè)條件了。那我們先用list封裝轉(zhuǎn)換一下。

3.1 準(zhǔn)備工作

我們把隊(duì)列的所有實(shí)現(xiàn)都放在queue.h里，在原來的test.cpp里測試。

在queue.h里用命名空間namespace與庫里面的queue分隔開，這個(gè)命名空間名字和棧取一樣的。

namespace lyj
{
	template<class T, class Container = list<T>>
	class queue
	{
	public:
 
	private:
		Container _con;
	};
}

第一個(gè)模板參數(shù)T是棧要存的數(shù)據(jù)類型，第二個(gè)模板參數(shù)Container是底層實(shí)現(xiàn)的類型，這里Container缺省值給list<T>。

3.2 隊(duì)列的接口實(shí)現(xiàn)

構(gòu)造函數(shù)我們還是不用寫，因?yàn)開con肯定是自定義結(jié)構(gòu)，所以會(huì)調(diào)用自己的構(gòu)造函數(shù)。

queue的代碼和stack大差不差，只是把pop部分變成_con里的頭刪。

template<class T, class Container = list<T>>
class queue
{
public:
	void push(const T& x) //隊(duì)尾插入
	{
		_con.push_back(x);
	}
	void pop() //隊(duì)頭刪除
	{
		_con.pop_front();
	}
 
	const T& top() const //獲取隊(duì)尾元素
	{
		return _con.back();
	}
 
    const T& front() const //獲取隊(duì)頭元素
    {
        return _con.front();
    }
    
	size_t size() const //獲取有效個(gè)數(shù)
	{
		return _con.size();
	}
 
	bool empty() const //判空
	{
		return _con.empty();
	}
private:
	Container _con;
};

在test.cpp中使用一下我們寫的這個(gè)queue。記得包含頭文件#include "squeue"

void test3()
{
	lyj::queue<int, list<int>> q;
	q.push(1);
	q.push(2);
	q.push(3);
}

 看著沒啥問題。

但是我們給Container傳vector類型時(shí)，這個(gè)測試代碼居然也可以。

void test3(){lyj::queue<int, vector<int>> q;q.push(1);q.push(2);q.push(3);}

vector按理來說不能實(shí)現(xiàn)queue，在實(shí)現(xiàn)queue的pop部分，vector也沒有pop_front（頭刪）這個(gè)接口。代碼為什么沒報(bào)錯(cuò)？

這里就要補(bǔ)充一個(gè)知識(shí)，按需實(shí)例化。

3.3 按需實(shí)例化

我們前面的測試代碼并沒有調(diào)用pop這個(gè)接口，當(dāng)我們調(diào)用pop這個(gè)接口時(shí)，就會(huì)立馬報(bào)錯(cuò)。

void test3()
{
	lyj::queue<int, vector<int>> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.pop(); //調(diào)用pop
}

這是因?yàn)?，類在?shí)例化的時(shí)候，不會(huì)實(shí)例化所有的成員函數(shù)，我們用哪些函數(shù)，就實(shí)例化哪些。

前面沒報(bào)錯(cuò)，因?yàn)槲覀兏緵]有調(diào)用pop這個(gè)成員函數(shù)，可以理解為沒有觸發(fā)到這個(gè)錯(cuò)誤。

編譯器對模板檢查的時(shí)候，只會(huì)檢查一個(gè)大概，明顯的語法錯(cuò)誤能檢查出來，但是不會(huì)檢查細(xì)節(jié)，比如說我們在這里調(diào)錯(cuò)了函數(shù)，用到這個(gè)接口時(shí)，才會(huì)報(bào)錯(cuò)。

所以，在類模板實(shí)例化時(shí)，只會(huì)實(shí)例化用到的函數(shù)，這就是按需實(shí)例化。

4.deque

4.1 STL標(biāo)準(zhǔn)庫中stack和queue的底層結(jié)構(gòu)

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

4.2 deque的簡單介紹

文檔介紹：deque - C++ Reference

我們看deque的成員函數(shù)，會(huì)發(fā)現(xiàn)deque有點(diǎn)像vector和list的結(jié)合。

vector支持[]，但是vector不直接支持頭刪尾刪。

list支持各種位置插入刪除，但是不支持[]。 

既然說到這里了，我們也順便說一下vector和list各自的優(yōu)缺點(diǎn)

4.2.1 vector和list各自的優(yōu)缺點(diǎn)

vector：

優(yōu)點(diǎn)：1.尾插尾刪的效率還不錯(cuò)，并且支持高效的下標(biāo)隨機(jī)訪問。

           2.物理空間連續(xù)，所以高速緩存利用率高。

缺點(diǎn)：1.空間需要擴(kuò)容，擴(kuò)容會(huì)帶來效率問題和空間的浪費(fèi)。

           2.頭部和中間部分的插入刪除操作效率低。

list：

優(yōu)點(diǎn)：1.按需申請釋放空間，不需要擴(kuò)容。

           2.可以在任意位置插入刪除。

缺點(diǎn)：不支持下標(biāo)隨機(jī)訪問。 

4.2.2 deque的優(yōu)缺點(diǎn)

deque的具體底層原理在這里就不詳細(xì)說明了，有興趣的可以去查閱資料。我們直接來說一下deque的優(yōu)缺點(diǎn)。

deque：

優(yōu)點(diǎn)：

1.可以在頭尾兩端進(jìn)行插入和刪除操作，且時(shí)間復(fù)雜度為O(1)。

2.與vector比較，頭插效率高，不需要搬移元素。

3.與list比較，空間利用率比較高。

缺點(diǎn)：

不適合遍歷，因?yàn)樵诒闅v時(shí)，deque的迭代器要頻繁的去檢測其是否移動(dòng)到某段小空間的邊界，導(dǎo)致效率低下，而序列式場景中，可能需要經(jīng)常遍歷，因此在實(shí)際中，需要線性結(jié)時(shí)，大多數(shù)情況下優(yōu)先考慮vector和list，deque的應(yīng)用并不多，而目前能看 到的一個(gè)應(yīng)用就是，STL用其作為stack和queue的底層數(shù)據(jù)結(jié)構(gòu)。

4.2.3 選deque做棧和隊(duì)列的底層默認(rèn)容器的原因

1. stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進(jìn)行操作。

2. 在 stack 中元素增長時(shí)， deque 比 vector 的效率高 ( 擴(kuò)容時(shí)不需要搬移大量數(shù)據(jù) ) ； queue 中的元素增長時(shí)，deque 不僅效率高，而且內(nèi)存使用率高。

結(jié)合了 deque 的優(yōu)點(diǎn)，而完美的避開了其缺陷。

5. STL標(biāo)準(zhǔn)庫中對于stack和queue的模擬實(shí)現(xiàn)

使用deque時(shí)要包含頭文件#include <deque>

5.1 stack

代碼和原來一樣，只是缺省參數(shù)換成deque<T>。

#include <iostream>
#include <list>
#include <vector>
#include <deque>
using namespace std;
namespace lyj
{
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& x) //插入
		{
			_con.push_back(x);
		}
		void pop() //刪除
		{
			_con.pop_back();
		}
 
		const T& top() const //獲取棧頂元素
		{
			return _con.back();
		}
 
		size_t size() const //獲取有效個(gè)數(shù)
		{
			return _con.size();
		}
 
		bool empty() const //判空
		{
			return _con.empty();
		}
 
	private:
		Container _con;
	};
}

在test.cpp里測試一下。

void test4()
{
	lyj::stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl;
}

5.2 queue

代碼和原來一樣，也是缺省參數(shù)換成deque<T>。

#include <iostream>
#include <list>
#include <vector>
#include <deque>
using namespace std;
namespace lyj
{
	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& x) //隊(duì)尾插入
		{
			_con.push_back(x);
		}
 
		void pop() //隊(duì)頭刪除
		{
			_con.pop_front();
		}
 
		const T& top() const //獲取隊(duì)尾元素
		{
			return _con.back();
		}
 
		const T& front() const //獲取隊(duì)頭元素
		{
			return _con.front();
		}
 
		size_t size() const //獲取有效個(gè)數(shù)
		{
			return _con.size();
		}
 
		bool empty() const //判空
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

在test.cpp里測試一下。

void test5()
{
	lyj::queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;
}

以上就是C++使用適配器模式模擬實(shí)現(xiàn)棧和隊(duì)列的詳細(xì)內(nèi)容，更多關(guān)于C++實(shí)現(xiàn)棧和隊(duì)列的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論