【C++】STL快速入门基础

---

STL（Standard Template Library）

1、一般介绍

STL（Standard Template Library）是一个具有工业强度的、高效的C++程序库，被容纳于C++标准程序库中，是ANSI/ISO C++标准中最新的一部分。STL包含了在计算机科学领域常用的基本数据结构和基本算法，为广大C++程序员提供了一个可扩展的应用框架，高度体现了软件的可复用性。

STL在逻辑层次上体现了泛型化程序设计的思想，引入了诸多新的名词，如需求（requirements）、概念（concept）、模型（model）、容器（container）、算法（algorithmn）、迭代子（iterator）等。与OOP（object-oriented programming）中的多态（polymorphism）一样，泛型也是一种软件的复用技术。

在实现层次上，整个STL是以一种类型参数化（type parameterized）的方式实现的，基于一个在早先C++标准中没有出现的语言特性–模板（template）。如果查阅任何一个版本的STL源代码，你就会发现，模板作为构成整个STL的基石是一件千真万确的事情。除此之外，还有许多C++的新特性为STL的实现提供了方便。

2、STL的六大组件

STL的六大组件包括：

1. 容器（Container）：包括序列式容器（Sequence containers）和关联式容器（Associated containers）。

   • 序列式容器：每个元素有固定位置，如vector、deque、list。
   • 关联式容器：元素位置取决于特定的排序准则，如set、multiset、map、multimap。

2. 迭代器（Iterator）：提供访问容器中对象的方法，包括iterator、const_iterator、reverse_iterator和const_reverse_iterator。

3. 算法（Algorithm）：用于操作容器中的数据，如sort()、find()等，与操作的数据结构和类型无关，可在各种数据结构上使用。

4. 仿函数（Function object）：重载了()操作符的struct，用于自定义操作。

5. 迭代适配器（Adaptor）：用于在不同的迭代器之间进行转换。

6. 空间配置器（Allocator）：用于对象的创建与销毁、内存的获取与释放。

STL的容器比较包括vector、deque、list、set、multiset、map、multimap等，各自具有不同的特点和适用场景。迭代器模式提供了一种方法顺序访问一个聚合对象中的元素，而不需暴露该对象的内部表示，提高了代码的灵活性和复用性。

2.1、STL容器

STL（标准模板库）提供了多种容器，用于存储和管理数据。常见的STL容器包括以下几种：

1. 序列式容器（Sequence Containers）：

   • vector：动态数组，支持快速随机访问，尾部插入/删除速度快，中间插入/删除较慢。
   • deque：双端队列，支持快速随机访问，首尾插入/删除速度快，中间插入/删除较慢。
   • list：双向链表，不支持随机访问，任意位置插入/删除速度快。

2. 关联式容器（Associative Containers）：

   • set：集合，内部元素按照某种规则自动排序，元素值唯一。
   • multiset：多重集合，内部元素按照某种规则自动排序，可以有重复元素。
   • map：映射，键值对集合，内部元素按照键值排序，键值唯一。
   • multimap：多重映射，键值对集合，内部元素按照键值排序，可以有重复键值。

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

   • unordered_set：无序集合，内部元素不按照特定顺序存储，元素值唯一。
   • unordered_multiset：无序多重集合，内部元素不按照特定顺序存储，可以有重复元素。
   • unordered_map：无序映射，键值对集合，内部元素不按照特定顺序存储，键值唯一。
   • unordered_multimap：无序多重映射，键值对集合，内部元素不按照特定顺序存储，可以有重复键值。

4. 容器适配器（Container Adapters）：

   ​ 实际上是容器适配器（container adapter），它们并非真正的容器，而是对底层容器（如vector、deque、list等）进行了封装，提供了特定的功能接口。

   • stack：栈，基于底层容器实现的栈数据结构。
   • queue：队列，基于底层容器实现的队列数据结构。
   • priority_queue：优先队列，基于堆（heap）实现的优先队列数据结构。

