C++的順序容器比較

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

1. 順序容器類型

在

STL

中（截至

C++11

，提供了如下所示幾個順序類型）

1. vector

   ：可變大小數組。支援快速随機通路。在尾部插入元素較快，但其他位置插入很慢。

2. deque

   ：雙端隊列。支援快速随機通路。在頭部、尾部插入元素都很快。

3. list

   ：雙向連結清單。僅支援雙向順序通路。在任何位置删除、添加元素都很快。

4. forward_list

   ：單向連結清單。僅支援從頭部開始的順序通路。在連結清單任何位置插入、删除元素都很快。

5. array

   ：固定大小數組。支援快速随機通路，不能添加、删除元素。

6. 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. 容器選擇基本原則

1. 一般選

   vector

   就可以啦，除非有更好理由。
2. 如果空間的額外開銷很重要，不要用

   list

   forward_list

   。
3. 如果要求高頻率随機通路元素，那麼使用

   vector

   deque

   更加合适。
4. 如果需要在容器中間位置插入删除元素，使用

   list

   forward_list

5. 如果隻有在最初輸入階段需要插入删除元素，而後穩定下來僅僅需要随機通路，可以這樣：
   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
}