C++ STL常用容器總結（vector, deque, list, map, set）
- 1. vector（動態數組）
- 特點
- 定義和初始化
- 常用操作
- 遍歷方法
- 2. deque（雙端隊列）
- 特點
- 定義和初始化
- 常用操作
- 3. list（雙向鏈表）
- 特點
- 定義和初始化
- 常用操作
- 遍歷方法
- 4. map（關聯容器-映射）
- 特點
- 定義和初始化
- 常用操作
- 遍歷方法
- 5. set（關聯容器-集合）
- 特點
- 定義和初始化
- 常用操作
- 遍歷方法
- 容器選擇指南
- 通用操作
1. vector（動態數組）
特點
- 動態大小的數組，內存連續存儲
- 支持隨機訪問，時間復雜度O(1)
- 尾部插入刪除效率高O(1)，中間插入刪除效率低O(n)
定義和初始化
#include <vector>vector<int> vec1; // 默認初始化，vec1為空
vector<int> vec2(vec1); // 使用vec1初始化vec2
vector<int> vec3(vec1.begin(),vec1.end()); // 使用vec1初始化vec3
vector<int> vec4(10); // 10個值為0的元素
vector<int> vec5(10,4); // 10個值為4的元素
vector<int> vec6{1,2,3,4,5}; // 列表初始化
常用操作
// 添加元素
vec1.push_back(100); // 尾部添加元素
vec1.insert(vec1.begin(), 50); // 在開頭插入50
vec1.insert(vec1.end(), 5, 3); // 從末尾插入5個值為3的元素// 訪問元素
cout << vec1[0] << endl; // 下標訪問
cout << vec1.at(0) << endl; // at()訪問，有邊界檢查
cout << vec1.front() << endl; // 首元素
cout << vec1.back() << endl; // 尾元素// 刪除元素
vec1.pop_back(); // 刪除末尾元素
vec1.erase(vec1.begin()); // 刪除首元素
vec1.erase(vec1.begin(), vec1.begin()+2); // 刪除[0,2)區間元素// 容器信息
int size = vec1.size(); // 元素個數
bool isEmpty = vec1.empty(); // 判斷是否為空
vec1.clear(); // 清空所有元素
遍歷方法
// 1. 下標法
for(int i = 0; i < vec1.size(); i++) {cout << vec1[i] << " ";
}// 2. 迭代器法
for(vector<int>::iterator it = vec1.begin(); it != vec1.end(); it++) {cout << *it << " ";
}// 3. 范圍for循環（C++11）
for(auto x : vec1) {cout << x << " ";
}
2. deque（雙端隊列）
特點
- 雙端隊列，支持兩端快速插入刪除O(1)
- 支持隨機訪問O(1)
- 內存不連續，由多個塊組成
定義和初始化
#include <deque>deque<int> dq1; // 默認初始化
deque<int> dq2(10); // 10個值為0的元素
deque<int> dq3(10, 5); // 10個值為5的元素
deque<int> dq4{1,2,3,4,5}; // 列表初始化
常用操作
// 添加元素
dq1.push_back(100); // 尾部添加
dq1.push_front(50); // 頭部添加
dq1.insert(dq1.begin()+1, 75); // 指定位置插入// 訪問元素
cout << dq1[0] << endl; // 下標訪問
cout << dq1.at(0) << endl; // at()訪問
cout << dq1.front() << endl; // 首元素
cout << dq1.back() << endl; // 尾元素// 刪除元素
dq1.pop_back(); // 刪除尾部元素
dq1.pop_front(); // 刪除頭部元素
dq1.erase(dq1.begin()); // 刪除指定位置元素// 容器信息
cout << dq1.size() << endl; // 元素個數
cout << dq1.empty() << endl; // 是否為空
dq1.clear(); // 清空
3. list（雙向鏈表）
特點
- 雙向鏈表，內存不連續
- 不支持隨機訪問，只能順序訪問
- 任意位置插入刪除效率高O(1)
定義和初始化
#include <list>list<int> lst1; // 默認初始化
list<int> lst2(10); // 10個值為0的元素
list<int> lst3(10, 5); // 10個值為5的元素
list<int> lst4{1,2,3,4,5}; // 列表初始化
常用操作
// 添加元素
lst1.push_back(100); // 尾部添加
lst1.push_front(50); // 頭部添加
auto it = lst1.begin();
advance(it, 2); // 迭代器前進2位
lst1.insert(it, 75); // 指定位置插入// 訪問元素（只能通過迭代器）
cout << lst1.front() << endl; // 首元素
cout << lst1.back() << endl; // 尾元素// 刪除元素
lst1.pop_back(); // 刪除尾部
lst1.pop_front(); // 刪除頭部
lst1.remove(75); // 刪除所有值為75的元素
lst1.erase(lst1.begin()); // 刪除指定位置// 鏈表特有操作
lst1.sort(); // 排序
lst1.reverse(); // 反轉
lst1.unique(); // 去除連續重復元素// 容器信息
cout << lst1.size() << endl;
cout << lst1.empty() << endl;
lst1.clear();
遍歷方法
// 迭代器法
for(list<int>::iterator it = lst1.begin(); it != lst1.end(); it++) {cout << *it << " ";
}// 范圍for循環
for(auto x : lst1) {cout << x << " ";
}
4. map（關聯容器-映射）
特點
- 存儲鍵值對(key-value)
- 按key自動排序（基于紅黑樹）
- key唯一，查找效率O(log n)
定義和初始化
#include <map>map<string, int> mp1; // 默認初始化
map<string, int> mp2{{"apple", 5}, {"banana", 3}, {"orange", 8}}; // 列表初始化
常用操作
// 插入元素
mp1["apple"] = 5; // 下標法插入/修改
mp1.insert(pair<string, int>("banana", 3)); // insert插入
mp1.insert(make_pair("orange", 8)); // make_pair插入
mp1.emplace("grape", 6); // emplace插入（C++11）// 訪問元素
cout << mp1["apple"] << endl; // 下標訪問
cout << mp1.at("apple") << endl; // at()訪問// 查找元素
auto it = mp1.find("apple"); // 查找，返回迭代器
if(it != mp1.end()) {cout << "Found: " << it->second << endl;
}// 判斷元素是否存在
if(mp1.count("apple") > 0) { // count返回0或1cout << "apple exists" << endl;
}// 刪除元素
mp1.erase("apple"); // 根據key刪除
mp1.erase(mp1.find("banana")); // 根據迭代器刪除// 容器信息
cout << mp1.size() << endl;
cout << mp1.empty() << endl;
mp1.clear();
遍歷方法
// 迭代器法
for(map<string, int>::iterator it = mp1.begin(); it != mp1.end(); it++) {cout << it->first << ": " << it->second << endl;
}// 范圍for循環
for(auto& pair : mp1) {cout << pair.first << ": " << pair.second << endl;
}// C++17結構化綁定
for(auto& [key, value] : mp1) {cout << key << ": " << value << endl;
}
5. set（關聯容器-集合）
特點
- 存儲唯一元素，自動排序
- 基于紅黑樹實現
- 查找、插入、刪除效率O(log n)
定義和初始化
#include <set>set<int> st1; // 默認初始化
set<int> st2{1, 3, 5, 7, 9}; // 列表初始化
set<int> st3(st2.begin(), st2.end()); // 迭代器初始化
常用操作
// 插入元素
st1.insert(10); // 插入單個元素
st1.insert({20, 30, 40}); // 插入多個元素
auto result = st1.insert(10); // insert返回pair<iterator, bool>
if(result.second) {cout << "插入成功" << endl;
}// 查找元素
auto it = st1.find(10); // 查找，返回迭代器
if(it != st1.end()) {cout << "Found: " << *it << endl;
}// 判斷元素是否存在
if(st1.count(10) > 0) { // count返回0或1cout << "10 exists" << endl;
}// 刪除元素
st1.erase(10); // 根據值刪除
st1.erase(st1.find(20)); // 根據迭代器刪除
st1.erase(st1.begin(), st1.end()); // 刪除范圍// 集合運算
set<int> st4{1, 2, 3};
set<int> st5{2, 3, 4};
set<int> result_union, result_intersection;// 并集
set_union(st4.begin(), st4.end(), st5.begin(), st5.end(), inserter(result_union, result_union.begin()));// 交集
set_intersection(st4.begin(), st4.end(), st5.begin(), st5.end(),inserter(result_intersection, result_intersection.begin()));// 容器信息
cout << st1.size() << endl;
cout << st1.empty() << endl;
st1.clear();
遍歷方法
// 迭代器法
for(set<int>::iterator it = st1.begin(); it != st1.end(); it++) {cout << *it << " ";
}// 范圍for循環
for(auto x : st1) {cout << x << " ";
}
容器選擇指南
| 容器 | 適用場景 | 時間復雜度 |
|---|---|---|
| vector | 需要隨機訪問，主要在尾部操作 | 訪問O(1)，尾部插入O(1) |
| deque | 需要隨機訪問，兩端都要操作 | 訪問O(1)，兩端插入O(1) |
| list | 頻繁在中間插入刪除，不需隨機訪問 | 插入刪除O(1)，查找O(n) |
| map | 需要鍵值對映射，要求有序 | 查找插入刪除O(log n) |
| set | 需要唯一元素集合，要求有序 | 查找插入刪除O(log n) |
通用操作
所有STL容器都支持的操作：
size()- 返回元素個數empty()- 判斷是否為空clear()- 清空所有元素begin(),end()- 返回迭代器==,!=- 比較操作符
RT-THREAD版)
)
)
