数据结构和STL

对stl库string等定义的变量 使用sizeof并不会得到真实的大小, sizeof只会返回相关类中成员的大小

stl等库中使用指针指向真实的数据, sizeof的时候只记录了指针的大小 并不记录指针指向空间的大小

顺序容器 按序访问
array 静态的连续数组
vector 动态的连续数组
deque 双端队列
forward_list 单链表
list 双链表
关联容器 能实现快速查找O(logn)
set 唯一key的集合, 按照key排序
map k v集合, 按照k排序, k是唯一的
multiset key的集合 按照key排序
multimap k v的集合, 按照key排序
无序关联容器 快速查找均摊O(1)最坏O(n)的无序(哈希)数据结构
unordered_set 唯一key的集合, 按照key生成散列
unordered_map 唯一key, k v的集合, 按照key生成散列
unordered_multiset key的集合, 按照key生成散列
unordered_multimap k v的集合, 按照key生成散列
容器适配器 提供顺序容器的不同接口
stack 适配一个容器提供栈 vector deque list满足要求 默认是deque
queue 适配一个容器提供队列 deque list 默认是deque
priority_queue 适配一个容器提供优先级队列 vector deque 默认是 vector

Sequence containers 顺序容器

array

vector

内部数组, 连续存储

deque

内部为多个等长的连续数组, 数组之间不一定连续. 通过一个记录数组顺序的串起这些等长的连续数组(保存各个数组的首地址)

forward_list

单链表

list

双链表

Associative containers 关联容器

内部会自动进行排序 底层红黑树 key不允许重复 提供O(logN)的查找

set

值就是key 值就是元素

不能通过迭代器修改set的值, 修改set的值会导致删除和新建 指针会失效

map

key和value分开 key+value作为一个元素

Unordered associative containers 无序关联容器

内部不会自动进行排序 底层散列表 提供平均O(1)最坏O(N)的查找

Container adaptors 容器适配器

stack

默认使用deque实现

queue

默认使用deque实现

priority_queue

默认使用vector实现