C++ STL 容器重要概念

2021-03-27 15:27

阅读：375

标签：基本 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

下一篇：Javascript之confirm的用法

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：C++ STL 容器重要概念
文章链接：http://soscw.com/index.php/essay/68635.html

亲，登录后才可以留言！

C++ STL 容器重要概念

如何定义

内存分配

时间复杂度

迭代器

评论

热门文章

推荐文章

最新文章

置顶文章