跳转至

序列式容器

vector

std::vector 是 STL 提供的 內存連續的、可變長度 的數組（亦稱列表）數據結構。能夠提供線性複雜度的插入和刪除，以及常數複雜度的隨機訪問。

為什麼要使用 vector

作為 OIer，對程序效率的追求遠比對工程級別的穩定性要高得多，而 vector 由於其對內存的動態處理，時間效率在部分情況下低於靜態數組，並且在 OJ 服務器不一定開全優化的情況下更加糟糕。所以在正常存儲數據的時候，通常不選擇 vector。下面給出幾個 vector 優秀的特性，在需要用到這些特性的情況下，vector 能給我們帶來很大的幫助。

vector 可以動態分配內存

很多時候我們不能提前開好那麼大的空間（eg：預處理 1~n 中所有數的約數）。儘管我們能知道數據總量在空間允許的級別，但是單份數據還可能非常大，這種時候我們就需要 vector 來把內存佔用量控制在合適的範圍內。vector 還支持動態擴容，在內存非常緊張的時候這個特性就能派上用場了。

vector 重寫了比較運算符及賦值運算符

vector 重載了六個比較運算符，以字典序實現，這使得我們可以方便的判斷兩個容器是否相等（複雜度與容器大小成線性關係）。例如可以利用 vector<char> 實現字符串比較（當然，還是用 std::string 會更快更方便）。另外 vector 也重載了賦值運算符，使得數組拷貝更加方便。

vector 便利的初始化

由於 vector 重載了 = 運算符，所以我們可以方便的初始化。此外從 C++11 起 vector 還支持 列表初始化，例如 vector<int> data {1, 2, 3};。

vector 的使用方法

以下介紹常用用法，詳細內容 請參見 C++ 文檔。

構造函數

用例參見如下代碼（假設你已經 using 了 std 命名空間相關類型）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// 1. 創建空vector; 常數複雜度
vector<int> v0;
// 1+. 這句代碼可以使得向vector中插入前3個元素時，保證常數時間複雜度
v0.reserve(3);
// 2. 創建一個初始空間為3的vector，其元素的默認值是0; 線性複雜度
vector<int> v1(3);
// 3. 創建一個初始空間為3的vector，其元素的默認值是2; 線性複雜度
vector<int> v2(3, 2);
// 4. 創建一個初始空間為3的vector，其元素的默認值是1，
// 並且使用v2的空間配置器; 線性複雜度
vector<int> v3(3, 1, v2.get_allocator());
// 5. 創建一個v2的拷貝vector v4， 其內容元素和v2一樣; 線性複雜度
vector<int> v4(v2);
// 6. 創建一個v4的拷貝vector v5，其內容是{v4[1], v4[2]}; 線性複雜度
vector<int> v5(v4.begin() + 1, v4.begin() + 3);
// 7. 移動v2到新創建的vector v6，不發生拷貝; 常數複雜度; 需要 C++11
vector<int> v6(std::move(v2));  // 或者 v6 = std::move(v2);
測試代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// 以下是測試代碼，有興趣的同學可以自己編譯運行一下本代碼。
cout << "v1 = ";
copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
cout << endl;
cout << "v2 = ";
copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
cout << endl;
cout << "v3 = ";
copy(v3.begin(), v3.end(), ostream_iterator<int>(cout, " "));
cout << endl;
cout << "v4 = ";
copy(v4.begin(), v4.end(), ostream_iterator<int>(cout, " "));
cout << endl;
cout << "v5 = ";
copy(v5.begin(), v5.end(), ostream_iterator<int>(cout, " "));
cout << endl;
cout << "v6 = ";
copy(v6.begin(), v6.end(), ostream_iterator<int>(cout, " "));
cout << endl;

可以利用上述的方法構造一個 vector，足夠我們使用了。

元素訪問

vector 提供瞭如下幾種方法進行元素訪問

  1. at()

    v.at(pos) 返回容器中下標為 pos 的引用。如果數組越界拋出 std::out_of_range 類型的異常。

  2. operator[]

    v[pos] 返回容器中下標為 pos 的引用。不執行越界檢查。

  3. front()

    v.front() 返回首元素的引用。

  4. back()

    v.back() 返回末尾元素的引用。

  5. data()

    v.data() 返回指向數組第一個元素的指針。

迭代器

vector 提供瞭如下幾種 迭代器

  1. begin()/cbegin()

    返回指向首元素的迭代器，其中 *begin = front。

  2. end()/cend()

    返回指向數組尾端佔位符的迭代器，注意是沒有元素的。

  3. rbegin()/crbegin()

    返回指向逆向數組的首元素的逆向迭代器，可以理解為正向容器的末元素。

  4. rend()/crend()

    返回指向逆向數組末元素後一位置的迭代器，對應容器首的前一個位置，沒有元素。

