[数据结构与算法]C++ STL学习路线及笔记

什么是STL

C++ STL（标准模板库）是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，这些模板类和函数可以实现多种流行和常用的算法和数据结构，如向量、链表、队列、栈。

C++ 标准模板库的核心包括以下三个组件：容器、算法、迭代器。

容器

???????STL学习笔记 - pyyyyyy - 博客园 (cnblogs.com)

vector 是采用倍增思想实现增强型数组；

queue?基本数据结构队列，先进先出；

stack?基本数据结构——栈，先进后出；

string 定义了对字符串操作的一些方法；

priority_queue 队列的扩展——优先队列，存入的数据默认按照从大到小排序，还可自定义；

deque 队列扩展——双端队列，双端队列中的元素既可以从队首进/出队，也可以从队尾进/出队，可支持像数组下标的方式随机访问；

set?数组扩展——其内部元素默认按升序排列，且具有元素不可重复的性质；

multiset?set集合扩展——有序多重集合，和set不同的是其中元素可以重复；

bitset?内部存储的是01串，可以被看作一个bool数组，它比bool数组更优秀的优点是：节约空间，节约时间，支持基本的位运算。

map?双列数据结构，是一个映射容器有键值和映照数据两个部分组成；和map类似的还有pair；

算法

(33条消息) C++ STL 常见算法(比较详细)_xyqqwer的博客-CSDN博客_c++算法

查找算法

find / find_if

统计算法

count / count_if

可变序列算法

复制 copy

替换 replace

填充?fill

随机生成 generate

移除 remove / unique

排序算法?

字典序排序?sort

随机排序 random_shuffle

反转 reverse

旋转排序 rotate

合并并排序 merge

关系算法

判断两个区间元素是否相等 equal

判断是否有包含关系 includes

求最大/最小元素下标 max_element / min_element

迭代器

正向迭代器?容器类名::iterator? 迭代器名;

反向迭代器?容器类名::reverse_iterator? 迭代器名;

迭代器遍历：

for (vector<int>::reverse_iterator i = v.rbegin(); i != v.rend(); ++i)
     cout << *j << " ";

随机访问迭代器：随机访问迭代器具有双向迭代器的全部功能。若 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：

• p+=i：使得 p 往后移动 i 个元素。
• p-=i：使得 p 往前移动 i 个元素。
• p+i：返回 p 后面第 i 个元素的迭代器。
• p-i：返回 p 前面第 i 个元素的迭代器。
• p[i]：返回 p 后面第 i 个元素的引用。

辅助函数

• advance(p, n)：使迭代器 p 向前或向后移动 n 个元素。
• distance(p, q)：计算两个迭代器之间的距离，即迭代器 p 经过多少次 + + 操作后和迭代器 q 相等。如果调用时 p 已经指向 q 的后面，则这个函数会陷入死循环。
• iter_swap(p, q)：用于交换两个迭代器 p、q 指向的值。