每种容器都有其特定的使用场景和性能特点，选择合适的容器可以提高程序的效率和可维护性。

各容器的比较：

容器	数据结构	随机存取	搜索速度（时间复杂度）	快速插入移除
vector	动态数组	Yes	O(1)	尾部
deque	数组的数组	Yes	O(1)	首尾
list	双向链表	No	O(n)	任何位置
set	红黑树	No	O(log n)	–
map	红黑树	Yes(key)	O(log n)	–
unordered_map	哈希表	Yes	O(1)	–
unordered_set	哈希表	No	O(1)	–
stack	deque	Yes	O(1)	尾部
queue	deque	Yes	O(1)	首部
priority_queue	vector(heap)	Yes	O(log n)	–

2.2、STL迭代器

Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素,而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。

迭代器的作用：能够让迭代器与算法不干扰的相互发展，最后又能无间隙的粘合起来，重载了***，＋＋，＝＝，！＝，＝**运算符。用以操作复杂的数据结构，容器提供迭代器，算法使用迭代器；

常见的一些迭代器的种类包括：

• Input Iterator：从容器中读取元素，只能一次读入一个元素向前移动，只支持一遍算法。
• Output Iterator：向容器中写入元素，只能一次一个元素向前移动，只支持一遍算法。
• Forward Iterator：组合输入迭代器和输出迭代器的功能，并保留在容器中的位置。
• Bidirectional Iterator：组合正向迭代器和逆向迭代器的功能，支持多遍算法。
• Random Access Iterator：组合双向迭代器的功能与直接访问容器中任何元素的功能，可以向前向后跳过任意个元素。

上述5种迭代器的继承关系如下图所示：

要注意，上面这图表并不是表明它们之间的继承关系：而只是描述了迭代器的种类和接口。处于图表下层的迭代器都是相对于处于图表上层迭代器的扩张集。例如：forward迭代器不但拥有input和output迭代器的所有功能，还拥有更多的功能。

迭代器一般声明使用示例

vector<T>::iterator it;
list<T>::iterator it;
deque<T>::iterator it；

每种迭代器均可进行包括表中前一种迭代器可进行的操作

迭代器操作	说明
所有迭代器
p++	后置自增迭代器
++p	前置自增迭代器
输入迭代器
*p	复引用迭代器，作为右值
p=p1	将一个迭代器赋给另一个迭代器
p==p1	比较迭代器的相等性
p!=p1	比较迭代器的不等性
输出迭代器
*p	复引用迭代器，作为左值
p=p1	将一个迭代器赋给另一个迭代器
正向迭代器	提供输入输出迭代器的所有功能
双向迭代器
--p	前置自减迭代器
p--	后置自减迭代器
随机迭代器
p+=i	将迭代器递增i位
p-=i	将迭代器递减i位
p+i	在p位加i位后的迭代器
p-i	在p位减i位后的迭代器
p[i]	返回p位元素偏离i位的元素引用
p<p1	如果迭代器p的位置在p1前，返回true，否则返回false
p<=p1	p的位置在p1的前面或同一位置时返回true，否则返回false
p>p1	如果迭代器p的位置在p1后，返回true，否则返回false
p>=p1	p的位置在p1的后面或同一位置时返回true，否则返回false

2.3、相关容器的函数

vector

• 变长数组，采用倍增的思想。
• size(): 返回元素个数。
• empty(): 返回是否为空。
• clear(): 清空容器。
• front()/back(): 返回第一个/最后一个元素。
• push_back()/pop_back(): 在尾部插入/删除一个元素。
• begin()/end(): 返回迭代器指向容器的起始/末尾位置。
• []: 支持下标访问，按照顺序访问元素。
• 支持比较运算，按照字典序排序。

pair

• 存储一对值，通常用于存储一对相关联的数据。
• first: 第一个元素。
• second: 第二个元素。
• 支持比较运算，以first为第一关键字，以second为第二关键字（按照字典序）。

string

