如何自己写一个STL(下)

最近有点忙，忙里抽点空出来把这个系列给补完吧！

前置要求

首先，我再强调一遍，你至少要达到以下的要求：

• 了解 STL，使用过 STL
• 了解模板
• 了解常用数据结构的原理
• 熟练掌握C++基础知识（Effective系列丛书）

并且我推荐在动手之前至少有了解过 C++ 的代码规范，不然以后大量重构的时候就很难受了。

如何开始

具备以上要求之后，就要开始定 Scope 了。首先要明白，标准中并没有 STL 的说法，这里我说的 STL 主要指标准中容器库及算法库的部分，还包括一些内存管理、函数对象等。可以看看在 这个问题 下 @陈硕 的回答。然后想想自己要做到什么程度。

实现顺序

然后我个人建议是按照这样的顺序来写，当然不排除有不按套路出牌的。

Allocator

我们先实现一个空间配置器，用于管理内存的分配回收，对象的构造析构。毕竟你要数据，就要给内存它放。有些童鞋可能会看到 SGI STL 中的实现，用的是内存池，什么自由链表，什么管理内存碎片……哦嚯听起来好x啊！我一开始也是这么做的，直到非常后来才发现这样并无卵用啊！！具体原因不在这里详细谈，只简单的讲一讲。因为用内存池很容易不释放内存还给系统，你会说不是大于xxxx bytes就调用 malloc/free 的吗？这个是这样的没错，但是还有很多是基于 node type 的容器，比如 list / set / map / unordered_* 等，而它们的 node 的大小并不是都一样的，所以不能完全复用，于是还是会分配一大堆的小内存，然后释放不了，全部都堆在池子里面。所以我原来测试的时候内存动不动就上几个G，后来实在是忍受不了内存池的破事了，于是弃用了。直接 new / delete，结果发现，性能反而好了不少……而且，现代的C++标准实现全部都是这样做的，你也不需要有什么疑虑了。因此这个部分，应该很快就可以完成。

迭代器

做完了 Allocator，我推荐先把迭代器的几种类型，以及迭代器的类型萃取呀，和 advance, distance 等常用函数。因为迭代器是算法与容器之间的“粘合剂”，无论是我们的算法还是容器，都是基于迭代器的。所以要先把迭代器的概念做出来。这里就用到了 STL 中常用的 tag 技巧，声明一些空类型，这些类型可以利用模板类型推导，来帮助我们识别我们想要的东西。标准的要求可以看 这里，具体实现可以参考一下 这里 的技巧。

基础函数

然后我推荐先实现一部分基础函数，因为这一部分的函数的使用频率非常的高，要实现容器也是离不开它们的，所以如何实现好这一部分基础函数是非常关键的。主要的我列出来一些：

修改未初始化的空间：

• uninitialized_copy
• uninitialized_copy_n
• uninitialized_fill
• uninitialized_fill_n
• uninitialized_move
• uninitialized_move_n

修改已初始化的空间：

• copy
• copy_backward
• move
• move_backward
• fill
• fill_n

其它常用的：

• swap
• min
• max

能先把这些实现出来就差不多了，还有一些在容器中也会用到的比如 reverse, make_heap, sort_heap 等，可以用到的时候再去实现。

然后你可以先尝试自己先按照自己的理解实现一遍，比如 uninitialized_copy，刚开始，思路会比较单纯，就是给 [first, last) 构造一个值，可能会写成这样（当然你可以写得更好）：

template <typename InputIterator, typename ForwardIterator>
InputIterator
uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result)
{
	for (; first != last; ++first, ++result)
		construct(*result, *first);
	return result;
}

然而你去看看主流标准库的实现，会发现跟你的差别非常巨大！比如看 libcxx 的：

template <class _InputIterator, class _ForwardIterator>
_ForwardIterator
uninitialized_copy(_InputIterator __f, _InputIterator __l, _ForwardIterator __r)
{
    typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
#ifndef _LIBCPP_NO_EXCEPTIONS
    _ForwardIterator __s = __r;
    try
    {
#endif
        for (; __f != __l; ++__f, (void) ++__r)
            ::new (static_cast<void*>(_VSTD::addressof(*__r))) value_type(*__f);
#ifndef _LIBCPP_NO_EXCEPTIONS
    }
    catch (...)
    {
        for (; __s != __r; ++__s)
            __s->~value_type();
        throw;
    }
#endif
    return __r;
}

这个 new 是什么用法？为什么要用 addressof？for 循环里面 ++__r 前面为什么要有 (void) ？以及异常的使用。你才会发现，原来需要考虑的地方还真多。你别说，这些问题还真的是有原因的，贴两个连接：

https://stackoverflow.com/questions/32680208/is-there-any-advantage-of-using-stdaddressof-function-template-instead-of-us
https://github.com/Alinshans/LCPP/blob/master/Note/other.md

所以啊，遇到什么问题，首先应该自己去搜索，学会搜索是很重要的。尤其是掌握 stack overflow 和 google 的使用。

