Home libstdc++ 的容器实现
Post
Cancel

libstdc++ 的容器实现

前言

好的设计适合用图描述,并且能做到「不言而喻,一目了然」,因此尝试用 UML 来描述 libstdc++ 实现

一些注意点:

  1. 图比较大,文章用的是 SVG 格式,你可以通过链接看到高清原图
  2. 一些大家都知道的公有函数不一定会写上,因为这里填上函数名是为了方便跟踪用的
  3. 图要看,代码也要看,这才称得上是健全

源码和注释

请看这里:GitHub/Caturra000/RTFSC/libstdc++

shared_ptr

shared_ptr

高清大图

TODO: 尚未添加 weak_ptrenable_shared_from_this 的结构

从图中可以看到:

  • 并发安全的处理,线程安全的支持是达到了什么程度
  • 为什么推荐用 std::make_shared
  • custom deleter 是怎样支持的
  • shared_ptr 的额外成本

我还分析了 EASTL 的 shared_ptr 实现,代码结构上会更加直接点:EASTL/shared_ptr

unordered_map

unordered_map

高清大图

unordered_mapUML 图看不出什么,其中很多复杂的类型萃取还得看源码才能理清

虽说实现上有一定独到之处,但是阅读难度太大了,很多时候都需要靠这张图才能看清调用链(因为实现方式是非主流的 GNU-sytle 加上非常离谱的 template)

如果只是需要看特定的 unordered_map 而不是极高灵活性的 _Hashtable,可以参考 libstdc++/unordered_map 下面的一些流程,我都把 template 特化给展开了,方便查阅

其实就算法而言,unordered_map 还是很朴素的,无非就是取余 + next prime + std::hash,即使调用方能通过特化来提高性能,又有谁会写这么复杂的东西

比较好奇的是为啥负载因子是 1.0,为啥它会这么自信(据我了解,这里可以构造特定数据使得 unordered_map 性能急剧下降)

deque

deque

高清大图

相比前面几位重量级,std::deque 内部实现简略太多了

(而且它使用 base 做继承是为了更方便处理异常,没别的意思)

但是,我在想 deque 的分配策略,对于 std::stackstd::queue 这些适配器来说是不是很不利?

简单的来说 deque 喜欢三等分的做法,而那些屏蔽某一端接口(双端变单端)的适配器的 load factor 自然不会高到哪里去

不过我还没细看,只是把想法放在这里

收回前言,应该是不对等的三分,但仍需要跟踪一下 reallocate 后的布局

update. 我看完 reallocate 了,也看懂了它的布局,然而槽点已经写满屏幕了

queue/stack

略,适配器没有资格配得上我做图

vector

vector

高清大图

TO BE CONTINUED

其他待更新,自己一幅幅画很累的

另外严重不推荐 Graphviz,浪费时间

This post is licensed under CC BY 4.0 by the author.
Contents