泛型程式設計與STL(三):容器

一.何為容器

二.為什麼容器

三.如何使用容器

四.深入容器

一.何為容器

       在STL中。算法，疊代器，容器是三個緊密聯系的元件。容器提供儲存資料的地方，疊代器提供對容器通路操作的通用接口，而算法利用疊代器通路資料提供對資料的操作。容器作為資料的存儲元件，同時也為存儲的資料提供了通路，修改操作的接口。而STL為它的容器規定了一組通用接口的規範，這使得STL的容器的接口具有了一緻性。例如vector,list它們都有push_back方法，雖然它們的實作方法不同，但是push_back的作用确是相同的。

1.1 容器的concept.

       要了解各類STL容器的特點，就必須先了解STL是怎麼定義各類容器的concept的。concept是一組requirement的集合，而STL的容器都會是滿足一個或多個concept的model，是以了解了各類concept的requirement就了解了容器的特點。        容器的concept有一定的層次結構，大緻結構如下所示，其中箭頭表示兩個concept之間的refine關系：

       container這個concept是容器最基本的concept，其他所有的concept都是這個concept的refine。        其中 中間這條主線的concept主要根據container所能提供的iterator來定義的。foward container的要求是容器能夠提供forward iterator，reversible container要求容器能夠提供bidredirection iterator............        sequence container 與 associate container 這兩個concept的 主要差別在于： sequence container将單一類型元素聚集起來，然後根據位置來存儲通路。順序容器的元素排列次序與元素值無關，而是由元素添加到容器裡的次序決定。associate contaqiner中的每個元素都有一個對應的鍵值，容器通過鍵值來存儲和讀取元素，元素在容器中的位置與元素對應的鍵值有關。         sequence container：sequence container中又精煉出了兩個concept及front insert container與back insert container，這兩個concept要求能夠提供在最前端，最末尾處通路，删除，插入的接口。這兩個refine的concept并不是互斥的，如deque及是front insert container的model，又是back insert container的model。而vector隻是back insert container的model。        associate container：associate container中有三組refine的concept，并且每組内的concept是互斥的。 simple associate container 與pair associate container互斥，simple associate container要求元素以自身的值為鍵值，而pari associate container則要求為元素提供一個額外的鍵值。set就是一個simple associate container，而map則相反。 unique associate container與multiple associate container互斥，unique associate container要求存儲的鍵值隻有一個唯一的元素對應，有multiple associate container則允許一個鍵值可以對應多個元素。如map，sort是unique associate container，而multiset multimap則是multiple associate container。 sorted associate container與hashed associate container互斥，sorted associate container 按照鍵值的比較結果排序組織元素（想象二叉搜尋樹等結構，這與它們的存儲方式類似），而hashed associate container則按照鍵值的hash table來組織元素。unordered_map是hashed associate container而map則是sorted associate container。最後總結下set是simple associate container ,unique associate container,sorted associate container的model。multimap是pair associate container，multiple associate container與sorted associate container的model。

1.2.容器容納的元素

       容器對元素的存儲有兩點必須的掌握：        1. 容器對元素的存儲是基于值語義的，而不是基于指針語義。這句話的意思是當我們傳入一個值給容器存儲時，容器會拷貝一份該元素的副本，而不是存儲一個該元素的指針或者引用在容器内。也就是說傳入一個值給容器容器會先締造一份該元素的拷貝然後将拷貝存入容器。（即使我們存入的資料類型是指針，容器也會拷貝一份指針的副本存儲）        2 .容器存儲的元素的生命周期是不會超過容器本身的。當容器銷毀時，容器内的指針也會被銷毀掉。是以當你存儲的是指針的時候要小心了，你必須在容器銷毀之前把指針的值取出來然後銷毀指針指向的對象，因為指針容器隻會銷毀指針本身，而不是指針指向的對象。        3. 容器一般都會使用預設的記憶體配置設定器，這點你不用擔心，但是如果你想使用自己的記憶體管理器也可以進行定制然後通過模闆參數傳給容器。但是預設的記憶體配置設定器的特點造就了容器不支援多态。或許這麼說不太好，舉個例子，如果有兩個類A與B，B繼承A，然後當你有一個類B的對象，将其存入類A的容器内，那麼将其取出的時候你會發現這個對象屬于B的部分已經被切除了。

二.為什麼容器

             為什麼使用STL容器，主要有一下幾點：        1.使用STL容器讓你免于反複造輪子，一些得到多年檢驗的元件将為你提供高質的服務。你不用自己在去寫什麼動态數組，連結清單，紅黑樹什麼的了。        2.使用STL容器可以享受配套的iterator與算法。買一送二何樂不為。        3.STL容器當然是跨平台的支援。

三.如何使用容器

 3.1STL容器對存儲元素的要求

       在使用STL容器存儲元素之前你得先明白，STL容器對于被存儲的元素都有哪些要求，以及它為這些元素提供哪些保障。 容器對這種元素提供的功能除了受限于容器本身提供的接口外，還受限與元素本身提供的特性。理論來說一個什麼操作都不支援的元素也可以使用容器，隻是容器對這種元素幾乎不提供任何接口而已。看下面例子：

