本文主要參考自 C++ Primer, 5th Edition, [美] Stanley B. Lippman / [美] Josée Lajoie / [美] Barbara E. Moo

1. 順序容器類型

在 STL 中（截至 C++11，提供瞭如下所示幾個順序類型）

vector：可變大小數組。支持快速隨機訪問。在尾部插入元素較快，但其他位置插入很慢。
deque：雙端隊列。支持快速隨機訪問。在頭部、尾部插入元素都很快。
list：雙向鏈表。僅支持雙向順序訪問。在任何位置刪除、添加元素都很快。
forward_list：單向鏈表。僅支持從頭部開始的順序訪問。在鏈表任何位置插入、刪除元素都很快。
array：固定大小數組。支持快速隨機訪問，不能添加、刪除元素。
string：和 vector 類似，只不過只能存儲 char 類型的數據。

2. 性能分析

除了 array 容器之外，其他容器均提供了高效的內存管理，可以在計算機資源允許的情況下任意添加刪除元素到容器中。它們之間的主要區別在於存儲策略的不同和操作接口的不同，從而間接導致了不同容器有不同的性能和應用場合。

string 和 vector 是存儲在一塊連續的內存空間中的，因此它可以很方便的計算每一個元素的物理地址從而實現快速隨機訪問。但是也正是因為它們在連續空間中存儲，當需要在中間位置 i 插入元素時，需要將 i + 1 及以後的每一個元素平移到它們的下一個位置，空出來 i 位置才可以插入進來保持空間的連續性。不僅如此，有時添加元素進來，需要擴容+拷貝元素到新存儲空間中。

list 和 forward_list 是兩個使用鏈表來實現的數據結構，它們在添加元素時非常便利，但是訪問時卻不支持快速隨機訪問，需要從頭部（list還支持從尾部向頭部的查找）開始逐個遍歷訪問。除此之外，這倆數據結構在存儲每一個元素時，都需要額外的空間來維持鏈表結構。

deque 是一個不僅支持快速隨機訪問，而且支持在頭部和尾部高效的刪除或添加元素，在這一點和 list 與 forward_list 效率相當。

forward_list 和 array 是 C++11 新添加的類型，array 是一種更加安全、易用的數組類型，在用法上和內置數組類似（並沒有感覺到有什麼大的區別）。forward_list 是單鏈表，為了達到最好的性能，沒有維護 size 方法，因此計算它的大小時，只能手動實現。

一般來說，除非有更好的理由（例如需要高頻率中間增加元素和刪除元素），使用 vector 就是最好的選擇了。

3. 容器選擇基本原則

一般選 vector 就可以啦，除非有更好理由。
如果空間的額外開銷很重要，不要用 list 和 forward_list。
如果要求高頻率隨機訪問元素，那麼使用 vector 和 deque 更加合適。
如果需要在容器中間位置插入刪除元素，使用 list 和 forward_list 更加合適。
如果只有在最初輸入階段需要插入刪除元素，而後穩定下來僅僅需要隨機訪問，可以這樣：
1. 如果需要在中間位置插入元素，那麼使用 list 來構造輸入階段，再把它放到 vector 中去。
2. 如果不需要在中間位置插入元素，那麼直接使用 vector （或 deque）就可以了，因為在末尾（或頭部）添加元素就很方便呀。

總的來說，容器操作類型（讀取或增刪）的佔比決定了容器類型的選擇，因此，在必要情況下進行性能測試也是不錯的選擇~

如果還是不清楚，那麼就用迭代器來代替下標訪問，因為迭代器是一個通用接口，可以任意替換具體實現而不影響程序使用，如下所示：

/**
 * Created by Xiaozhong on 2020/9/10.
 * Copyright (c) 2020/9/10 Xiaozhong. All rights reserved.
 */

#include <vector>
#include <list>
#include <iostream>

using namespace std;

int main() {
    list<int> nums = {1, 2, 3, 4, 5};
    /**
     *  如果後面需要，可以只改一處地方，就完成了整個實現，如：
     *  vector<int> nums = {1, 2, 3, 4, 5};
     */
    for (auto iter = nums.begin(); iter != nums.end(); iter++)
        cout << *iter << " "; // >: 1 2 3 4 5
}

C++的順序容器比較

1. 順序容器類型

2. 性能分析

3. 容器選擇基本原則

Leave a Reply Cancel reply