C++ 標準庫容器詳解：特性、用法與場景選型

容器是 C++ 標準庫（STL）的核心組件，用于存儲和管理數據。不同容器因底層實現不同，在性能、功能和適用場景上差異顯著。本文系統梳理vector、list、set、map等常用容器，從核心特性、API 用法到場景選型進行全方位解析，幫助開發者精準選擇合適的容器。

一、容器分類與核心差異概覽

C++ 容器按功能可分為序列式容器（側重元素順序）和關聯式容器（側重元素查找），核心差異如下表：

二、序列式容器詳解

1.?vector：動態數組（最常用序列容器）

核心特性

• 底層實現：基于動態數組，內存連續（同數組），但支持自動擴容。
• 關鍵優勢：
  • 支持隨機訪問（通過[]或at()），時間復雜度 O (1)；
  • 尾部插入 / 刪除（push_back/pop_back）效率極高，O (1)；
  • 內存局部性好，緩存命中率高（因內存連續）。
• 局限性：
  • 中間 / 頭部插入 / 刪除需移動大量元素，O (n)；
  • 擴容時可能觸發內存重分配（通常擴容為原容量 2 倍），導致性能波動。

常用 API 與示例

#include <vector>
#include <iostream>
using namespace std;int main() {// 1. 初始化（三種常用方式）vector<int> vec1; // 空容器vector<int> vec2(5, 10); // 5個元素，均為10vector<int> vec3 = {1, 2, 3, 4, 5}; // 初始化列表// 2. 插入元素vec1.push_back(6); // 尾部插入（O(1)）vec1.insert(vec1.begin() + 1, 8); // 在索引1處插入（O(n)，需移動元素）// 3. 訪問元素（兩種方式）cout << vec3[2] << endl; // 下標訪問（無越界檢查，快）cout << vec3.at(3) << endl; // at()訪問（有越界檢查，安全）cout << "首元素：" << vec3.front() << "，尾元素：" << vec3.back() << endl;// 4. 遍歷（迭代器/范圍for）for (auto it = vec3.begin(); it != vec3.end(); ++it) {cout << *it << " ";}// 范圍for更簡潔（C++11+）for (int num : vec3) { cout << num << " "; }// 5. 修改與刪除vec3[0] = 100; // 直接修改vec1.pop_back(); // 刪除尾部元素（O(1)）vec3.erase(vec3.begin() + 2); // 刪除索引2處元素（O(n)）// 6. 容量管理（關鍵！）cout << "當前大小：" << vec2.size() // 元素個數<< "，容量：" << vec2.capacity() << endl; // 已分配內存可容納的元素數vec2.reserve(10); // 預分配容量（避免頻繁擴容）vec2.resize(3); // 調整大小（多余元素被截斷，新增元素為默認值）vec1.clear(); // 清空元素（size=0，但capacity不變）return 0;
}

典型場景

• 需頻繁隨機訪問元素（如存儲數組、矩陣、日志數據）；
• 元素主要在尾部增刪（如批量數據收集、緩沖區）；
• 需與 C 語言數組兼容（因內存連續，可通過data()獲取原始指針）。

2.?list：雙向鏈表（高效增刪的序列容器）

核心特性

• 底層實現：雙向鏈表，每個節點包含數據域和前后指針，內存不連續。
• 關鍵優勢：
  • 任意位置（已知迭代器）插入 / 刪除效率極高，O (1)（無需移動元素，僅修改指針）；
  • 無擴容開銷（節點動態分配），內存使用更靈活。
• 局限性：
  • 不支持隨機訪問（訪問第 n 個元素需從頭遍歷），時間復雜度 O (n)；
  • 內存開銷大（每個節點額外存儲兩個指針）；
  • 緩存命中率低（內存不連續）。

常用 API 與示例

