STL(Standard Template Library)
程序员文章站
2022-03-28 18:13:33
常用容器: 1)顺序容器 vertor: 可变大小数组 随机访问(索引)、尾部快、头和中间慢(插入时,位置后的元素都得改变) deques(double-ended queue): 双端队列 随机访问(索引)、头尾快、中间慢(同上) list:双向链表 顺序访问 任何位置都快(内部只需调整一下指针) ......
容器(Containers) | list、deque、vector、map、set等 |
算法(Algorithms) | 算法作用于容器,它们提供了执行各种操作的方式。包括了对容器的初始化、排序、搜索和转化等操作 |
迭代器(iterators) | 用于遍历元素,这些集合可能是容器也可能是容器的子集 |
仿函数(Function object) | 仿函数又称函数对象,其实就是重载了()的struct |
迭代适配器(Adaptor) | |
空间配置器(Allocator) | 作用:1、对象的创建于销毁 2、内存的获取与释放 |
常用容器:
1)顺序容器
vertor: 可变大小数组 随机访问(索引)、尾部快、头和中间慢(插入时,位置后的元素都得改变)
deques(double-ended queue): 双端队列 随机访问(索引)、头尾快、中间慢(同上)
list:双向链表 顺序访问 任何位置都快(内部只需调整一下指针)
2)关联容器
map:关联数组 key-value
set: 关键字即值
容器 | vector | deques | list | map | set |
内部结构 | DynamicArray | array of arrays | double linked list | binary tree | binary tree |
随机存取 | 是 | 是 | 否 | 是 | 否 |
搜索速度 | 慢 | 慢 | 很慢 | 快 | 快 |
快速插入\移除 | 尾 | 头尾 | 都快 | -- | -- |
迭代器:
重载了*,++,==,!=,=运算符。用以操作复杂的数据结构,容器提供迭代器,算法使用迭代器;
常见的一些迭代器类型:iterator、const_iterator、reverse_iterator和const_reverse_iterator
算法:
STL中算法大致分为四类:
1)非可变序列算法:指不直接修改其所操作的容器内容的算法。
2)可变序列算法:指可以修改它们所操作的容器内容的算法。
3)排序算法:包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
4)数值算法:对容器内容进行数值计算。
适配器:
STL提供了三个容器适配器:queue、priority_queue、stack。这些适配器都是包装了vector、list、deque中某个顺序容器的包装器。注意:适配器没有提供迭代器,也不能同时插入或删除多个元素。