以上列出的迭代器中，含有字符 c 的為只讀迭代器，你不能通過只讀迭代器去修改 vector 中的元素的值。如果一個 vector 本身就是隻讀的，那麼它的一般迭代器和只讀迭代器完全等價。只讀迭代器自 C++11 開始支持。

長度和容量

vector 有以下幾個與容器長度和容量相關的函數。注意，vector 的長度（size）指有效元素數量，而容量（capacity）指其實際分配的內存長度，相關細節請參見後文的實現細節介紹。

與長度相關：

  • empty() 返回一個 bool 值，即 v.begin() == v.end()，true 為空，false 為非空。

  • size() 返回容器長度（元素數量），即 std::distance(v.begin(), v.end())。

  • resize() 改變 vector 的長度，多退少補。補充元素可以由參數指定。

  • max_size() 返回容器的最大可能長度。

    與容量相關：

  • reserve() 使得 vector 預留一定的內存空間，避免不必要的內存拷貝。

  • capacity() 返回容器的容量，即不發生拷貝的情況下容器的長度上限。

  • shrink_to_fit() 使得 vector 的容量與長度一致，多退但不會少。

元素增刪及修改

  • clear() 清除所有元素
  • insert() 支持在某個迭代器位置插入元素、可以插入多個。複雜度與 pos 距離末尾長度成線性而非常數的
  • erase() 刪除某個迭代器或者區間的元素，返回最後被刪除的迭代器。複雜度與 insert 一致。
  • push_back() 在末尾插入一個元素，均攤複雜度為 常數，最壞為線性複雜度。
  • pop_back() 刪除末尾元素，常數複雜度。
  • swap() 與另一個容器進行交換，此操作是 常數複雜度 而非線性的。

vector 的實現細節

vector 的底層其實仍然是定長數組，它能夠實現動態擴容的原因是增加了避免數量溢出的操作。首先需要指明的是 vector 中元素的數量（長度）\(n\) 與它已分配內存最多能包含元素的數量（容量）\(N\) 是不一致的，vector 會分開存儲這兩個量。當向 vector 中添加元素時，如發現 \(n>N\)，那麼容器會分配一個尺寸為 \(2N\) 的數組，然後將舊數據從原本的位置拷貝到新的數組中，再將原來的內存釋放。儘管這個操作的漸進複雜度是 \(O(n)\)，但是可以證明其均攤複雜度為 \(O(1)\)。而在末尾刪除元素和訪問元素則都仍然是 \(O(1)\) 的開銷。 因此，只要對 vector 的尺寸估計得當並善用 resize() 和 reserve()，就能使得 vector 的效率與定長數組不會有太大差距。

vector<bool>

標準庫特別提供了對 bool 的 vector 特化，每個「bool」只佔 1 bit，且支持動態增長。但是其 operator[] 的返回值的類型不是 bool& 而是 vector<bool>::reference。因此，使用 vector<bool> 使需謹慎，可以考慮使用 deque<bool> 或 vector<char> 替代。而如果你需要節省空間，請直接使用 bitset。

array(C++11)

std::array 是 STL 提供的 內存連續的、固定長度 的數組數據結構。其本質是對原生數組的直接封裝。

為什麼要用 array

array 實際上是 STL 對數組的封裝。它相比 vector 犧牲了動態擴容的特性，但是換來了與原生數組幾乎一致的性能（在開滿優化的前提下）。因此如果能使用 C++11 特性的情況下，能夠使用原生數組的地方几乎都可以直接把定長數組都換成 array，而動態分配的數組可以替換為 vector。

成員函數

隱式定義的成員函數

函數 作用
operator= 以來自另一 array 的每個元素重寫 array 的對應元素

元素訪問

函數 作用
at 訪問指定的元素，同時進行越界檢查
operator[] 訪問指定的元素，不 進行越界檢查
front 訪問第一個元素
back 訪問最後一個元素
data 返回指向內存中數組第一個元素的指針

at 若遇 pos >= size() 的情況會拋出 std::out_of_range。

容量

函數 作用
empty 檢查容器是否為空
size 返回容納的元素數
max_size 返回可容納的最大元素數

由於每個 array 都是固定大小容器，size() 返回的值等於 max_size() 返回的值。

操作

函數 作用
fill 以指定值填充容器
swap 交換內容

注意，交換兩個 array 是 \(\Theta(\text{size})\) 的，而非與常規 STL 容器一樣為 \(O(1)\)。

非成員函數

函數 作用
operator== 等 按照字典序比較 array 中的值
std::get 訪問 array 的一個元素
std::swap 特化的 std::swap 算法