#include <list>
#include <iostream>int main() {// 1. 初始化list<int> list1;list<int> list2(4, 20); // 4個元素，均為20list<int> list3 = {10, 20, 30, 40};// 2. 插入元素（頭部/尾部/中間）list1.push_back(5); // 尾部插入（O(1)）list1.push_front(3); // 頭部插入（O(1)）auto it = list3.begin(); ++it; // 指向第二個元素（20）list3.insert(it, 25); // 在20和30之間插入25（O(1)，已知位置）// 3. 訪問元素（僅支持首尾直接訪問）cout << "首元素：" << list3.front() << "，尾元素：" << list3.back() << endl;// 訪問中間元素需遍歷it = list3.begin();advance(it, 2); // 移動迭代器到第3個元素（25）cout << "第3個元素：" << *it << endl;// 4. 遍歷（僅迭代器/范圍for）for (int num : list3) { cout << num << " "; }// 5. 特殊操作（鏈表特有）list3.reverse(); // 反轉鏈表（O(n)，僅修改指針）list3.sort(); // 排序（O(n log n)，鏈表自帶排序，無需轉換為vector）// 6. 刪除元素list1.pop_back(); // 尾部刪除（O(1)）list3.pop_front(); // 頭部刪除（O(1)）it = list3.begin(); ++it;list3.erase(it); // 刪除指定位置元素（O(1)，已知位置）return 0;
}

典型場景

• 頻繁在中間位置增刪元素（如實現鏈表、隊列、棧的變種）；
• 數據量不確定，且需避免擴容開銷（如實時數據采集，元素動態增減）；
• 需要高效拆分 / 合并鏈表（splice()方法，O (1) 實現鏈表拼接）。

三、關聯式容器詳解

1.?set與unordered_set：集合（元素去重與查找）

核心特性對比

常用 API 與示例（以set為例）

#include <set>
#include <iostream>
#include <functional> // 用于自定義排序
using namespace std;
int main() {// 1. 初始化（默認升序）set<int> set1;// 自定義排序（降序）set<int,greater<int>> set2;// 2. 插入元素（自動去重）set1.insert(3);set1.insert(1);set1.insert(2);set1.insert(2); // 重復元素，插入無效set2.insert({5, 3, 7}); // 初始化列表插入// 3. 查找元素（核心操作）auto it1 = set1.find(2); // 查找值為2的元素if (it1 != set1.end()) {cout << "找到元素：" << *it1 << endl;}// 判斷元素是否存在（count()返回0或1）if (set1.count(3)) { cout << "元素3存在" << endl; }// 4. 遍歷（有序性體現）cout << "set1（升序）：";for (int num : set1) { cout << num << " "; } // 輸出：1 2 3cout << "\nset2（降序）：";for (int num : set2) { cout << num << " "; } // 輸出：7 5 3// 5. 刪除元素set1.erase(1); // 按值刪除（O(log n)）set2.erase(set2.begin()); // 按迭代器刪除（O(1)）return 0;
}

典型場景

• set：需去重且保持有序（如排行榜、區間統計，支持lower_bound/upper_bound范圍查詢）；
• unordered_set：僅需去重，追求極致查找效率（如緩存校驗、數據去重驗證）。

2.?map與unordered_map：鍵值對（關聯查詢）

核心特性對比

常用 API 與示例（以unordered_map為例）

cpp

運行

#include <unordered_map>
#include <iostream>int main() {// 1. 初始化（鍵為int，值為string）unordered_map<int, string> umap;// 2. 插入鍵值對（三種方式）umap.insert({1, "one"}); // 插入pair（重復key無效）umap[2] = "two"; // []運算符（重復key會覆蓋）umap.emplace(3, "three"); // 直接構造（效率更高）// 3. 訪問value（兩種方式）cout << umap[2] <<endl; // []訪問（無key則插入默認值）try {cout << umap.at(3) << endl; // at()訪問（無key拋異常，更安全）} catch (const out_of_range& e) {cout << "key不存在" << endl;}// 4. 查找key（核心操作）auto it = umap.find(1); // 查找key=1if (it != umap.end()) {cout << "key：" << it->first << "，value：" << it->second << endl;}// 5. 遍歷for (const auto& pair : umap) {cout << pair.first << " → " << pair.second << " ";}// 6. 刪除元素umap.erase(2); // 按key刪除it = umap.find(3);if (it != umap.end()) {umap.erase(it); // 按迭代器刪除}return 0;
}

