C++算法
C++ 容器全面剖析：STL 常用容器特性与用法详解
详细解析了 C++ STL 中的三大类容器：序列容器（vector, array, list, deque）、关联容器（set, map）及无序容器（unordered_set, unordered_map）。阐述了各类容器的存储机制、时间复杂度特点及适用场景，并通过代码示例展示了常用操作方法，帮助开发者根据实际需求选择最优容器以提升程序性能。
详细解析了 C++ STL 中的三大类容器：序列容器（vector, array, list, deque）、关联容器（set, map）及无序容器（unordered_set, unordered_map）。阐述了各类容器的存储机制、时间复杂度特点及适用场景，并通过代码示例展示了常用操作方法，帮助开发者根据实际需求选择最优容器以提升程序性能。
C++ 标准模板库（STL）提供了一组功能强大的容器类，用于存储和操作数据集合。不同的容器具有独特的特性和应用场景，因此选择合适的容器对于程序的性能和代码的可读性至关重要。
C++ 容器按照用途大致分为三大类：
std::vector、std::array、std::deque、std::list。std::set、std::map、std::multiset、std::multimap。std::unordered_set、std::unordered_map。std::vectorstd::vector 是一个动态数组，支持自动扩展和随机访问，适用于需要频繁随机访问的场景。它是初学者最常使用的容器之一，因为它的使用方式和普通数组非常类似，但多了动态管理内存的功能。
std::vector 的大小会根据需求动态调整，当元素数目超过当前容量时，它会自动分配更多的内存来容纳新元素。vector 是连续存储，插入或删除中间元素时，需移动大量元素，因此效率为 O(n)。| 操作 | 方法 | 描述 |
|---|---|---|
| 添加元素 | push_back() | 在尾部插入元素 |
| 删除尾部元素 | pop_back() | 删除尾部元素 |
| 插入元素 | insert(iterator, value) | 在指定位置插入元素 |
| 删除指定元素 | erase(iterator) | 删除指定位置的元素 |
| 随机访问元素 | operator[] 或 at() | 随机访问指定索引处的元素 |
| 获取大小 | size() | 返回当前元素数量 |
| 检查是否为空 | empty() | 判断容器是否为空 |
| 调整大小 | resize() | 调整容器的大小，若新大小小于当前大小，超出部分的元素将被删除，若新大小大于当前大小，则会增加元素，默认初始化为零 |
| 清空容器 | clear() | 删除容器中的所有元素，容器的大小变为 0 |
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3};
// 添加元素
vec.push_back(4); // 在尾部添加元素 4
// 修改元素
vec[1] = 20; // 修改第二个元素的值为 20
// 插入和删除
vec.insert(vec.begin() + 2, 10); // 在索引 2 的位置插入元素 10
vec.erase(vec.begin() + 1); // 删除索引 1 的元素
// 调整大小
vec.resize(5, 0); // 调整容器大小为 5，新增的元素初始化为 0
// 清空容器
vec.clear(); // 删除所有元素
// 输出容器大小
std::cout << "Vector size after clear: " << vec.size() << std::endl;
return 0;
}
std::vector 适合需要频繁随机访问或尾部增删元素的场景，比如处理一组动态变化的数值或管理待办事项列表等。
std::arraystd::array 是固定大小的静态数组，大小在编译时确定。它的用法与普通 C 风格数组非常相似，但提供了一些更安全、更便捷的操作接口。
std::array 是静态分配的，因此不涉及动态内存分配，这使得它非常高效。| 操作 | 方法 | 描述 |
|---|---|---|
| 访问元素 | operator[] 或 at() | 随机访问元素 |
| 获取大小 | size() | 返回固定大小 |
| 获取头尾元素 | front() / back() | 获取第一个或最后一个元素 |
| 填充所有元素 | fill(value) | 用指定值填充整个数组 |
#include <array>
#include <iostream>
int main() {
std::array<int, 4> arr = {1, 2, 3, 4};
arr[2] = 10; // 修改第三个元素的值为 10
// 遍历并输出元素
for (int val : arr) {
std::cout << val << " ";
}
return 0;
}
std::array 适合用于需要固定大小且已知的数据集合，比如存储 RGB 颜色值或者某个固定大小的矩阵行数据。
std::liststd::list 是双向链表，适用于频繁的中间插入和删除操作。在链表中，每个元素都有一个指向前后元素的指针，这使得在任何位置进行插入和删除都非常高效。
vector 一样移动其他元素。| 操作 | 方法 | 描述 |
|---|---|---|
| 添加元素 | push_front() / push_back() | 在头部或尾部添加元素 |
| 删除元素 | pop_front() / pop_back() | 删除头部或尾部元素 |
| 插入元素 | insert(iterator, value) | 在指定位置插入元素 |
| 删除指定元素 | erase(iterator) | 删除指定位置的元素 |
#include <list>
#include <iostream>
int main() {
std::list<int> lst = {1, 2, 3};
lst.push_back(4); // 在尾部添加元素 4
lst.insert(std::next(lst.begin(), 1), 10); // 在第二个位置插入元素 10
lst.pop_front(); // 删除头部元素
// 遍历并输出元素
for (int val : lst) {
std::cout << val << " ";
}
return 0;
}
std::list 适合频繁的中间插入和删除，尤其是当数据集合较大并且需要灵活调整时，比如管理网络节点或实现复杂的缓存算法。
std::dequestd::deque 是双端队列，支持在头部和尾部快速插入和删除。它可以理解为 vector 和 list 的结合，具有两者的优点。
vector 类似，deque 支持通过索引直接访问元素，但它的底层存储结构并非一个连续的内存块。| 操作 | 方法 | 描述 |
|---|---|---|
| 添加元素 | push_front() / push_back() | 在头部或尾部添加元素 |
| 删除元素 | pop_front() / pop_back() | 删除头部或尾部元素 |
| 随机访问元素 | operator[] 或 at() | 随机访问元素 |
#include <deque>
#include <iostream>
int main() {
std::deque<int> dq = {1, 2, 3};
dq.push_front(0); // 在头部添加元素 0
dq.push_back(4); // 在尾部添加元素 4
// 遍历并输出元素
for (int val : dq) {
std::cout << val << " ";
}
return 0;
}
std::deque 适合在头尾都需要频繁增删数据的场景，比如模拟队列或双向缓存。
关联容器用于存储键值对，通常用于高效查找、插入和删除操作。
std::setstd::set 是集合容器，用于存储不重复的元素，底层实现为红黑树，具有自动排序的功能。
set 使用平衡二叉树，查找、插入和删除的时间复杂度为 O(log n)。set 保证集合中不会有重复的元素。| 操作 | 方法 | 描述 |
|---|---|---|
| 添加元素 | insert(value) | 插入一个元素 |
| 删除元素 | erase(iterator) | 删除指定元素 |
| 查找元素 | find(value) | 查找元素是否存在 |
#include <set>
#include <iostream>
int main() {
std::set<int> s = {3, 1, 4};
s.insert(2); // 插入元素 2
s.erase(1); // 删除元素 1
// 遍历并输出元素
for (int val : s) {
std::cout << val << " ";
}
return 0;
}
std::set 适合需要保证数据唯一性并且需要有序存储的场景，比如保存用户 ID、追踪唯一的值等。
std::mapstd::map 是键值对容器，类似于字典，它也是通过红黑树实现的，因此提供了有序的数据存储方式。
map 的查找、插入和删除操作的时间复杂度为 O(log n)。| 操作 | 方法 | 描述 |
|---|---|---|
| 添加元素 | operator[] 或 insert() | 添加或更新键值对 |
| 删除元素 | erase(iterator) | 删除指定键的元素 |
| 查找元素 | find(key) | 查找指定键是否存在 |
#include <map>
#include <iostream>
int main() {
std::map<int, std::string> m = {{1, "one"}, {2, "two"}};
m[3] = "three"; // 插入键值对 (3, "three")
// 遍历并输出键值对
for (auto& [key, value] : m) {
std::cout << key << ": " << value << std::endl;
}
return 0;
}
std::map 适合需要快速查找键值对的场景，比如存储用户信息或用于配置文件读取等。
| 场景 | 推荐容器 |
|---|---|
| 随机访问 | std::vector |
| 数据大小固定且已知 | std::array |
| 频繁插入和删除 | std::list 或 std::deque |
| 有序存储和查找 | std::set 或 std::map |
| 无序存储和查找 | std::unordered_set / std::unordered_map |
通过掌握这些容器的特性和用法，你将能够在开发中游刃有余地选择最佳的容器，为程序带来性能和代码可读性的提升。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online