歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

C++ STL相關容器詳解

vector:

一種隨機訪問的數組類型,他提供了對數組元素的快速、隨機訪問,以及在序列尾部快速、隨機的插入和刪除操作。它在需要時可以改變其大小,也就是說大小可變的向量,比較靈活。可取代C++語言本身提供的傳統數組。提供隨機存儲能力。操作尾端元素的速度最快。由於所有元素占用連續空間,所以一旦進行插入或者刪除動作,有可能使原本的某些 iterators失效。

list:

這是一個雙向鏈表容器,完成了標准的C++數據結構中鏈表的所有功能。它不支持隨機訪問的數組類型,因為STL以雙向鏈表的方式實現list對象,所以訪問鏈表元素要指針從鏈表的某個端點開始。插入和刪除操作所花的時間是固定的,也就是說,list對象插入和刪除一個元素所需要的時間與該元素在鏈表中的位置無關。在任何位置做插入和刪除動作都很快,不像vector只局限於尾端,而deque只局限於兩端才有高效率。由於各元素並不占用連續空間,所以一旦進行插入或者刪除動作,原本的iterators任然有效。注意,許多只在元素搬移的STL algorithms用於list身上會有不佳的效率。幸好這些STL algorithms 都有對應的list member functions 可以替代。後者之所以會有比較好的效率,原因是他們只操作指標,而非真正去拷貝或者移動元素。

queue:

這是一種隊列容器,它采用deque和list對象創建一個先進先出(FIFO)的容器,它實際上完成了標准的C++數據結構中的隊列所有功能。不提供隨機存儲能力。行為與特性都很類似vector,但因為是雙向開口,所以操作兩端元素的速度都很快,不像vectoer只在操作尾端元素時才有高效率。由於所有元素占用連續空間,所以一旦進行插入或者刪除動作,有可能是原本的某些iterators失效。

stack:

這是一種棧容器,完成了標准的C++數據結構中棧的所有功能。也就是說,它通過vector、deque或者list對象創建了一個先進後出的容器。stack特性是先進後出(FILO: First In, Last Out)。

deque:

這是一種隨機訪問的數據類型,提供了在序列兩端快速插入和刪除操作的功能,他可以再需要的時候修改器自身大小。也就是說這是一種雙端隊列容器,完成了標准的C++數據結構中隊列的所有功能。queue特性是先進先出。

priority_queue:

這是一種按值排序的隊列容器。它使用vector或者deque對象創建了一個排序隊列。priority_queue特性是依優先權來誰是下一個元素。

set:

這是一種隨機存取的集合容器。其關鍵詞和數據元素是同一個值,也就是說它不能包含重復的元素。set經過排序的結構體,以某個可指定的排序方式排序,每個元素第一無二。由於已經排序,所以搜尋速度極快。但也因此不允許我們直接修改某個元素的內容,因為這可能會影響排序。修改元素內容的正確的作法是,先將該元素刪除,再加入(此時使用新值)。set通常是以平衡二叉樹(balanced binary tree)來存儲(但並不是強制規定),甚至是以red-black trees來完成。

multiset:

其關鍵詞和數據元素也是同一個值,但和set不同的以及最大的區別在於這是一種允許出現重復元素的集合容器。multiset允許元素重復。

map:

其是一種關聯數組容器,它包含成對數據的容器,其中一個值是實際數據值,另外一個是用來尋找數據的關鍵值,一個特定的關鍵詞只能與一個元素相關聯。map是由一對一對的鍵值(key/value)所組成的排序結構體,鍵值獨一無二。map通常是以balanced binary tree來實現,但並不強制規定。事實上map的內部結構通常與set是一樣的,因此我們可以將set視為一種特殊的map,其鍵值和實值是相同的,所以map和set幾乎擁有完全相同的能力。

multimap:

這是一種允許出現重復關鍵之的關聯數組容器,然而與map對象不同,它的一個關鍵詞可以與多個元素相聯系,multimap允許鍵值重復。

hash table:

這並不是C++ Standard規范內的一容器(因標准委員會作業時間的關系),但是它對於大量數據的搜索而言,很實用也很重要。有許多STL實作品例如SGI都涵蓋了它。通常STL產品廠商會提供4中hash tables: hash_set、hash_multiset、hash_map、hash_multimap。

Copyright © Linux教程網 All Rights Reserved