• 字符串容器。
• size()/length(): 返回字符串长度。
• empty(): 返回是否为空。
• clear(): 清空字符串。
• substr(start, length): 返回子串。
• c_str(): 返回字符串所在字符数组的起始地址。

queue

• 队列容器。
• size(): 返回队列中元素个数。
• empty(): 返回是否为空。
• push(val): 向队尾插入一个元素。
• front(): 返回队头元素。
• back(): 返回队尾元素。
• pop(): 弹出队头元素。

priority_queue

• 优先队列容器，默认是大根堆。
• size(): 返回优先队列中元素个数。
• empty(): 返回是否为空。
• push(val): 插入一个元素。
• top(): 返回堆顶元素。
• pop(): 弹出堆顶元素。
• 可以定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;。

stack

• 栈容器。
• size(): 返回栈中元素个数。
• empty(): 返回是否为空。
• push(val): 向栈顶插入一个元素。
• top(): 返回栈顶元素。
• pop(): 弹出栈顶元素。

deque

• 双端队列容器。
• size(): 返回双端队列中元素个数。
• empty(): 返回是否为空。
• clear(): 清空双端队列。
• front()/back(): 返回第一个/最后一个元素。
• push_back()/pop_back(): 在尾部插入/删除一个元素。
• push_front()/pop_front(): 在头部插入/删除一个元素。
• begin()/end(): 返回迭代器指向容器的起始/末尾位置。
• []: 支持下标访问，按照顺序访问元素。

set, map, multiset, multimap

• 基于平衡二叉树（红黑树）的动态维护有序序列容器。
• size(): 返回容器中元素个数。
• empty(): 返回是否为空。
• clear(): 清空容器。
• begin()/end(): 返回迭代器指向容器的起始/末尾位置。
• ++, --: 返回前驱和后继，时间复杂度 O(logn)。
• insert(): 插入一个元素。
• find(): 查找一个元素。
• count(): 返回某个元素的个数。
• erase(): 删除元素，支持输入一个元素值或一个迭代器。
• lower_bound()/upper_bound(): 返回大于等于/大于某个值的最小元素的迭代器。

unordered_set, unordered_map, unordered_multiset, unordered_multimap

• 哈希表容器。
• 增删改查的时间复杂度是 O(1)。
• 不支持 lower_bound()/upper_bound()，迭代器的 ++, --。

bitset

• 位集合容器，用于处理位操作。
• bitset<10000> s;
• 支持位运算操作 ~, &, |, ^, >>, <<.
• 支持比较操作 ==, !=.
• 支持 [] 访问操作。
• count(): 返回有多少个1。
• any(): 判断是否至少有一个1。
• none(): 判断是否全为0。
• set(): 把所有位设置为1。
• set(k, v): 将第k位设置为v。
• reset(): 把所有位设置为0。
• flip(): 对所有位取反，等价于 ~。
• flip(k): 对第k位取反。

3、STL算法概述

STL（Standard Template Library）算法是C++标准模板库的核心部分，提供了丰富的算法来操作各种容器。STL算法主要由头文件<algorithm>, <numeric>, <functional>组成。要使用STL中的算法函数必须包含头文件<algorithm>，对于数值算法需要包含<numeric>，<functional>中定义了一些模板类，用来声明函数对象。

STL中的算法大致可以分为以下四类：

1. 非可变序列算法：不直接修改其所操作的容器内容的算法。
2. 可变序列算法：可以修改其所操作的容器内容的算法。
3. 排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
4. 数值算法：对容器内容进行数值计算。

学习算法详细使用方法：cplusplus

查找算法

