本文讲解C++的STL库设计思路并按照自己的思路大致实现其功能。
本人深知标准库编写大佬的实力，实现的目的只是学习大佬的设计思想并发挥自己的想法。一键访问。

一、STL介绍

按照惯例，先介绍一下STL。STL全称Standard Template Library（标准模板库），是软件开发里最基本的数据结构和算法的一套标准实现。
软件开发过程需要用到的各种数据结构，例如数组、动态数组、优先队列、栈、哈希表…在没有标准之前都是开发者自己动手实现的，重复的工作浪费时间不说，实现的结果也是一言难尽。为了提高效率，实现代码复用，STL在这样的环境下作为标准模板库编写。从此开发者可以更专注地投入到功能实现上，无需再操心数据结构的实现。

1.1 STL组成

STL六大组件：容器、算法、迭代器、仿函数、适配器和空间配置器，共同作用，成就一番大业。
下面介绍一下各组件。
容器：指各种数据结构，如vector（动态数组）、list（链表）、stack（栈）等…并提供了一系列操作，比如insert插入，erase擦除等非常符合直觉的操作，简单易上手，是开发者最直接面对的部分

算法：为容器提供各种常用的算法，如sort（排序）、find（查找元素）、copy（复制）…

迭代器：不同的容器在内存分布上会有所不同，比方说vector（数组）是占用连续的内存，而list（链表）占用分散的内存，这样会导致遍历或者说查找元素的方式会有所不同。为了解决这个问题，迭代器概念应运而生，迭代器重载了自增，自减等常用的运算符，使用起来就好像所有容器都位于连续的内存空间。这样只需要写一次算法就能适配所有容器

仿函数：本质是一个类，但是通过运算符重载使得这个类像一个函数，通过这种方式适配模板编程（暂时迷茫是正常的）

适配器：一种用来修饰容器或者仿函数或迭代器接口的东西（对某些容器进行二次封装实现不同数据结构）

空间配置器：频繁地向操作系统申请，释放内存会造成性能损失。这时可以向操作系统申请大块内存，自行管理，减小调用操作系统api的带来的性能损失。这个管理内存的方式就是空间配置器
STL六大组件的交互关系，容器通过空间配置器取得数据存储空间，算法通过迭代器存储容器中的内容，仿函数可以协助算法完成不同的策略的变化，适配器可以修饰仿函数

1.2 STL优点

STL的一个重要特性是将数据和操作分离。数据由容器类别加以管理，操作则由可定制的算法定义。
开发者可以不了解 STL 具体的实现过程，只要掌握容器的操作方法就可以了。这样可以节省精力，投入到程序开发方面上。这也是代码复用最大的意义
STL 具有高可重用性，高性能，高移植性，跨平台的优点。
因为本篇文章主要是讲解STL的实现，就不再过多介绍表面的内容了。贴一张侯捷老师的图
各容器的关系

二、空间配置器(allocator)

空间配置器是STL的重要组成，有多重要呢？随便找一个容器看看就知道了

$ template <class _Ty, class _Alloc = allocator<_Ty>>
$ class vector
$ {...
$ }

可以看到构造vector的时候有两个参数，一个是数据类型，另一个就是空间配置器，只是空间配置器有默认参数。事实上，几乎所有容器在模板定义时都有默认的内存分配器。
空间配置器真正需要完成的工作有四个，分别是申请内存，释放内存，调用构造函数，调用析构函数。看到这，有的人会说，这不就是 malloc,free还有调用构造函数析构函数吗？
对，没错。空间配置器就是单纯负责这块工作的。
有的人会想，那为什么要写个空间配置器？直接malloc直接free不行吗？
当然不是不行，只是malloc函数会调用操作系统底层的api向内存申请空间，申请的空间经过操作系统严格处理后才返回，频繁的malloc，free会导致性能无畏的消耗。除此之外malloc，free使用起来也不够便利，还给容器开发者带来诸多困扰。编写一个空间配置器，可以一劳永逸地解决内存分配问题，何乐而不为（内存池这个概念用途非常广泛）
接下来的问题是如何实现空间配置器
首先要解决内存碎片问题，造成内存碎片问题的原因是容器在使用过程中会频繁的申请，释放内存。打个比方说我有一块8个字节的内存，但是0，2，4，6这四个字节给存了char型变量，还剩下1，3，5，7共四个字节内存。本来还能存一个int型变量的，可是它不连续，存不了。内存碎片就是这么个问题。目前为止还没有完美的解决方案
但不完美也得尝试解决，目前的方案就是写一个空间配置器，空间配置器向操作系统申请一大块内存，再把这一大块内存细分成几小块，存储的类型分配对应空间的内存池。有点抽象，举个例子。把一大块内存分8块，申请1_{8个字节的类型就返回第一小块里的内存，申请9}16个字节的返回第二块里的内存，以此类推。这样还是会有浪费，但是浪费小很多了。
实际运用中，空间配置器又分一级空间配置器和二级空间配置器。一级分配器称为Allocator，二级分配器称为Alloc。Allocator提供给外部，主要负责释放内存并向Alloc申请内存。Alloc里实现一级配置器、二级配置器，一级空间配置器负责调用构造函数和析构函数，以及向二级空间配置器申请内存，归还内存；二级空间配置器负责响应一级空间配置器的请求，并维护一个自由链表。这个自由链表用来记录内存位置。逻辑不是很复杂，结合注释看代码就行。

