STL 的设计理解和杂谈

这是在这个博客里的第一个杂谈类的帖子，目标是不想出现过多的代码，而是多取谈一谈在这中间遇到的一些问题，和自己对一些设计的理解。
下文中提到的 STL 可能均为书中使用的 SGI STL。

内存管理

作为 STL 最基础的设施之一的 allocators，是 STL 设计之初必须要考虑的问题。如果没有空间支配器，访问容器内存的效率将极大的降低。
STL 在设计上采用了两种 allocator，一种是使用内存配置函数 malloc() 进行直接分配的配置器，另一种是为了避免内存碎块降低访问效率而专门设计的 allocator。前者没有什么好谈的，我愿意谈一谈后者。
后者名为 default allocator，内部由 N 个链表构成，这些链表分别包含指向 8 倍数个内存的节点。在节点这种小细节的设计上，采用了我之前从来没有考虑过的联合体，用来减轻链表节点占用额外内存的负担。该 allocator 主要是完成对无用内存的回收，去替代更底层的 free() 防止内存区域破碎。因为这里不谈代码，过多的也就详见代码部分了。
对于内存管理这块的设计（对应我的版本的 memory 目录下的 hpp headers），因为 STL 的版本较低，没有过多地见到设计模式的东西，代码也较为简单，于是需要总结的技巧并没有太多。首先是关于模块化，对于“低耦合，高内聚”，STL 的理解是非常深刻的，设计的处处均能体会出这样的思想。其次是在细节上，SGI STL 是参考了 STL 的接口标准，但其实想一想 C++ 标准库 STL 在设计之初一定是先统一接口再去实现的，对于大型的工程，必须要先做好需求分析和标准的制定，我没有完成这样的步骤，并且想到东西就往里面加，才导致了 NA_TCL 项目（本科数据结构课程的实验报告内容）的失败。
我看书比较慢，不过有机会还是想拜读一下设计模式和 C++ 标准。

迭代器

迭代器的设计没有什么可多说的，整个类对操作符的设计都是在模仿原生指针（其实智能指针也是这样，这个在 Effective C++ 里已经读到过了）。然后依旧是想提一下有关接口统一的问题。在迭代器设计中，STL 中使用到了一个叫 iterator tag 的标记，用以区分各种迭代器类型。这是巧妙地利用了 C++ 的类型系统而诞生的产物，也就是接下来我想提到的。
traits，利用了 C++ 类型系统和模板编程的一门技术，C++ 的灵魂之一。虽然 C++ 对于动态类型抑或是运行时类型被骂得臭的不行，但是作为甚至达到图灵完备程度的 C++ 子语言之一的模板（这种说法源自侯捷先生翻译的另外一本 Effective C++），为 C++ 提供了一些区别于其他同类型语言的细微的元编程能力。traits 从中诞生了，基于编译时类型的判断。我读过一点英文版的 C++ Templates，但是很多东西因为英语水平和阅读水平实在有限，没有读得太懂。同样，如果有机会想重新读一下这本书的 Part I 和 Part II。有关 traits 具体就不介绍了，代码里才能将问题体现的非常明白。
对于我而言，C++ 的魅力也就在这里。挺尴尬的，我还记得几年前还在写 C 语言的时候，因为不习惯 C++ 的标准库而尽力去避免使用 C++。直到进入大学后开始对 STL 进行了一些了解，然后对 C++ 开始不离不弃。中间我也做过一些 PyTorch 深度学习的简单模型，Python 水平也提升了微少；做了不到 3 个 Lab 的 6.828，因为缺少了一些 xv6 的知识暂且弃坑去读了 APUE（UNIX 环境高级编程）。蛮可笑的是，最后还是回来开始做 STL 了。不知道我对 C++ 的坚持能持续多久，毕竟快两年就要本科毕业了。

线性容器（序列式容器）

一位一位的谈吧。
首先是 vector，这个容器是我在竞赛中使用最多的，不过后来换了原生数组了。最近开始着手实现 STL 才发现，vector 的效率其实低到吐血，这玩意儿真真切切就是一个所谓的 dynamic array，无论是插入操作、删除操作、拷贝操作，反正就是没有常量级复杂度的，效率非常低。蛮尴尬的，之前都没有去了解这些东西。而且 vector 的 iterator 竟然就是普通的指针，这个也是之前所不知道的。
然后是 list，相比 vector 这个反而没什么好说的，因为就是非常非常普通的双向链表。但是 list 提供的成员函数比我想象的要多，比如私有成员 transfer() 竟然可以衍生出那么多算法，真是算大开眼界了。

谈一谈我自己额外的设计

在书中的代码的基础上，我加上了一些额外的内容。这本书比较老了，而我自己实现的版本不需要考虑版本兼容性，甚至我还想使用更高的版本，于是代码中可能出现了下面的内容：

• C++11 的 auto 关键字
• C++17 的 nested namespace
• C++17 的 lambda 参数使用 auto 关键字推导类型
• C++20 的 concept，甚至还无聊，在最开始的时候就弄了个 concept 库（已经弃用）
• … （之后还有什么特别的东西再添加）

另外就是我自己参考书上的代码，和实际的一些需求，设计了单元测试部分，并为它们编写了 Makefile。这个 Makefile 其实是我从我的 APUE 项目中 copied 的，当时设计还花了点功夫，个人觉得还是蛮好的。