第4章 STL相关知识(一)

4.1 STL容器是什么？

STL（Standard Template Library） 容器是 C++ 标准库中用于存储和管理数据的组件。它们提供了一些常用的数据结构（如数组、链表、队列、栈、映射等），用于管理集合类型的数据。STL 容器具有强大的性能优势，因为它们基于模板，可以自动适应不同类型的数据，并且在 C++ 标准库中得到了高度优化。

STL 容器分为几种不同的类型，主要包括：

1. 序列容器（Sequence Containers）
2. 关联式容器（Associative Containers）
3. 无序关联式容器（Unordered Associative Containers）
4. 适配器容器（Container Adapters）

序列容器（Sequence Containers）

序列容器用于存储按顺序排列的数据，它们提供了类似数组和链表的功能。常见的序列容器有：

• vector：动态数组，可以在尾部快速增加元素，但在中间或开头插入元素时较慢。
• list：双向链表，支持在任意位置插入或删除元素，但不支持随机访问。
• deque：双端队列，允许在两端进行高效的插入和删除操作。
• array（C++11 引入）：固定大小的数组，可以进行快速访问。

关联式容器（Associative Containers）

关联式容器是一类按照特定规则（如红黑树）自动排序并存储元素的容器。它们提供了根据键快速查找数据的功能。常见的关联式容器有：

• set：存储唯一元素的集合，按照元素的键进行排序。
• map：存储键值对（key-value pairs），每个键必须是唯一的，按键排序。
• multiset：类似 set，但允许重复元素。
• multimap：类似 map，但允许多个相同的键。

这些容器通常实现了 红黑树（或平衡二叉搜索树）的数据结构，保证了元素的自动排序。

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

无序关联式容器与关联式容器类似，区别在于它们 不按照顺序存储 元素，而是通过哈希表来存储数据。它们提供常数时间的查找效率，但不保证元素的顺序。

常见的无序关联式容器有：

• unordered_set：存储唯一元素的集合，不按顺序存储。
• unordered_map：存储键值对（key-value pairs），不按顺序存储。
• unordered_multiset：与 unordered_set 类似，允许重复元素。
• unordered_multimap：与 unordered_map 类似，允许多个相同的键。

这些容器通常使用 哈希表 来实现。

适配器容器（Container Adapters）

适配器容器是对其他容器的封装，通常用于提供不同的操作接口。常见的适配器容器有：

• stack：栈，基于其他容器（通常是 deque 或 list）实现，遵循后进先出（LIFO）原则。
• queue：队列，基于其他容器（通常是 deque 或 list）实现，遵循先进先出（FIFO）原则。
• priority_queue：优先队列，基于堆（通常是 vector）实现，元素按优先级顺序出队。

总结

C++ STL 容器提供了多种数据存储和管理方式，针对不同的应用场景选择合适的容器可以显著提高程序的效率和可读性。根据数据存储方式和访问效率，C++ STL 容器可以分为：

1. 序列容器：vector, list, deque, array 等。
2. 关联式容器：set, map, multiset, multimap 等，基于 红黑树 实现。
3. 无序关联式容器：unordered_set, unordered_map, unordered_multiset, unordered_multimap 等，基于 哈希表 实现。
4. 适配器容器：stack, queue, priority_queue 等，封装其他容器。

4.2 序列容器

序列容器用于存储和管理数据，并且允许按照一定的顺序访问这些数据。序列容器是 STL 中的一类容器，通常包含一系列元素，支持元素的顺序存储和访问。它们与关联式容器不同，后者是通过键来存储和检索元素。常见的序列容器包括：

1. array<T, N>（数组容器）
2. vector<T>（向量容器）
3. deque<T>（双端队列容器）
4. list<T>（链表容器）
5. forward_list<T>（正向链表容器）

array<T, N>（数组容器）

array<T, N> 是一个 固定大小的容器，它用于存储 N 个类型为 T 的元素。这个容器的大小在编译时就已经确定，不能动态调整。

特点：

• 固定大小：大小在声明时指定，并且不能改变。
• 高效访问：提供与 C 风格数组一样的常数时间访问。
• 不支持动态增加或删除元素：只能修改已存在的元素。

vector<T>（向量容器）

vector<T> 是一个 动态大小的序列容器，允许在尾部插入和删除元素。它会自动扩展其大小，当存储空间不足时会申请更多的内存。

特点：

• 动态大小：可以根据需要增加或减少元素，自动调整容量。
• 尾部操作高效：在尾部添加或删除元素的时间复杂度为 O(1)。
• 中间操作效率较低：在中间位置插入或删除元素的时间复杂度为 O(n)，其中 n 为容器大小。

deque<T>（双端队列容器）

deque<T> 是一个 双端队列，它允许在两端进行高效的插入和删除操作。与 vector 相似，deque 也允许动态调整大小，但它在两端操作上更为高效。

特点：

• 两端操作高效：插入和删除操作的时间复杂度为 O(1)，无论是在头部还是尾部。
• 中间操作效率较低：在容器中间插入或删除元素的时间复杂度为 O(n)。

list<T>（链表容器）

list<T> 是一个 双向链表，它支持在任何位置插入或删除元素。在这个容器中，每个元素都包含指向前后元素的指针，因此在任意位置的插入和删除操作都是高效的。

特点：

• 插入和删除操作高效：在容器的任意位置进行插入或删除操作的时间复杂度为 O(1)。
• 访问效率较低：由于链表是由节点组成的，每次访问元素都需要从头部或尾部开始遍历，时间复杂度为 O(n)。

forward_list<T>（正向链表容器）

forward_list<T> 是一个 单向链表，与 list<T> 类似，但它只允许从头部访问元素，因此内存开销更小，效率更高。

特点：

