C STL容器間的區別與選用標準

2022-09-23 06:57:13 字數 2724 閱讀 9193

stl容器有vector、list、deque、map、multimap、unordered_map、set、multiset和unodered_map,他們之間有什麼不同,各自的優缺點是什麼,如何選用時適當的容器,這些問題需要去了解。

序列容器,類似於c語言中的陣列,它維護一段連續的記憶體空間,具有固定的起始地址,可以在任何位置插入新元素,有隨機訪問功能,即提供操作符,並可以和標準c相容。在效率方面,任意元素的讀取、修改具有常數時間複雜度,在序列尾部進行插入、刪除是常數時間複雜度,但在序列的頭部插入、刪除的時間複雜度是o(n)。此外,當被插入的記憶體空間不夠時,需要重新申請一塊足夠大的記憶體並進行記憶體拷貝。值得注意的是,vector每次擴容為原來的兩倍,對小物件來說執行效率高,但如果遇到大物件,執行效率就低了。

序列容器,類似於c語言中的雙向連結串列,它通過指標來進行資料的訪問,因此維護的記憶體空間可以不連續,這有利於資料的隨機存取,沒有提供 操作符過載。效率方面,任意元素的訪問、修改時間複雜度是o(n),插入、刪除操作是常數時間複雜度。

序列容器,類似於c語言中的雙向佇列,即兩端都可以插入或者刪除的佇列,它維護一段連續的記憶體空間。queue支援 操作符,也就是支援隨機存取,而且跟vector的效率相差無幾,並且在序列的頭部插入和刪除操作是常數時間複雜度。

關聯容器,按照方式組成集合,其中鍵不允許重複,查詢的時間複雜度o(logn)。map內部自建一棵紅黑樹,會對資料自行排序,所以map內部的資料都是有序的。

關聯容器,multimap和map的區別在與一個鍵可以對應多個值,也就是說鍵允許重複。

關聯容器,和map的區別在於內部實現是hash表,因此其查詢速度非常的快。

關聯容器,set類似於數學裡面的集合,不過set的集合中不包含重複的元素,這是和vector的第一個區別,第二個區別是set內部用平衡二叉樹實現,所以會對資料進行排序,且便於元素查詢,查詢的時間複雜度是o(logn),而vector是使用連續記憶體儲存,便於隨機存取。set不支援下標訪問。

multiset類似於數學裡面的集合,和set最大的區別在於集合中可以包含重複的元素。

關聯容器,和set的區別在於內部實現基於hash表。需要注意的是,每當unordered_set內部進行一次擴容或者縮容,都需要對錶中的資料重新計算,也就是說,擴容或者縮容的時間複雜度至少為o(n)。

在實際使用過程中,到底選擇這幾種容器中的哪一個,應該根據遵循以下原則:

1、如果需要高效的隨機存取,不在乎插入和刪除的效率,使用vector;

2、如果需要大量的插入和刪除元素,不關心隨機存取的效率,使用list;

3、如果需要隨機存取,並且關心兩端資料的插入和刪除效率,使用deque;

4、如果打算儲存資料字典,並且要求方便地根據key找到value,一對一的情況使用map,一對多的情況使用multimap;

5、如果打算查詢一個元素是否存在於某集合中,唯一存在的情況使用set,不唯一存在的情況使用multiset。

6、如果要求很快的查詢速度,根據情況選擇使用unordered_map或unordered_set。

stl容器有vector、list、deque、map、multimap、unordered_map、set、multiset和unodered_map,他們之間有什麼不同,各自的優缺點是什麼,如何選用時適當的容器,這些問題需要去了解。

序列容器,類似於c語言中的陣列,它維護一段連續的記憶體空間,具有固定的起始地址,可以在任何位置插入新元素,有隨機訪問功能,即提供操作符,並可以和標準c相容。在效率方面,任意元素的讀取、修改具有常數時間複雜度,在序列尾部進行插入、刪除是常數時間複雜度,但在序列的頭部插入、刪除的時間複雜度是o(n)。此外,當被插入的記憶體空間不夠時,需要重新申請一塊足夠大的記憶體並進行記憶體拷貝。值得注意的是,vector每次擴容為原來的兩倍,對小物件來說執行效率高,但如果遇到大物件,執行效率就低了。

序列容器,類似於c語言中的雙向連結串列,它通過指標來進行資料的訪問,因此維護的記憶體空間可以不連續,這有利於資料的隨機存取,沒有提供 操作符過載。效率方面,任意元素的訪問、修改時間複雜度是o(n),插入、刪除操作是常數時間複雜度。

序列容器,類似於c語言中的雙向佇列,即兩端都可以插入或者刪除的佇列,它維護一段連續的記憶體空間。queue支援 操作符,也就是支援隨機存取,而且跟vector的效率相差無幾,並且在序列的頭部插入和刪除操作是常數時間複雜度。

關聯容器,按照方式組成集合,其中鍵不允許重複,查詢的時間複雜度o(logn)。map內部自建一棵紅黑樹,會對資料自行排序,所以map內部的資料都是有序的。

關聯容器,multimap和map的區別在與一個鍵可以對應多個值,也就是說鍵允許重複。

關聯容器,和map的區別在於內部實現是hash表,因此其查詢速度非常的快。

關聯容器,set類似於數學裡面的集合,不過set的集合中不包含重複的元素,這是和vector的第一個區別,第二個區別是set內部用平衡二叉樹實現,所以會對資料進行排序,且便於元素查詢,查詢的時間複雜度是o(logn),而vector是使用連續記憶體儲存,便於隨機存取。set不支援下標訪問。

multiset類似於數學裡面的集合,和set最大的區別在於集合中可以包含重複的元素。

關聯容器,和set的區別在於內部實現基於hash表。需要注意的是,每當unordered_set內部進行一次擴容或者縮容,都需要對錶中的資料重新計算,也就是說,擴容或者縮容的時間複雜度至少為o(n)。