典型場景

• map：需按 key 排序的鍵值對（如按 ID 排序的用戶信息、區間查詢配置）；
• unordered_map：高頻鍵值查詢（如數據庫索引、緩存映射，優先考慮查找速度）。

四、容器選型決策指南

選擇容器時需結合操作類型（增刪查為主？隨機訪問？）、數據特性（是否有序？是否重復？）和性能需求（時間 / 內存優先），決策流程如下：

1. 是否需要鍵值對關聯？

   • 是 → 選map（有序）或unordered_map（無序）；
   • 否 → 進入下一步。

2. 是否需要去重？

   • 是 → 選set（有序）或unordered_set（無序）；
   • 否 → 進入下一步（序列容器）。

3. 序列容器核心需求？

   • 頻繁隨機訪問 →?vector；
   • 頻繁中間增刪 →?list；
   • 頭尾增刪頻繁且需隨機訪問 →?deque（雙端隊列，未詳細展開）。

五、容器算法

C++ 標準庫的?<algorithm>?頭文件提供了大量實用算法，涵蓋排序、查找、修改、數值計算等場景。以下是常用算法的分類總結及例程：

5.1 排序與順序相關算法

1.?sort?- 快速排序（不穩定）

對范圍元素排序，平均復雜度 O (n log n)

#include <algorithm>
#include <vector>
#include <iostream>int main() {std::vector<int> v = {3, 1, 4, 1, 5};std::sort(v.begin(), v.end()); // 升序// 輸出：1 1 3 4 5// 自定義降序std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });// 輸出：5 4 3 1 1return 0;
}

2.?stable_sort?- 穩定排序

保持相等元素的原始相對順序

std::vector<std::pair<int, int>> v = {{2,1}, {1,2}, {2,3}};
std::stable_sort(v.begin(), v.end()); 
// 結果：{1,2}, {2,1}, {2,3}（兩個2的相對順序不變）

3.?partial_sort?- 部分排序

只保證前 k 個元素有序（最小的 k 個）

std::vector<int> v = {5, 3, 1, 4, 2};
std::partial_sort(v.begin(), v.begin()+3, v.end());
// 結果：1 2 3 5 4（前3個為最小且有序）

4.?nth_element?- 定位第 n 大元素

使第 n 個元素處于排序后的正確位置

std::vector<int> v = {5, 3, 1, 4, 2};
std::nth_element(v.begin(), v.begin()+2, v.end());
// 結果：2 1 3 5 4（3是第3小元素，左側≤3，右側≥3）

5.2? 查找算法

1.?find?- 查找元素

返回首個匹配元素的迭代器

std::vector<int> v = {1, 2, 3, 4, 5};
auto it = std::find(v.begin(), v.end(), 3);
if (it != v.end()) {std::cout << "找到元素：" << *it; // 輸出：3
}

2.?find_if?- 條件查找

通過謂詞查找元素

// 查找第一個偶數
auto it = std::find_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

3.?binary_search?- 二分查找

在已排序范圍中查找（返回 bool）

std::vector<int> v = {1, 3, 5, 7};
bool exists = std::binary_search(v.begin(), v.end(), 5); // true

4.?lower_bound?/?upper_bound

• lower_bound：返回首個 ≥ 目標值的迭代器
• upper_bound：返回首個 > 目標值的迭代器

std::vector<int> v = {1, 3, 3, 5};
auto lb = std::lower_bound(v.begin(), v.end(), 3); // 指向第一個3
auto ub = std::upper_bound(v.begin(), v.end(), 3); // 指向5
int count = ub - lb; // 3的個數：2

5.3 容器修改算法

1.?copy?- 復制元素

std::vector<int> src = {1, 2, 3};
std::vector<int> dest(3);
std::copy(src.begin(), src.end(), dest.begin()); // dest = {1,2,3}

2.?swap?- 交換元素

int a = 1, b = 2;
std::swap(a, b); // a=2, b=1std::vector<int> v1 = {1,2}, v2 = {3,4};
std::swap(v1, v2); // 交換整個容器

3.?reverse?- 反轉范圍

