对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实现