超硬核 | 2 万字 20 图带你手撕 STL 序列式容器源码

前言

源码之前，了无秘密。

上一篇，我们剖析了 STL 迭代器源码与 traits 编程技法 ，这一篇我们来学习下容器。

在 STL 编程中，容器是我们经常会用到的一种数据结构，容器分为序列式容器和关联式容器。

两者的本质区别在于：序列式容器是通过元素在容器中的位置顺序存储和访问元素，而关联容器则是通过键 (key) 存储和读取元素。

本篇着重剖析序列式容器相关背后的知识点。

容器分类

前面提到了，根据元素存储方式的不同，容器可分为序列式和关联式，那具体的又有哪些分类呢，这里我画了一张图来看一下。

限于篇幅，这篇文章小贺会来重点讲解一下经常使用到的那些容器，比如 vector，list，deque，以及衍生的栈和队列其背后核心的设计和奥秘，不多 BB， 马上就来分析。

vector

写 C 的小伙伴们，应该对 vector 都非常熟悉了，vector 基本能够支持任何类型的对象，同时它也是一个可以动态增长的数组，使用起来非常的方便。

但如果我问你，知道它是如何做到动态扩容的吗？哎，是不是一时半会答不上来了，哈哈，没事，我们一起来看看。

vector 基本数据结构

基本上，STL 里面所有的容器的源码都包含至少三个部分：

• 迭代器，遍历容器的元素，控制容器空间的边界和元素的移动；
• 构造函数，满足容器的多种初始化；
• 属性的获取，比如 begin()，end()等；

vector 也不例外，其实看了源码之后就发现，vector 相反是所有容器里面最简单的一种。

template <class T, class Alloc = alloc>
class vector {
public:
   // 定义 vector 自身的嵌套型别
    typedef T value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    // 定义迭代器, 这里就只是一个普通的指针
    typedef value_type* iterator;
    typedef const value_type* const_iterator;
    typedef value_type