class TestA
{
//我們屏蔽了預設提供的内置方法
private:
	TestA&  operator=(const TestA &b);
	TestA(const TestA& b);
	TestA();
	~TestA();
	TestA& operator*();
	const TestA& operator*() const;

};
int main(int argc,char* argv[])
{
//之是以用new而且不delete,是不讓vector<TestA>的析構函數不被執行個體化
	vector<TestA>* a=new vector<TestA>();
}
           

這個程式能編譯通過，也能運作。為什麼？主要是因為我們除了使用了vector的預設構造函數之外，沒有使用vector的任何函數，是以我們提供的元素本身也不需要提供任何額外的功能。 template member function隻有在我們調用了它之後它才會在編譯時執行個體化（雖然不夠準确，但是重點不在這裡），這裡我們隻是調用了vector預設構造函數，而它對元素本身沒有任何要求是以能通過編譯。但是如果我們調用了vector其他的member function 比如push_back，這時候編譯時push_back會執行個體化，push_back執行個體化之後編譯器便會對push_back型别推導，這時候因為我們的元素沒有提供任何push_back要求的功能，是以型别推導會失敗。        上述例子隻是為了說明，STL容器能提供使用的接口并不是預設所有都可以使用的，隻有當我們提供的存儲元素滿足了某些條件之後我們才能使用STL容器的相應功能。        總的來說對于sequence container容器我們需要提供以下的三個方法才能“正常”的使用，copy construction,copy assignment以及析構函數。而要使用如下面這種功能我們則需要提供一個預設構造函數。

vector<Foo> ok(10);//在容器内以預設構造函數構造10個Foo對象
           

       而對于associate container容器元素我們除了要提供sequence container所需要的三個方法之外，我們還需要讓associate 元素的鍵值有一個相關比較函數。預設情況下associate container會為我們生成一個STL預置的less<T>函數對象，像下面這樣：

template < class T,                       
           class Compare = less<T>,        // 如果我們自己不提供key的函數比較對象,則STL為我們提供一個，并在内部調用key的<進行比較
           class Alloc = allocator<T> >    
           > class set
           

less<T>這個函數對象會被container調用來比較我們的兩個鍵值大小，less<T>内部預設使用的鍵值的<符号進行比較。我們隻要為元素的鍵值提供<操作就可以使用associate container的預設的less<T>函數對象進行比較。或者我們也可以提供一個我們自己的函數對象，對key進行比較。注意這裡提供的函數對象必須是Predicate binary function object的model(提供兩個傳入參數，傳回結果是bool型别的函數對象)。 嚴格若排序       associate container 元素的鍵值之間的比較必須滿足 嚴格若排序。這個概念簡單的了解就是滿足下面這個的條件：        1.X<X始終不成立.        2.不可能X<Y成立 而Y<X也成立.        3.X<Y，Y<Z，則X<Z

照例舉個例子吧，假設我有一個類A有兩個變量value1,value2。我想以value1的順序進行排序，如果兩個對象的value1相等則用value2進行排序。當我們改寫<的時候我們就應該這麼做

//編譯器預設為我們提供的copy assignment與copy construction足夠了
//如果你的value不是内置的型别你應該小心的對待他們的拷貝動作。
class A
{
public:
	A(int var1,int var2):value1_(var1),value2_(var2){}
	int value1_;
	int value2_;
	bool operator<(const A& a) const
	{
		//value1的值相等我們用value2的值來比較
		if(value1_!=a.value1_)
			return value1_<a.value1_;
		else
			return value2_<a.value2_;
	}

};
int main(int argc,char* argv[])
{
	set<A> seta;
	seta.insert(A(2,9));
	seta.insert(A(2,1));
	seta.insert(A(3,2));
	seta.insert(A(1,1));
	seta.insert(A(1,2));
	seta.insert(A(2,3));
	for(set<A>::iterator it=seta.begin();it!=seta.end();it++)
	{
		printf("%d,%d\n",it->value1_,it->value2_);
	}
}
           

輸出結果： 1，1 1，2 2，1 2，3 2，9 3，2

3.2 容器擴充卡

       目前STL提供了三種針對sequence container的擴充卡，分别是stack,queue,priority_queue。下面是三種擴充卡對被适配的底層容器的要求： stack：

• back()
• push_back()
• pop_back()

queue：

• front()
• back()
• push_back()
• pop_front()

priority_queue：

• front()
• push_back()
• pop_back()
• random_access concept的container

在STL容器中滿足所有的sequence container都能滿足stack的要求，而隻有list,dequeue可以滿足queue的要求，vector，deque則可以滿足priority_queue的要求。               在沒有沒有提供适配容器的情況下調用這些adaptor的話它們會選用預設的container進行适配，stack預設選擇的deque作為其适配容器，queue預設選擇也選擇deque,而priority_queue則預設選擇了vector。以下是這些擴充卡的聲明：

template < class T, class Container = vector<T>,
           class Compare = less<typename Container::value_type> > class priority_queue;

template < class T, class Container = deque<T> > class queue;

template < class T, class Container = deque<T> > class stack;
           

不得不提到的一點是priority_queue中元素的優先級比較預設是使用的預制的binary predicate function的model“less<T>”來進行的，而這個function object預設則會使用元素的"<"符号進行比較是以，我們需要為存儲在priority_queue中的提供"<"比較符，如果我們希望使用預設的function object的話。同樣的提供的"<"也必須滿足strict weak ordering。

四：深入容器

這個主題留待下節吧