C++ STL 容器重要概念
2021-03-27 15:27
阅读:474
标签:基本 hash 方式 容器 自定义 长度 gnu table ring
本文所有内容均在 GNU C++ (64位) 里瞎搞出来,有很多猜测,仅供参考
如何定义
vector/deque/list/forward_list >
set , allocator >
map , allocator > >
unordered_set , equal_to, allocator >
unordered_map , equal_to, allocator > >
basic_string/basic_stringstream , allocator >
queue/stack >
priority_queue , less >
array
bitset
内存分配
容器 | sizeof | 扩容方式 | 内存释放方式 |
---|---|---|---|
vector | 24 | 每次两倍 | 不释放 |
deque | 80 | 初始512字节,每次512字节+少量额外内存 | 基本释放 |
list | 16 | 要多少申请多少 | 不留多余内存 |
forward_list | 8 | 要多少申请多少 | 不留多余内存 |
(multi)set/map | 48 | 要多少申请多少 | 不留多余内存 |
unordered_(multi)set/map | 56 | 要多少申请多少+桶的内存 | 桶不释放,其余不留多余内存 |
string | 8 | 每次两倍+少量额外内存 | 不释放 |
stringstream | 368 | 初始512字节,每次两倍+少量额外内存 | 不释放 |
- queue,stack,priority_queue是由其他容器改造过来的(第二个模板参数),queue,stack默认是deque,priority_queue默认是vector
- array,bitset都是固定长度,没有内存分配器,估计和数组行为一致
- list,forward_list,set,map这些链表数据结构(unordered每个桶也是链表),每个结点的指针的内存不通过自定义内存分配器分配。目前初步估计set/map的每个结点有额外24字节(通过鸡兔同笼法),其余懒得算
时间复杂度
-
list
的size()
是 \(O(n)\) 的!(forward_list
干脆不定义这个函数),想用list
代替deque
的同学要注意这个坑点 - 其他复杂度还没发现不正常的
迭代器
- 由其他容器改造的容器(queue,stack,priority_queue)都没有迭代器
- bitset没有迭代器
- stringstream没有迭代器(不考虑特殊迭代器)
C++ STL 容器重要概念
标签:基本 hash 方式 容器 自定义 长度 gnu table ring
原文地址:https://www.cnblogs.com/axiomofchoice/p/13659385.html
上一篇:C语言学习DAY5
评论
亲,登录后才可以留言!