STL是Standard Template Library的简称,中文名标准模板库,可以理解为是一堆被封装过的数据结构的集合,与上课学习的数据结构不同,这个系列的主要作用是如何使用这些数据结构来对我们所写的算法进行加速。

容器名称特性
vector向量动态数组
list列表双链表
forward_list单向列表单链表
stack后进先出
queue队列先进先出
deque双端队列两端可操作
priority_queue优先级队列优先级
set集合底层实现为红黑树
multiset多重集合可以重复存放元素
map映射键-->值的映射
multimap多重映射一个元素映射到多个值
unordered_set无序集合字典(常数时间)
unordered_multiset无序多重集合
unorderd_map无序映射键-->值
unorderd_multimap无序多重映射

数据结构是算法的加速剂,一个小例子:

算法场景:现在有约10m左右的英文序列,长度为止,逆置序列存为文本文本文件

ADT(抽象数据类型): 栈
DS(数据结构实现): vector, deque, list 使用vector所需要的时间是最少的
调优(空间换时间): 10m左右的序列,可以将初始空间预留20m,vector底层实现是当存储空间快用完时做一次加倍的扩容,有兴趣的同学可以看看邓俊辉的那本数据结构。

立志成为一名攻城狮
最后更新于 2020-01-02