下面是一個 array 的使用示例：

1
2
3
4
5
6
7
8
9
// 1. 創建空array，長度為3; 常數複雜度
std::array<int, 3> v0;
// 2. 用指定常數創建array; 常數複雜度
std::array<int, 3> v1{1, 2, 3};

v0.fill(1);  // 填充數組

// 訪問數組
for (int i = 0; i != arr.size(); ++i) cout << arr[i] << " ";

deque

std::deque 是 STL 提供的 雙端隊列 數據結構。能夠提供線性複雜度的插入和刪除，以及常數複雜度的隨機訪問。

deque 的使用方法

以下介紹常用用法，詳細內容 請參見 C++ 文檔。deque 的迭代器函數與 vector 相同，因此不作詳細介紹。

構造函數

參見如下代碼（假設你已經 using 了 std 命名空間相關類型）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// 1. 定義一個int類型的空雙端隊列 v0
deque<int> v0;
// 2. 定義一個int類型的雙端隊列 v1，並設置初始大小為10; 線性複雜度
deque<int> v1(10);
// 3. 定義一個int類型的雙端隊列 v2，並初始化為10個1; 線性複雜度
deque<int> v2(10, 1);
// 4. 複製已有的雙端隊列 v1; 線性複雜度
deque<int> v3(v1);
// 5. 創建一個v2的拷貝deque v4，其內容是v4[0]至v4[2]; 線性複雜度
deque<int> v4(v2.begin(), v2.begin() + 3);
// 6. 移動v2到新創建的deque v5，不發生拷貝; 常數複雜度; 需要 C++11
deque<int> v5(std::move(v2));

元素訪問

與 vector 一致，但無法訪問底層內存。其高效的元素訪問速度可參考實現細節部分。

  • at() 返回容器中指定位置元素的引用，執行越界檢查，常數複雜度。
  • operator[] 返回容器中指定位置元素的引用。不執行越界檢查，常數複雜度。
  • front() 返回首元素的引用。
  • back() 返回末尾元素的引用。

迭代器

與 vector 一致。

長度

與 vector 一致，但是沒有 reserve() 和 capacity() 函數。（仍然有 shrink_to_fit() 函數）

元素增刪及修改

與 vector 一致，並額外有向隊列頭部增加元素的函數。

  • clear() 清除所有元素
  • insert() 支持在某個迭代器位置插入元素、可以插入多個。複雜度與 pos 與兩端距離較小者成線性。
  • erase() 刪除某個迭代器或者區間的元素，返回最後被刪除的迭代器。複雜度與 insert 一致。
  • push_front() 在頭部插入一個元素，常數複雜度。
  • pop_front() 刪除頭部元素，常數複雜度。
  • push_back() 在末尾插入一個元素，常數複雜度。
  • pop_back() 刪除末尾元素，常數複雜度。
  • swap() 與另一個容器進行交換，此操作是 常數複雜度 而非線性的。

deque 的實現細節

deque 通常的底層實現是多個不連續的緩衝區，而緩衝區中的內存是連續的。而每個緩衝區還會記錄首指針和尾指針，用來標記有效數據的區間。當一個緩衝區填滿之後便會在之前或者之後分配新的緩衝區來存儲更多的數據。更詳細的説明可以參考 STL 源碼剖析——deque 的實現原理和使用方法詳解。

list

std::list 是 STL 提供的 雙向鏈表 數據結構。能夠提供線性複雜度的隨機訪問，以及常數複雜度的插入和刪除。

list 的使用方法

list 的使用方法與 deque 基本相同，但是增刪操作和訪問的複雜度不同。詳細內容 請參見 C++ 文檔。list 的迭代器、長度、元素增刪及修改相關的函數與 deque 相同，因此不作詳細介紹。

元素訪問

由於 list 的實現是鏈表，因此它不提供隨機訪問的接口。若需要訪問中間元素，則需要使用迭代器。

  • front() 返回首元素的引用。
  • back() 返回末尾元素的引用。

操作

list 類型還提供了一些針對其特性實現的 STL 算法函數。由於這些算法需要 隨機訪問迭代器，因此 list 提供了特別的實現以便於使用。這些算法有 splice()、remove()、sort()、unique()、merge() 等。

forward_list（C++11）

std::forward_list 是 STL 提供的 單向鏈表 數據結構，相比於 std::list 減小了空間開銷。

forward_list 的使用方法

forward_list 的使用方法與 list 幾乎一致，但是迭代器只有單向的，因此其具體用法不作詳細介紹。詳細內容 請參見 C++ 文檔

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：MingqiHuang, Xeonacid, greyqz, i-Yirannn, ChenZ01
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用