• adjacent_find: 在迭代器对标识的元素范围内，查找一对相邻重复元素，找到则返回指向这对元素的第一个迭代器，否则返回末尾迭代器。
• binary_search: 在有序序列中查找值，找到返回true。重载版本使用自定义比较函数对象或函数指针来判断相等。
• count: 返回与指定值相等的元素个数。
• count_if: 返回使谓词函数返回true的元素个数。
• equal_range: 返回一对迭代器，第一个表示第一个大于或等于特定值的元素，第二个表示第一个大于特定值的元素。
• find: 在指定范围内查找值，返回第一个匹配元素的迭代器。
• find_end: 在指定范围内查找最后一次出现子序列的位置。
• find_first_of: 在指定范围内查找另一个序列中任意元素的第一次出现位置。
• find_if: 返回第一个使谓词函数返回true的元素的迭代器。
• lower_bound: 返回第一个大于或等于特定值的元素的迭代器。
• upper_bound: 返回第一个大于特定值的元素的迭代器。
• search: 在指定范围内查找子序列的第一次出现位置。
• search_n: 在指定范围内查找连续出现n次的值。

排序和通用算法

• inplace_merge: 合并两个有序序列。
• merge: 合并两个有序序列到另一个序列。
• nth_element: 重新排序使得第n个元素是第n个最小的元素。
• partial_sort: 对序列做部分排序。
• partial_sort_copy: 类似于partial_sort，不过结果保存到另一个容器。
• partition: 对序列进行划分。
• random_shuffle: 随机排列序列。
• reverse: 反转序列。
• reverse_copy: 类似于reverse，不过结果保存到另一个容器。
• rotate: 循环移动元素。
• rotate_copy: 类似于rotate，不过结果保存到另一个容器。
• sort: 对序列排序。
• stable_sort: 稳定排序。
• stable_partition: 稳定划分序列。

删除和替换算法

• copy: 复制序列。
• copy_backward: 与copy相同，不过元素以相反顺序被拷贝。
• iter_swap: 交换两个迭代器指向的元素。
• remove: 删除值相等的元素，不改变容器大小。
• remove_copy: 将不匹配元素复制到另一个容器。
• remove_if: 删除满足条件的元素，不改变容器大小。
• remove_copy_if: 将不匹配元素复制到另一个容器。
• replace: 替换所有等于特定值的元素。
• replace_copy: 类似于replace，结果保存到另一个容器。
• replace_if: 替换满足条件的元素。
• replace_copy_if: 类似于replace_if，结果保存到另一个容器。
• swap: 交换两个元素或容器。
• swap_range: 交换两个范围内的元素。
• unique: 删除连续的重复元素，不改变容器大小。
• unique_copy: 类似于unique，结果保存到另一个容器。

排列组合算法

• next_permutation: 生成下一个排列。
• prev_permutation: 生成上一个排列。

算术算法

• accumulate: 计算序列元素的累加值。
• partial_sum: 计算部分和。
• inner_product: 计算内积。
• adjacent_difference: 计算相邻元素的差值。

生成和异变算法

• fill: 用特定值填充序列。
• fill_n: 用特定值填充n个元素。
• for_each: 对每个元素执行操作。
• generate: 用生成器填充序列。
• generate_n: 用生成器填充n个元素。
• transform: 应用操作到每个元素，并生成结果。

关系算法

• equal: 比较两个序列是否相等。
• includes: 检查一个序列是否包含另一个序列。
• lexicographical_compare: 比较两个序列的字典顺序。
• max: 返回两个元素中的较大者。
• max_element: 返回最大元素的迭代器。
• min: 返回两个元素中的较小者。
• min_element: 返回最小元素的迭代器。
• mismatch: 找到两个序列不匹配的位置。

集合算法

• set_union: 计算两个集合的并集。
• set_intersection: 计算两个集合的交集。
• set_difference: 计算两个集合的差集。
• set_symmetric_difference: 计算两个集合的对称差集。

堆算法

• make_heap: 创建一个堆。
• pop_heap: 移除堆顶元素。
• push_heap: 添加一个新元素到堆中。
• sort_heap: 对堆进行排序。

相关推荐：

《STL源码剖析》 - 作者：侯捷

《C++ Primer》 - 作者：Stanley B. Lippman， Josée Lajoie， Barbara E. Moo