std::vector<int> v = {1, 2, 3};
std::reverse(v.begin(), v.end()); // {3,2,1}

4.?remove?- 移除元素（邏輯刪除）

std::vector<int> v = {1, 2, 3, 2, 4};
// 邏輯刪除所有2（返回新結尾迭代器）
auto last = std::remove(v.begin(), v.end(), 2);
v.erase(last, v.end()); // 物理刪除，結果：{1,3,4}

5.?unique?- 移除連續重復元素

std::vector<int> v = {1, 2, 2, 3, 3, 3};
std::sort(v.begin(), v.end()); // 先排序
auto last = std::unique(v.begin(), v.end());
v.erase(last, v.end()); // 結果：{1,2,3}

5.4 數值與集合算法

1.?accumulate?- 累加（需?<numeric>?頭文件）

#include <numeric>
std::vector<int> v = {1, 2, 3, 4};
int sum = std::accumulate(v.begin(), v.end(), 0); // 0+1+2+3+4=10// 計算乘積
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());

2.?count?/?count_if?- 計數

std::vector<int> v = {1, 2, 2, 3};
int cnt = std::count(v.begin(), v.end(), 2); // 2的個數：2// 計數偶數
int even_cnt = std::count_if(v.begin(), v.end(), [](int x) { return x%2==0; });

3.?min_element?/?max_element?- 查找最值

std::vector<int> v = {3, 1, 4};
auto min_it = std::min_element(v.begin(), v.end()); // 指向1
auto max_it = std::max_element(v.begin(), v.end()); // 指向4

4.?set_intersection?- 求交集（需已排序）

std::vector<int> a = {1, 2, 3, 4};
std::vector<int> b = {3, 4, 5, 6};
std::vector<int> res;
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(res));
// res = {3,4}

5.5? 編程練習

