从零开始的 STL 实现记录

前言

从上个月的四号创建 TinySTL以来已经过了一个多月，中间还准备了一场面试放了暑假，鸽了很久。但总之这个亲手实现基本 SGI-STL 的项目终于要完成了！

项目链接：https://github.com/Qlipphoth/TinySTL

在实现 STL 的过程中，我对 C++ 的语法与模板的使用有了更深入的理解，和一个月前确实不可同日而语，只能说 STL 不愧是被称为任何 C++ 初学者都得手搓一两遍的项目。为了加深自己的理解与印象，博主会陆续将 STL 的实现过程与笔记都整理至博客中，方便自己回顾的同时也希望能帮助到后续想要或正在实现 STL 的读者们。

STL 中有六大组件：

Allocator (空间配置器)
Iterator (迭代器)
Container (容器)
Alogorithm (算法)
Functor (仿函数)
Adapter (适配器)

六大组件的相互套用，成就了 STL 强大的功能。值得注意的是，虽然六大组件看似独立，但在实际实现某一组件的过程中，往往会涉及到其他组件的相关内容，如迭代器中的一些操作就使用了算法组件中的一些功能，容器中大量使用的算法与仿函数更甚，且 traits 编程思想贯穿整个 STL 全程。这种现象不可避免，但却会实在地为我们的实现之路造成困扰，特别是 C++ 基础比较薄弱的同学（比如我），在前期的实现过程中总会发现：咦？这个函数怎么没见过，哦，原来需要先实现这个组件；啊？这个模板为什么要这样写，SFINAE是什么意思？这样的困扰。往往就会选择放弃，觉得这么复杂的东西是不可能让我这个菜鸡手搓出来的。但实际上，只要熬过艰难的前期，把一些常用的功能都写好，STL 经常使用的一些编程知识与技巧都了解后，剩下的工作就是顺水推舟了，要简单许多。

博客的逻辑顺序与更新顺序都会按照上述列出的六大组件顺序进行。

参考资料（TODO）

MyTinySTL

GitHub 上 star 数量快 1w 的仓库，基本完整地实现了 SGI-STL 的全部内容，注释详尽且配套了许多的单元测试内容。几乎是你能找到的最好的手搓 STL 的轮子，博主在实现 STL (TinySTL) 过程中参考最多的就是这个项目了，逻辑也基本与该仓库一致，只是对其中一部分做了修改。

值得注意的是，该项目中有一些内容的实现逻辑并非与 SGI-STL 相同，并且适配器部分的许多功能并没有实现，如果想实现原教旨主义的 STL，还请结合其他资料一起互相补充。

文章索引

这里将会列出后续具体实现 STL 的博客索引。

Allocator

Iterator

Container

序列式容器

vector
1. vector
list
deque
1. deque 的结构
2. deque 的函数
stack & queue
1. stack & queue
priority queue
1. heap
2. priority queue

关联式容器

rb-tree
set/multiset、map/multimap
1. set 与 map
hashtable
unordered_set/multiset、unordered_map/multimap
1. unorder_set 与 unordered_map