三、迭代器（iterator）

刚接触这个名词的时候，可能会有人像我一样疑惑，迭代器是个什么东西？对于这个问题，到现在也没有一个定义清晰准确并且能够说服我的解释。迭代器像是一个指针，可以让用户便捷地访问容器元素，但它又不是一个指针，而是一个类。举个直观的例子，我们都知道链表。链表在内存是不连续的，用户只保存有访问头节点的指针，要访问后续元素，就需要获取头节点所保存的下一个元素的地址，以此类推。这样访问有点麻烦，迭代器就是把访问的方式封装起来，我们只需要对迭代器自增就可以访问下一个元素，用起来很方便。对于每一个容器，不管内存连续还是不连续，我们都用相同方法就可以访问下一个元素，这就是迭代器在发挥作用。对于一个链表a和数组b。

1 2	$ list <int> a(10,1) $ int b[10]

我们可以通过下面方式访问a和b中的元素

$ vector<int>::iterator iter = v.begin()
$ int* pointer = b
$for(int i=0;i<10;++i)
${
$   cout<<*iter<<" "<<*pointer;
$   ++iter;
$   ++pointer;
$}

这种行为很像指针对吧？
迭代器其实就是对指针的封装。迭代器作为一个类，指针则是其中的成员变量，大概率也是唯一的成员变量。C++提供的重载操作符，可以使迭代器达到类似指针的行为。
迭代器分为输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器。
输入迭代器和输出迭代器负责对元素的操作，前向迭代器则是输入迭代器和输出迭代器的派生类，只能单向迭代，双向迭代器则继承了前向迭代器，添加了反向迭代，随机访问迭代器则继承双向迭代器，加入随机访问的功能
现在的实现的过程中，迭代器已经取消标签的概念了。目前每个容器需要单独设计一个专属的迭代器，才能使用头文件algorithm里的算法

四、容器（）

容器是提供给用户直接操作的东西，这部分也应该是用户最熟悉的东西。事实上，对于大部分人来说，只需要掌握容器的使用即可。因为它实在是封装得太好了，好到我啥也不懂拿来就能直接用。学明白数据结构，就明白这些容器了。
不再赘述，直接解释每一个容器，并且都会实现（可能一年也可能十年）

1、array （数组）

array和普通的数组没有很大区别，也要在定义时确定大小，比普通数组就多了迭代器和一些使用方法，包括获取长度，顺序遍历，逆序遍历，交换位置这些。使用场景不多，就不多描述了，可以参考下源码实现。为了提高开发效率可以使用array，但对性能有要求是还是用普通数组好一点。

2、vector （向量）

vector跟普通数组有一些共同点，内存连续，支持下标访问。但更多的是不同点，vector可以看成是动态数组，在定义的时候不需要确定长度。有些人可能会纳闷，怎么实现？计算机居然能相应申请内存大小不确定的指令？其实，所谓动态是相对的，不断地调整静态，让人产生动态的错觉。这一切都是空间配置器在发挥作用，理解了空间配置器，也就理解了vector的实现过程。
下面介绍一下提供的api及用法:
push_back(value)
pop_back(void)
at(position)
emplace(iterator,value)
size(void)
empty()

3、deque （双向队列）

类似vector，内存连续。但比vector多了一个前置插入的操作。维护的时候常需要迁移数组使数组以保持前置后置位都有空余，经过封装可以实现栈和优先队列。

4、list （链表）

前面的几种结构在内存上都是连续的，这样的好处是能够快速的随机访问任何一个元素，但缺点是在容器非首尾插入元素时效率很低。链表与此相反，链表把每一个节点独立出来，节点内包含了数据和下一个节点的地址，这样插入删除节点效率很高，但不能随机访问其中的元素，只能从头结点开始一个一个往下找

5、map（映射）

6、set（集合）

所谓集合其实是对红黑树的封装，红黑树是二叉平衡树的改良

7、

五、仿函数（Functor）

仿函数，本质是一个重载了括号运算符的类，大致定义如下

struct Test
{
    Test() = default;
    ~Test() = default;
    Elemtype operator ()(Elemtype a...)
    {
        //...
    }
}

对括号运算符的重载使得这个类能够像函数一样调用。有的人可能会问，为何多此一举？
这是因为C++模板里不能以函数名作为参数，为了将一个函数当成模板参数传入，所以有了这么一个操作，它是一个类，但是行为像函数，所以叫仿函数。

六、适配器（）

七、补充

除了上述几种容器，STL还包含了许多内容。
比如著名的智能指针。
智能指针本身也是一个模板类，而智能指针的实现是相当巧妙的。我们一起揭开它的面纱。
先以shared_ptr作为例子，看下它的简易版定义。

template<class T>
class shared_ptr
{
public:
    constexpr shared_ptr() noexcept = default;
    constexpr shared_ptr(nullptr_t) noexcept        // construct empty shared_ptr
    {
    }
    constexpr shared_ptr(T* ptr) noexcept
    {
        _ptr = ptr;
        ...                                         //省略对计数器的操作
    }
private:
    T* _ptr;
}

可以看到，shared_ptr的定义非常的质朴，就是对指针的一个封装。除上述代码，后面就是简单的计数和运算符重载。依样画葫芦我们可以写一个unique_ptr，weak_ptr等智能指针。
引入智能指针我们可以不需要再手动释放内存，不过计数方式存在一些bug，我们有时候还是需要普通指针。