STL 标准库

### STL标准库详解 #### 一、STL简介 C++ Standard Template Library (STL) 是一种用于C++编程语言的通用程序库，它提供了一系列高效的数据结构和算法，极大地提高了开发者的编程效率。STL的主要组成部分包括容器、迭代器、算法、函数对象以及分配器等。 - **容器**：提供了不同类型的容器来存储和组织数据，如向量(vector)、列表(list)、集合(set)等。 - **迭代器**：用于遍历容器中的元素。 - **算法**：提供了一组通用的算法，可以在不同的容器上运行，如排序(sort)、搜索(find)等。 - **函数对象**：也称为仿函数，是一种可以像函数一样被调用的对象。 - **分配器**：用于管理内存分配和释放，特别适用于容器中大量数据的管理。 #### 二、顺序性容器 ##### 2.1 C++ Vector（向量容器） - **定义**：`std::vector`是一个动态数组，它能够根据需要动态地调整其大小。 - **特点**： - 支持快速的随机访问。 - 在尾部插入或删除元素效率高。 - 当容量不足时，会重新分配内存并将原有数据复制过去，这是一个相对耗时的操作。 - **示例**： ```cpp std::vector<int> vec; // 创建一个空的向量 vec.push_back(1); // 在向量尾部添加元素 int first = vec.front(); // 访问向量的第一个元素 ``` ##### 2.2 C++ List（双向链表） - **定义**：`std::list`是一个双向链表，它支持在列表的任意位置快速地插入和删除元素。 - **特点**： - 插入和删除操作效率高，尤其是在列表的中间位置。 - 不支持随机访问。 - **示例**： ```cpp std::list<int> lst; // 创建一个空的列表 lst.push_front(1); // 在列表头部添加元素 lst.push_back(2); // 在列表尾部添加元素 ``` ##### 2.3 C++ Deque（双向队列） - **定义**：`std::deque`是一个双向队列，它允许在两端快速地插入和删除元素。 - **特点**： - 两端插入和删除元素效率高。 - 支持随机访问。 - **示例**： ```cpp std::deque<int> dq; // 创建一个空的双向队列 dq.push_front(1); // 在队列头部添加元素 dq.push_back(2); // 在队列尾部添加元素 ``` ##### 2.4 三者比较 - **性能对比**： - **随机访问**：`std::vector` > `std::deque` > `std::list` - **插入/删除**： - 尾部操作：`std::vector` ≈ `std::deque` > `std::list` - 中间操作：`std::list` > `std::deque` > `std::vector` - **适用场景**： - 需要频繁随机访问元素时，首选`std::vector`。 - 需要在两端频繁插入或删除元素时，选择`std::deque`。 - 需要在任意位置快速插入或删除元素时，选择`std::list`。 #### 三、关联容器 ##### 3.1 特点 - **关联容器**（如`std::set`、`std::map`）是通过键值来索引数据的容器，内部使用平衡二叉树或其他数据结构实现。 - **特点**： - 元素是有序的。 - 支持高效的查找、插入和删除操作。 - **示例**： ```cpp std::set<int> s; // 创建一个整数集合 s.insert(1); // 插入元素 ``` ##### 3.2 C++ Sets & Multisets - **定义**：`std::set`是一个包含唯一元素的集合；`std::multiset`允许重复元素的存在。 - **特点**： - 自动保持元素的排序。 - 不支持随机访问。 - 查找、插入和删除操作的时间复杂度为O(log n)。 - **示例**： ```cpp std::set<int> s; // 创建一个集合 s.insert(1); // 插入元素 ``` ##### 3.3 C++ Maps & Multimaps - **定义**：`std::map`是一个键值对的集合，其中键是唯一的；`std::multimap`允许相同的键存在多个值。 - **特点**： - 键值对按键的排序。 - 查找、插入和删除操作的时间复杂度为O(log n)。 - **示例**： ```cpp std::map<std::string, int> m; // 创建一个字符串到整数的映射 m["key"] = 1; // 插入键值对 ``` #### 四、容器适配器 - **容器适配器**：提供了一个接口，使得其他容器能够模拟某种数据结构的行为，如栈(stack)、队列(queue)等。 - **示例**： - **栈**（`std::stack`）：LIFO（Last In First Out）。 - **队列**（`std::queue`）：FIFO（First In First Out）。 - **优先队列**（`std::priority_queue`）：总是弹出优先级最高的元素。 #### 五、迭代器 - **定义**：迭代器是一种指针类型，用于遍历容器中的元素。 - **分类**： - 输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器。 - **示例**： ```cpp std::vector<int> v = {1, 2, 3}; auto it = v.begin(); // 获取迭代器指向向量的第一个元素 ``` #### 六、C++标准库总结 - **容器**：提供了各种类型的容器，如顺序性容器、关联容器和容器适配器。 - **算法**：提供了一组通用的算法，如排序、查找等。 - **函数对象**：提供了可以像函数一样调用的对象。 - **迭代器**：提供了遍历容器中元素的方式。 - **分配器**：提供了内存分配和释放的功能。 - **数值**：提供了处理数值运算的工具。 通过以上对STL的介绍，我们可以看出STL极大地方便了C++程序员的工作，使得他们能够更加专注于业务逻辑的实现，而不是底层数据结构和算法的实现细节。