#include <algorithm>
#include <vector>
#include <iostream>
#include <numeric>  // 用于accumulateusing namespace std;int main() {// 一、排序與順序相關算法{// 1. sort - 快速排序（不穩定）vector<int> v1 = {3, 1, 4, 1, 5};sort(v1.begin(), v1.end());  // 升序cout << "sort升序: ";for (int num : v1) cout << num << " ";  // 1 1 3 4 5cout << endl;// 自定義降序sort(v1.begin(), v1.end(), [](int a, int b) { return a > b; });cout << "sort降序: ";for (int num : v1) cout << num << " ";  // 5 4 3 1 1cout << endl;// 2. stable_sort - 穩定排序（保留相等元素相對順序）vector<pair<int, int>> v2 = {{2,1}, {1,2}, {2,3}};stable_sort(v2.begin(), v2.end());cout << "stable_sort結果: ";for (auto p : v2) cout << "{" << p.first << "," << p.second << "} ";  // {1,2} {2,1} {2,3}cout << endl;// 3. partial_sort - 部分排序（前k個元素有序）vector<int> v3 = {5, 3, 1, 4, 2};partial_sort(v3.begin(), v3.begin()+3, v3.end());cout << "partial_sort前3個: ";for (int num : v3) cout << num << " ";  // 1 2 3 5 4cout << endl;// 4. nth_element - 定位第n個元素vector<int> v4 = {5, 3, 1, 4, 2};nth_element(v4.begin(), v4.begin()+2, v4.end());  // 第3小元素cout << "nth_element結果: ";for (int num : v4) cout << num << " ";  // 2 1 3 5 4（3在正確位置）cout << endl;}// 二、查找算法{vector<int> v = {1, 2, 3, 4, 5};// 1. find - 查找元素auto it1 = find(v.begin(), v.end(), 3);if (it1 != v.end()) cout << "find找到: " << *it1 << endl;  // 3// 2. find_if - 條件查找auto it2 = find_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });if (it2 != v.end()) cout << "find_if找到首個偶數: " << *it2 << endl;  // 2// 3. binary_search - 二分查找（需已排序）bool exists = binary_search(v.begin(), v.end(), 5);cout << "binary_search查找5: " << (exists ? "存在" : "不存在") << endl;  // 存在// 4. lower_bound/upper_boundvector<int> v_sorted = {1, 3, 3, 5};auto lb = lower_bound(v_sorted.begin(), v_sorted.end(), 3);  // 首個>=3auto ub = upper_bound(v_sorted.begin(), v_sorted.end(), 3);  // 首個>3cout << "3的個數: " << (ub - lb) << endl;  // 2}// 三、容器修改算法{// 1. copy - 復制元素vector<int> src = {1, 2, 3};vector<int> dest(3);copy(src.begin(), src.end(), dest.begin());cout << "copy結果: ";for (int num : dest) cout << num << " ";  // 1 2 3cout << endl;// 2. swap - 交換int a = 1, b = 2;swap(a, b);cout << "swap后: a=" << a << ", b=" << b << endl;  // a=2, b=1// 3. reverse - 反轉vector<int> v_rev = {1, 2, 3};reverse(v_rev.begin(), v_rev.end());cout << "reverse結果: ";for (int num : v_rev) cout << num << " ";  // 3 2 1cout << endl;// 4. remove - 移除元素（需配合erase）vector<int> v_rem = {1, 2, 3, 2, 4};auto last = remove(v_rem.begin(), v_rem.end(), 2);  // 邏輯刪除v_rem.erase(last, v_rem.end());  // 物理刪除cout << "remove后: ";for (int num : v_rem) cout << num << " ";  // 1 3 4cout << endl;// 5. unique - 去重（需先排序）vector<int> v_uni = {1, 2, 2, 3, 3, 3};sort(v_uni.begin(), v_uni.end());auto last_uni = unique(v_uni.begin(), v_uni.end());v_uni.erase(last_uni, v_uni.end());cout << "unique后: ";for (int num : v_uni) cout << num << " ";  // 1 2 3cout << endl;}// 四、數值與集合算法{vector<int> v = {1, 2, 3, 4};// 1. accumulate - 累加/累乘int sum = accumulate(v.begin(), v.end(), 0);  // 初始值0cout << "累加和: " << sum << endl;  // 10int product = accumulate(v.begin(), v.end(), 1, multiplies<int>());cout << "累乘積: " << product << endl;  // 24// 2. count/count_if - 計數vector<int> v_cnt = {1, 2, 2, 3};int cnt = count(v_cnt.begin(), v_cnt.end(), 2);cout << "數字2的個數: " << cnt << endl;  // 2int even_cnt = count_if(v_cnt.begin(), v_cnt.end(), [](int x) { return x%2 == 0; });cout << "偶數個數: " << even_cnt << endl;  // 2// 3. min_element/max_element - 最值vector<int> v_minmax = {3, 1, 4};auto min_it = min_element(v_minmax.begin(), v_minmax.end());auto max_it = max_element(v_minmax.begin(), v_minmax.end());cout << "最小值: " << *min_it << ", 最大值: " << *max_it << endl;  // 1,4// 4. set_intersection - 交集（需已排序）vector<int> a = {1, 2, 3, 4};vector<int> b = {3, 4, 5, 6};vector<int> res;set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(res));cout << "交集: ";for (int num : res) cout << num << " ";  // 3 4cout << endl;}return 0;
}

六 、算法使用要點

1. 算法通常接受迭代器范圍?[first, last)（左閉右開）
2. 排序相關算法要求容器支持隨機訪問迭代器（如?vector、array）
3. 二分查找類算法要求范圍已排序
4. 自定義謂詞需滿足 "嚴格弱序" 規則，避免邏輯錯誤

這些算法大幅簡化了常見操作，合理使用可提高代碼效率和可讀性。

總結

C++ 容器的設計各有側重：vector以連續內存和隨機訪問為核心，list以高效增刪為優勢，set/map提供有序性和穩定查找，unordered_*系列則追求極致查詢效率。理解底層實現是掌握容器的關鍵 —— 紅黑樹帶來有序性和穩定性能，哈希表帶來平均 O (1) 的效率，動態數組平衡了訪問與增刪成本。實際開發中，需根據具體場景的操作頻率和性能需求，選擇最適合的容器，才能寫出高效、易維護的代碼。