• 节省内存：每个节点只有一个指向下一个节点的指针，比双向链表的 list<T> 更节省内存。
• 仅能从前向访问：只能从头部开始访问元素，无法在中间进行双向访问。

总结

C++ STL 中的 序列容器 提供了多种存储数据的方式，每种容器都有其特点，适用于不同的场景：

1. array<T, N>：固定大小，适用于数据大小已知且不可改变的场景。
2. vector<T>：动态大小，适合需要高效尾部操作的场景。
3. deque<T>：双端操作高效，适合两端操作频繁的场景。
4. list<T>：双向链表，适合需要在中间频繁插入或删除元素的场景。
5. forward_list<T>：单向链表，比 list 更节省内存，适合仅从头部访问元素的场景。

4.3 关联式容器（Associative Containers）

关联式容器是 C++ STL 中的一类容器，它们按照一定的规则（通常是基于 红黑树 或其他平衡二叉搜索树）自动排序和存储元素。这些容器提供了高效的基于键的查找、插入和删除操作。关联式容器的主要特点是它们可以通过 键 来访问存储的元素，而不是通过索引，这使得它们在许多应用中非常有用，尤其是在需要快速查找的场景中。

常见的关联式容器：

1. set
2. map
3. multiset
4. multimap

set 容器

set 是一个存储 唯一元素的集合 的容器，它按照元素的键进行自动排序，并且不允许重复元素。set 使用红黑树或平衡二叉搜索树实现，确保元素始终按照顺序排列。

特点：

• 元素唯一：不允许重复元素。
• 元素有序：元素按键的顺序自动排序。
• 查找、插入、删除操作的时间复杂度是 O(log n)，其中 n 是容器中的元素数量。

• 即使插入了重复的元素（如两个 1），set 仍然会保持元素的唯一性，并自动排序。

map 容器

map 是一个 键值对集合，每个键都与一个值相关联，且每个键必须是唯一的。map 使用键对元素进行排序，并提供根据键进行快速查找的功能。

特点：

• 存储键值对：每个元素是一个 key-value 对。
• 键唯一：每个键在 map 中只能出现一次。
• 有序：元素按键的顺序自动排序。
• 查找、插入、删除操作的时间复杂度为 O(log n)。

• 键 1、2、3 自动按升序排列，map 存储键值对，按键的顺序输出。

multiset 容器

multiset 是类似于 set 的容器，不同之处在于它 允许重复元素。multiset 同样使用红黑树或平衡二叉搜索树来保证元素的自动排序。

特点：

• 元素可以重复：multiset 允许存储多个相同的元素。
• 元素有序：元素按照键的顺序自动排序。
• 查找、插入、删除操作的时间复杂度为 O(log n)。

• 与 set 不同，multiset 允许存储重复元素，且仍然会自动排序。

multimap 容器

multimap 是类似于 map 的容器，但它 允许多个相同的键。每个键可以关联多个值，这使得 multimap 与 map 的区别在于键的重复性。

特点：

• 存储键值对：每个元素是一个 key-value 对。
• 键可以重复：多个相同的键可以有不同的值。
• 有序：元素按键的顺序自动排序。
• 查找、插入、删除操作的时间复杂度为 O(log n)。

• 键 2 对应多个值（banana 和 orange），因此 multimap 允许重复的键值对。

总结

关联式容器是 C++ STL 中的一个重要部分，它们利用排序和高效的查找机制来处理数据。以下是四个常见的关联式容器的对比：

1. set：存储唯一的、有序的元素，自动排序。
2. map：存储唯一的键值对，按键排序。
3. multiset：存储重复的、有序的元素，允许重复元素。
4. multimap：存储重复的键值对，允许重复键。

这些容器使用红黑树或平衡二叉搜索树来实现高效的查找、插入和删除操作，时间复杂度通常为 O(log n)，非常适合需要按顺序存储和快速查找的场景。

4.4 无序关联式容器（Unordered Associative Containers）

无序关联式容器是 C++ STL 中的一类容器，类似于关联式容器，但它们不按照顺序存储元素，而是通过 哈希表 来存储数据。这些容器提供常数时间复杂度的查找效率（理论上为 O(1)，实际可能因哈希冲突而变差），但它们并不保证元素的顺序。

无序关联式容器通常提供比关联式容器更高效的查找操作，但由于使用哈希表存储数据，元素的存储顺序是无法预测的。

常见的无序关联式容器

• unordered_set：存储唯一元素的集合，不按顺序存储。
• unordered_map：存储键值对（key-value pairs），不按顺序存储。
• unordered_multiset：与 unordered_set 类似，允许重复元素。
• unordered_multimap：与 unordered_map 类似，允许多个相同的键。

这些容器通常通过 哈希表 来实现，提供高效的插入、删除和查找操作。

unordered_set 示例

unordered_set 用于存储 唯一的元素，并且元素不按顺序存储。

• unordered_set 自动去除重复元素，因此 10 和 20 只会出现一次。
• 元素的输出顺序是不确定的，因为 unordered_set 使用哈希表存储，哈希表不保证元素顺序。

unordered_map 示例

unordered_map 用于存储 键值对（key-value pairs），不按顺序存储。

• unordered_map 存储了键值对，每个键必须是唯一的。
• 输出顺序是不确定的，因为 unordered_map 使用哈希表来存储元素，哈希表不保证按键的顺序输出。

unordered_multiset 示例

unordered_multiset 允许存储重复的元素，并且元素不按顺序存储。

• unordered_multiset 允许存储重复元素，因此容器中有多个 3 和 2。
• 输出顺序是不确定的，因为 unordered_multiset 使用哈希表，哈希表不保证元素的顺序。

unordered_multimap 示例

unordered_multima 与 类似，但允许 存在。