在面向對象程序中,大多引入了容器的概念。那麼什麼是容器?實質上是一組相同類型對象的集合,但它不僅僅是數組那麼簡單,它實現了比數組更復雜的數據結構,能夠實現更復雜的功能。C++標准模版庫裡提供了10種通用的容器,它基本可以解決程序中遇到的大部分問題。
什麼是容器
C++中容器的定義如下:數據存儲上,有一種對象類型,它可以持有其他對象或指向其他對象的指針,這種對象類型叫容器。通俗的說容器就是保存其他對象的對象,這種“對象”還包含了一些列處理其他對象的方法,這也體現了容器類的一個好處,“容器類對特定代碼重用問題的良好的解決方案”。
容器另一個好處就是可以自行擴展,解決問題是我們不知道需要存儲多少個對象,數組在這方面是個欠缺。容器可以為你申請內存、釋放內存,並且使用最優的算法來執行你的命令。
通用容器的分類
(1)順序性容器:各元素之間有順序關系的線性表,是一種線性關系的有序集群,順序容器中的元素均有固定的位置,除非用刪除和插入來改變它的位置,這個位置和元素本身無關,和操作時間和地點有關。
vector:從後面快速刪除和插入,訪問任一元素;
deque:從前面或後面快速刪除和插入,訪問任一元素;
list:雙聯表,從任何位置插入和刪除;
(2)關聯式容器:非線性的樹結構(二叉樹結構),各元素之間沒有嚴格的物理順序。關聯容器提供了根據元素特點排序的功能,迭代器根據元素特點“順序”的取元素。
set:快速查找,不允許重復值;
multiset:快速查找,允許重復值;
map:一對多映射,基於關鍵字快速查找,不允許重復值;
multimap:一對多映射,基於關鍵字快速查找,允許重復值;
(3)容器適配器:讓一種已存在的容器類型采用另一種不同抽象類型的工作方式來實現的一種機制。實質上僅發生了接口轉換。
stack:後進先出;
queue:先進先出;
priority_queue:最高優先級第一個出列;
順序性容器
(1)向量vector:我們可以把它看成動態數組,創建一個vector後,它會在內存中分配一塊連續的區域存儲數據,初試空間可以指定也可以有vector決定(capacity()函數返回值)。當數據存儲空間超過分配空間,vector會重新分配一塊內存區域,這樣的分配很耗時,動作如下:
首先,vector申請一塊更大內存區域;
然後,將原來的數據拷貝到新的內存區域;
其次,銷毀原來內存塊數據;
最後,釋放原來內存空間。
所以,如果vector保存的數據量很大,這樣的操作會導致很糟糕的性能。只有在預知空間大小的情況下,vector的性能才是最好的。
(2)雙向鏈表List:雙向線性鏈表結構,指針將所有元素鏈接起來。根據其結構特點,List檢索性能不好,需要順序查找,檢索時間與目標元素位置成正比。但是它可以對快速的刪除和插入。
(3)雙端隊列deque:對序列兩端插入和刪除的容器,可以快速的隨即查找。它不像vector把所有元素存儲在同一內存塊,而是采用多個連續的存儲塊,並且一個映射結構中保存對這些塊和元素順序的跟蹤。deque是vector和List優缺點的結合,它是處於兩者之間的一種容器。支持[]及vector.at(),性能沒有vector好。
關聯容器
set,multiset,map,multimap都是非線性結構的樹結構,采用高效的平衡檢索二叉樹——紅黑樹結構。
(1)set:一組元素的集合,元素值是唯一的,且按一定順序排列,集合中每個元素稱為集合的實例,內部采用鏈表結構組織;
(2)multiset:多重集合,實現方式類似set,元素值不唯一;
(3)map:提供“鍵--值”一一對應的數據存儲能力,“鍵”在容器中不可重復,且按一定順序排列;
(4)multimap:原理同上,“鍵”在容器中可重復。
關聯容器插入和刪除比vector快,比List要慢,每次插入刪除後需要對元素重現排序;
關聯容器檢索比vector慢,但比List要快得多;
容器適配器
STL提供的三種適配器可以由某一種順序容器去實現,默認stack和queue是基於deque容器實現,prioriety_queue是基於vector實現。