C++ STL深度解析：vector、list、map的原理与应用

C++中的STL（Standard Template Library，标准模板库）是一组高效的、可重用的、类型安全的容器、算法和迭代器的集合，它极大地提高了C++程序员的生产力。STL的主要组成部分包括： 1. **容器**：容器是STL的基础，它们用于存储和组织数据。其中，`vector`、`list` 和 `map` 是三种常见的容器。 - **vector**：动态数组，支持随机访问。它可以像数组一样通过下标操作快速访问元素，但同时也支持动态增删元素。插入或删除元素时，可能会导致所有元素的重新排列，因此效率相对较低。`vector` 的常用操作包括： - `push_back()`：在末尾添加元素。 - `pop_back()`：删除最后一个元素。 - `at()`：安全访问元素，越界会抛出异常。 - `size()`：返回元素数量。 - `capacity()`：返回当前分配的内存大小。 - `reserve()`：预先分配内存，避免频繁的内存重新分配。 - `resize()`：改变容器大小，可以添加或删除元素。 - **list**：双向链表，适合频繁的插入和删除操作。由于每个元素都有前驱和后继指针，所以插入和删除操作的时间复杂度为O(1)，但访问元素需要线性时间。常用操作包括： - `push_front()`：在开头添加元素。 - `push_back()`：在末尾添加元素。 - `pop_front()`：删除第一个元素。 - `pop_back()`：删除最后一个元素。 - **map**：关联容器，提供键值对的映射。内部实现为红黑树，插入和查找的时间复杂度通常为O(logn)。常用操作包括： - `insert()`：插入键值对。 - `find()`：查找指定键的元素。 - `erase()`：删除键值对。 - `operator[]`：通过键直接访问或设置值。 2. **算法**：`algorithm` 头文件包含了一系列通用的算法，如排序、搜索、复制等，可以应用于任何类型的容器。 3. **迭代器**：迭代器是STL的桥梁，允许用户通过迭代访问容器中的元素，同时提供了类似指针的操作方式。迭代器有五种类型：输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器，每种都有不同的能力范围。 4. **其他组件**：除了上述组件，STL还包含`deque`(双端队列)、`set`(红黑树实现的集合)、`queue`(队列)、`stack`(栈)、`unordered_map`(哈希表实现的映射)等容器，以及`functional`（函数对象）、`memory`（智能指针）和`numeric`（数值计算）等库。 示例代码展示了`vector`的一些基本操作： ```cpp #include <iostream> #include <vector> using namespace std; int main() { vector<int> v1; // 创建一个空vector vector<int> v2(5, 0); // 创建一个包含5个0的vector vector<int> v3 = v2; // 复制构造 // 插入元素 v1.push_back(10); v1.push_back(20); // 访问元素 cout << v1[0] << endl; // 使用下标访问 cout << v1.at(1) << endl; // 安全访问，越界抛异常 // 删除元素 v1.pop_back(); // 查看容量和大小 cout << "Size: " << v1.size() << ", Capacity: " << v1.capacity() << endl; // 扩容 v1.reserve(100); return 0; } ``` 了解并熟练掌握STL的使用，对于编写高效、简洁的C++代码至关重要。