順序容器初探（上）

• 2021 年 3 月 17 日
• 筆記

一個容器就是一些特定類型對象的集合

順序容器的數據結構

array:

如下圖所示 數組是一個大小固定的數據結構，支持高效的隨機訪問，時間複雜度為O(1)，但是插入與刪除等操作比較低效,時間複雜度為O(n)，需要做大量的數據搬移工作。因此該容器支持快速隨機訪問，不支持添加或刪除元素。

forward_list:

下圖為一個單鏈表，與數組相反，它並不需要一塊連續的內存空間，它通過「指針」將一組零散的內存塊串聯起來使用，鏈表的特點為隨機訪問複雜度高，時間複雜度為O(n)，但是插入與刪除操作比較高效，時間複雜度為O(1)。

因此只支持單向順序訪問，在鏈表任何位置進行插入刪除操作都很快。

list:

下圖為一個雙向鏈表，與單向鏈表類似，只是在每個節點多了一個前驅指針，所以該鏈表支持雙向遍歷。

因此該容器支持雙向順序訪問，在鏈表任何位置進行插入刪除操作都很快。

deque：

下圖為單向隊列的數據結構，隊列跟棧一樣，也是一種抽象的數據結構。它具有先進先出的特性，支持在隊尾插入元素，在隊頭刪除元素。deque為雙向隊列的順序容器，顧名思義，雙向隊列的不同之處在於隊頭也是隊尾，隊尾也是隊頭。

因此deque這種容器支持快速隨機訪問，在頭尾位置插入/刪除速度很快。

vector:

vector其實也是一個數組結構，只不過經過對數組內存空間的管理，使得vector成為了一個動態的數組結構。

因此vector為可變大小數組，支持快速隨機訪問，在尾部之外的位置插入或刪除元素可能很慢。

string:

與vector類似的容器，但專門用來保存字符。隨機訪問快。在尾部插入刪除速度快。

容器選擇原則

1. 除非有很好的理由使用其他容器，否則應使用vector。

2. 如果程序有很多小元素，且空間額外開銷很重要，則不要使用鏈表。因為鏈表每個節點都會至少有一個後繼指針，因此會佔用很多額外空間。

3. 如果程序要求隨機訪問元素，則使用數組（vector）或隊列（deque）。string也支持隨機訪問，但是該容器專門用於保存字符，array則是因為該數組為固定大小數組。

4. 如果程序要求在容器的中間插入或刪除元素，應使用鏈表。

5. 如果程序要求在容器的頭尾插入或刪除元素，但不在中間插入，則使用隊列。

6. 如果程序要求只有在讀取輸入時需要在容器中插入元素，隨後需要隨機訪問元素，則

   • 首先確定真的需要中間插入元素，當處理輸入數據時，通常可以很容易的在vector容器末追加數據，再調用標準庫中的sort函數來對容器中的元素進行重排，以避免中間插入操作

   • 如果必須在中間位置插入元素，則在輸入階段考慮list，一旦輸入完成，將list中的數據拷貝到另一個vector中。

容器操作