以上我列出来的那些函数，实现都不简单，但是你去看了某个的实现，其它的都可以照猫画瓢。

容器

真的是万事开头难，若不是有经验，第一次都是无从下手，或者写的很糟糕的。我们已经把一些基础的东西写好了，接下来可以实现一些容器了！

要实现一个容器，最重要是要理解其中的数据结构以及添加删除时的操作。一个容器是如何存放数据、如何访问数据、如何添加与删除数据的，这些在脑海里面，都要有个大致的过程。其次要明白，这个容器的要求是什么。比如 vector 容器，要满足 ContiguousContainer，迭代器要符合 RandomAccessIterator，它各种操作，要满足什么样子的时间复杂度。

还有提一下，要不要支持用户自定义分配器(user-defined allocator)是你的选择，支持了破事多一点而已，这不是我的重点，所以我没有支持。

我们可以先从 vector 开始，实现基本的功能，然后逐步扩展。vector 内部并不复杂，就是有一段分配得到的空间，然后我们记录已经使用过的空间，若插入时剩余可用空间够大，就直接插入，否则我们就重新开一个更大的空间，并把原来的数据搬过去，然后再插入。那么你可以选择用“三指针”的形式，也可以使用一个指针+两个大小的形式。我就选择前者吧。我们先把大的框架写出来：

template <typename T>
class Vector
{
public:
	// typedefs ...
	typedef T*       iterator;
	typedef const T* const_iterator;
	// typedefs ...

private:
	iterator _begin;  // 指向当前数据的起始位置
	iterator _end;    // 指向当前数据的结束位置
	iterator _cap;    // 指向可用空间的结束位置

public:
	iterator begin() { return _begin; }
	iterator end()   { return _end; }

	// ...

	void push_back();
	void pop_back();

	iterator insert(const_iterator pos, const T& value);

	iterator erase(const_iterator pos);

	// ...
};

再大的东西，也是由一点点小的东西堆砌起来的。再复杂的系统，也是由一个一个模块实现起来的。再复杂的类，也是由一个一个函数实现起来的。所以只要开始了，其实并不难。并不需要一步到位，功能都是一步一步加上去的。可以对照着 这里 的接口说明，慢慢地去添加接口，完善接口，甚至是完善范围检查，异常安全等方面的内容。

当然自己没有任何参考写出来不是一件简单的事情，你很难考虑的周全。所以我也参考了非常多 msvc、libstdc++ 还有 libcxx 的实现，个人认为阅读这些实现也是一种学习的方法。当然不可以直接照着就抄，而是要多问为什么。为什么要这么实现，不这么实现会怎么样。很多你看似没什么用的操作，其实背后都是有原因的。比如 vector 内存增长的策略，比如 这个问题，你都需要多提问，多思考，才能有较深刻的理解。而据我的体验，我推荐参考 libcxx 的实现，因为它目录结构清晰，代码风格较易阅读，性能更好。

每个容器，接口风格都是差不多的，认认真真实现完第一个之后，后面的就轻车熟路了，当然提前还是一样，要对容器的数据结构熟悉。

再接再厉

然后就是长时间的填坑的过程，把容器库一点一点填好，算法库一个一个写完，这得花上不少的时间。

考虑更多

大致完成之后，如果你还有兴趣，那么还可以考虑更多，如果你觉得到此为止了，那也没有什么所谓，全看你自己的目的。大概还有那些需要考虑的呢？我罗列一些，自己看着办：

• 特化 vector<bool> ?
• 异常安全
• 优化
• 单元测试
• 与标准库的交互
• ……

重构

重构是在所难免的。可能是代码风格混乱，可能是隔一段时间回头看之前写的代码就像一坨*，可能是优化实现，可能是接口扩展。我从第一次写完，到现在，也进行了三次大重构。

重构是一个比较大的话题。以后有机会会详细谈谈，限于篇幅，我这里只简单地谈一下针对这个项目，重构的一些策略。

1. 如何放心大胆的重构

这就体现了单元测试的重要性了。有了单元测试，你才敢放心大胆的重构，当然提前是你单元测试的覆盖率要达到。重构完之后跑一遍单元测试，心里也有点底。

1. 如何重构

根据我的经验，重构的时候尽量不要直接在原来的函数上进行改动，除非是一些小修改。因为很容易你没改好，然后原来的又乱掉了，就很麻烦。所以我建议是用这样的方法：

#if 0
void 原来的函数()
{
	// ...	
}
// 还有其它相关的函数
#elif
void 这里是重构的函数()
{
	// ...
}
#endif

在要重构的函数旁边，重新写，然后用 #if 来控制使用原来的函数还是重构后的函数，等完全重构好之后测试过之后再删除原来的。

其它

要实现一个 tinystl，还有非常多的细节，但我不可能一一讲到。所以如果有什么问题的地方，可以通过 email，qq，甚至是提 issue 的方式来告诉我，只要有空一般我都会回。

以上两篇便是自己的一些心得体会。感谢阅读！