C++ STL常用容器总结（vector, deque, list, map, set）

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<int> vec1; // 默认初始化，vec1为空vector<int> vec2(vec1);  // 使用vec1初始化vec2vector<int> vec3(vec1.begin(),vec1.end()); // 使用vec1初始化vec3vector<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); // 在开头插入50vec1.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<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<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<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或1 cout << \"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<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返回pairif(result.second) { cout << \"插入成功\" << endl;}// 查找元素auto it = st1.find(10);  // 查找，返回迭代器if(it != st1.end()) { cout << \"Found: \" << *it << endl;}// 判断元素是否存在if(st1.count(10) > 0) {  // count返回0或1 cout << \"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() - 返回迭代器
• ==, != - 比较操作符