前言
好的设计适合用图描述,并且能做到「不言而喻,一目了然」,因此尝试用 UML
来描述 libstdc++
实现
一些注意点:
- 图比较大,文章用的是 SVG 格式,你可以通过链接看到高清原图
- 一些大家都知道的公有函数不一定会写上,因为这里填上函数名是为了方便跟踪用的
- 图要看,代码也要看,这才称得上是健全
源码和注释
请看这里:GitHub/Caturra000/RTFSC/libstdc++
shared_ptr
TODO: 尚未添加 weak_ptr
和 enable_shared_from_this
的结构
从图中可以看到:
- 并发安全的处理,线程安全的支持是达到了什么程度
- 为什么推荐用
std::make_shared
custom deleter
是怎样支持的shared_ptr
的额外成本
我还分析了 EASTL 的 shared_ptr
实现,代码结构上会更加直接点:EASTL/shared_ptr
unordered_map
unordered_map
用 UML
图看不出什么,其中很多复杂的类型萃取还得看源码才能理清
虽说实现上有一定独到之处,但是阅读难度太大了,很多时候都需要靠这张图才能看清调用链(因为实现方式是非主流的 GNU-sytle
加上非常离谱的 template)
如果只是需要看特定的 unordered_map
而不是极高灵活性的 _Hashtable
,可以参考 libstdc++/unordered_map 下面的一些流程,我都把 template 特化给展开了,方便查阅
其实就算法而言,unordered_map
还是很朴素的,无非就是取余 + next prime + std::hash
,即使调用方能通过特化来提高性能,又有谁会写这么复杂的东西
比较好奇的是为啥负载因子是 1.0,为啥它会这么自信(据我了解,这里可以构造特定数据使得 unordered_map
性能急剧下降)
deque
相比前面几位重量级,std::deque
内部实现简略太多了
(而且它使用 base
做继承是为了更方便处理异常,没别的意思)
但是,我在想 deque
的分配策略,对于 std::stack
和 std::queue
这些适配器来说是不是很不利?
简单的来说 deque
喜欢三等分的做法,而那些屏蔽某一端接口(双端变单端)的适配器的 load factor
自然不会高到哪里去
不过我还没细看,只是把想法放在这里
收回前言,应该是不对等的三分,但仍需要跟踪一下 reallocate
后的布局
update. 我看完 reallocate 了,也看懂了它的布局,然而槽点已经写满屏幕了
queue/stack
略,适配器没有资格配得上我做图
vector
TO BE CONTINUED
其他待更新,自己一幅幅画很累的
另外严重不推荐 Graphviz,浪费时间