C++进阶-2-STL

C++标准模板库（STL）是C++语言的一个重要组成部分，它提供了一系列通用的类和函数模板，用于支持数据结构和算法的实现。STL的设计理念是实现高效、可复用和可扩展的数据结构和算法，使程序员能够专注于应用逻辑而非底层实现细节。

1. STL的组成部分

STL主要由以下几个部分组成：

1.1 容器（Containers）

容器是用于存储对象的类。STL提供了多种类型的容器，主要分为以下几类：

1.1.1 序列容器（Sequence Containers）

序列容器用于按顺序存储一组对象，常见的序列容器包括：

vector：动态数组，支持快速随机访问。
list：双向链表，适合频繁插入和删除操作。
deque：双端队列，支持在两端快速插入和删除。
array：固定大小的数组，支持直接访问。

这些容器的主要特点是它们的存储方式和访问效率，适合不同的使用场景。

1.1.2 关联容器（Associative Containers）

关联容器用于以键值对的形式存储对象，支持快速查找。常见的关联容器包括：

set：存储唯一元素，支持快速查找，通常使用红黑树实现。
map：存储键值对，键唯一，支持快速查找。
multiset 和 multimap：允许存储重复元素的集合和键值对。

这些容器的主要特点是它们的元素存储方式，通常基于平衡树或哈希表实现，提供高效的查找、插入和删除操作。

1.1.3 无序关联容器（Unordered Associative Containers）

使用哈希表实现的无序关联容器提供常数时间复杂度的查找。包括：

unordered_set
unordered_map
unordered_multiset
unordered_multimap

这些容器在插入和查找时的性能通常优于有序关联容器，但不保证元素的顺序。

1.2 算法（Algorithms）

STL提供了许多算法，适用于各种数据结构。常见算法包括：

排序算法：如 sort、stable_sort，用于对容器中的元素进行排序。
查找算法：如 find、binary_search，用于查找元素。
修改算法：如 copy、remove、unique，用于修改容器内容。
组合算法：如 merge、set_union，用于合并和集合操作。

这些算法都是以模板形式实现的，因此可以用于任何类型的容器，增强了代码的通用性和复用性。

1.3 迭代器（Iterators）

迭代器是用于访问容器中元素的对象，提供了一种统一的方式来遍历容器。STL中的迭代器分为几种类型：

输入迭代器（Input Iterator）：只读访问容器元素。
输出迭代器（Output Iterator）：只写访问容器元素。
前向迭代器（Forward Iterator）：可以读取和写入，并且至少可以遍历一次。
双向迭代器（Bidirectional Iterator）：可以向前和向后遍历。
随机访问迭代器（Random Access Iterator）：支持随机访问，如 vector 和 deque 的迭代器。

迭代器使得算法和容器的结合变得更加灵活，程序员可以使用相同的算法在不同类型的容器上进行操作。

1.4 适配器（Adapters）

适配器是对已有容器、迭代器和函数的封装，提供新的接口。常见的适配器包括：

容器适配器：
- stack：基于 deque 或 list 实现的栈，后进先出（LIFO）结构。
- queue：基于 deque 实现的队列，先进先出（FIFO）结构。
- priority_queue：基于堆实现的优先队列，支持按优先级访问元素。
迭代器适配器：
- reverse_iterator：反向迭代器，用于反向遍历容器。
- insert_iterator：插入迭代器，用于在遍历时插入元素。

适配器的使用可以简化编程，提高代码的可读性和可维护性。

2. STL的使用示例

2.1 使用 `vector`

vector 是最常用的序列容器之一，支持动态大小和随机访问。

cpp

#include <iostream>
#include <vector>
#include <algorithm> // for sortusing namespace std;int main() {// 创建一个vector并初始化vector<int> vec = {4, 1, 3, 9, 5};// 添加元素vec.push_back(2);// 排序sort(vec.begin(), vec.end());// 打印元素cout << "Sorted vector: ";for (int num : vec) {cout << num << " ";}cout << endl;return 0;
}

2.2 使用 `map`

map 是一种关联容器，用于存储键值对。

cpp

#include <iostream>
#include <map>using namespace std;int main() {// 创建一个mapmap<string, int> ages;// 插入键值对ages["Alice"] = 30;ages["Bob"] = 25;// 查找元素cout << "Alice's age: " << ages["Alice"] << endl;// 遍历mapcout << "All ages:" << endl;for (const auto& pair : ages) {cout << pair.first << ": " << pair.second << endl;}return 0;
}

2.3 使用迭代器

迭代器提供了一种通用的方式来访问容器中的元素。

cpp

#include <iostream>
#include <vector>using namespace std;int main() {vector<int> vec = {10, 20, 30, 40};// 使用迭代器遍历cout << "Vector elements: ";for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {cout << *it << " ";}cout << endl;return 0;
}

2.4 使用 `set`

set 是一种关联容器，存储唯一的元素，可以快速查找。

cpp

#include <iostream>
#include <set>using namespace std;int main() {// 创建一个setset<int> mySet = {1, 2, 3, 4, 5};// 插入元素mySet.insert(6);mySet.insert(3); // 重复元素，插入失败// 遍历setcout << "Set elements: ";for (const int& val : mySet) {cout << val << " ";}cout << endl;return 0;
}