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

[herongwei]

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

大家好，我是小贺，继续更新 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& reference;
    typedef const value_type& const_reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    ...
  protected:
    typedef simple_alloc<value_type, Alloc> data_allocator;	// 设置其空间配置器
    iterator start;				// 当前使用空间的头
    iterator finish;			// 当前使用空间的尾
    iterator end_of_storage;	// 当前可用空间的尾
    ...
};

因为 vector 需要表示用户操作的当前数据的起始地址，结束地址，还需要其真正的最大地址。所以总共需要 3 个迭代器分别指向：数据的头(start)，数据的尾(finish)，数组的尾(end_of_storage)。

构造函数

vector 有多个构造函数, 为了满足多种初始化。

我们看到，这里面，初始化满足要么都初始化成功， 要么一个都不初始化并释放掉抛出异常，异常机制这块拿捏的死死的呀。

因为 vector 是一种 class template， 所以呢，我们并不需要手动的释放内存， 生命周期结束后就自动调用析构从而释放调用空间，当然我们也可以直接调用析构函数释放内存。

void deallocate() {
	if (start) 
        data_allocator::deallocate(start, end_of_storage - start);
}
// 调用析构函数并释放内存
~vector()  { 
	destroy(start, finish);
	deallocate();
}

属性获取

下面的部分就涉及到了位置参数的获取， 比如返回 vector 的开始和结尾，返回最后一个元素，返回当前元素个数，元素容量，是否为空等。

这里需要注意的是因为 end() 返回的是 finish，而 finish 是指向最后一个元素的后一个位置的指针，所以使用 end() 的时候要注意。

public:
	// 获取数据的开始以及结束位置的指针. 记住这里返回的是迭代器, 也就是 vector 迭代器就是该类型的指针.
    iterator begin() { return start; }
    iterator end() { return finish; }
    reference front() { return *begin(); } // 获取值
    reference back() { return *(end() - 1); } 
    const_iterator begin() const { return start; }// 获取右值
    const_iterator end() const { return finish; }
    
    const_reference front() const { return *begin(); }
    const_reference back() const { return *(end() - 1); }
    
    size_type size() const { return size_type(end() - begin()); }	 // 数组元素的个数
    size_type max_size() const { return size_type(-1) / sizeof(T); }	// 最大能存储的元素个数
    size_type capacity() const { return size_type(end_of_storage - begin()); } // 数组的实际大小
    bool empty() const { return begin() == end(); }	
    //判断 vector 是否为空， 并不是比较元素为 0，是直接比较头尾指针。

push 和 pop 操作

vector 的 push 和 pop 操作都只是对尾进行操作， 这里说的尾部是指数据的尾部。

当调用 push_back 插入新元素的时候，首先会检查是否有备用空间，如果有就直接在备用空间上构造元素，并调整迭代器 finish 。

当如果没有备用空间，就扩充空间(重新配置-移动数据-释放原空间)，这里则是调用了 insert_aux 函数。

在上面这张图里，可以看到，push_back 这个函数里面又判断了一次 finish != end_of_storage 这是因为啥呢？原来这是因为 insert_aux 函数可能还被其他函数调用哦。

在下面的 else 分支里面，我们看到了 vector 的动态扩容机制：如果原空间大小为 0 则分配 1 个元素，如果大于 0 则分配原空间两倍的新空间，然后把数据拷贝过去。

pop 元素

public:
  //将尾端元素拿掉 并调整大小
  void pop_back() {
      --finish;//将尾端标记往前移动一个位置 放弃尾端元素
      destroy(finish);
  }

erase 删除元素

erase 函数清除指定位置的元素， 其重载函数用于清除一个范围内的所有元素。实际实现就是将删除元素后面所有元素往前移动，对于 vector 来说删除元素的操作开销还是很大的，所以说 vector 它不适合频繁的删除操作，毕竟它是一个数组。

//清楚[first, last)中的所有元素
  iterator erase(iterator first, iterator last) {
      iterator i = copy(last, finish, first);
      destroy(i, finish);
      finish = finish - (last - first);
      return first;
  }
  //清除指定位置的元素
  iterator erase(iterator position) {
      if (position + 1 != end()) 
          copy(position + 1, finish, position);//copy 全局函数
      }      
      --finish;
      destroy(finish);
      return position;
  }
  void clear() {
      erase(begin(), end());
  }

我们结合图解来看一下:

清楚范围内的元素，第一步要将 finish 迭代器后面的元素拷贝回去，然后返回拷贝完成的尾部迭代器，最后在删除之前的。

删除指定位置的元素就是实际就是将指定位置后面的所有元素向前移动, 最后析构掉最后一个元素。

insert 插入元素

vector 的插入元素具体来说呢，又分三种情况：

1 、如果备用空间足够且插入点的现有元素多于新增元素；

2 、如果备用空间足够且插入点的现有元素小于新增元素；

3 、如果备用空间不够；

我们一个一个来分析。

• 插入点之后的现有元素个数 > 新增元素个数

• 插入点之后的现有元素个数 <= 新增元素个数

如果备用空间不足

这里呢，要注意一个坑，就是所谓的迭代器失效问题。 通过图解我们就明白了，所谓的迭代器失效问题是由于元素空间重新配置导致之前的迭代器访问的元素不在了，总结来说有两种：

• 由于插入元素，使得容器元素整体迁移导致存放原容器元素的空间不再有效，从而使得指向原空间的迭代器失效；

• 由于删除元素，使得某些元素次序发生变化导致原本指向某元素的迭代器不再指向期望指向的元素。

前面提到的一些全局函数，这里总结一下：

• copy(a,b,c)：将(a,b)之间的元素拷贝到(c,c-(b-a))位置

• uninitialized_copy(first, last, result)： 具体作用是将 [first,last)内的元素拷贝到 result 从前往后拷贝

• copy_backward(first, last, result)： 将 [first,last)内的元素拷贝到 result 从后往前拷贝

vector 总结

到这里呢，vector 分析的就差不多了，最后提醒需要注意的是：vector 的成员函数都不做边界检查 (at 方法会抛异常)，使用者要自己确保迭代器和索引值的合法性。

我们来总结一下 vector 的优缺点。

优点

• 在内存中分配一块连续的内存空间进行存，可以像数组一样操作，动态扩容。
• 随机访问方便，支持下标访问和 vector.at()操作。
• 节省空间。

缺点

• 由于其顺序存储的特性，vector 插入删除操作的时间复杂度是 O(n)。
• 只能在末端进行 pop 和 push 。
• 当动态长度超过默认分配大小后，要整体重新分配、拷贝和释放空间。

vector 的缺点也很明显, 在频率较高的插入和删除时效率就太低了

list

好了，下面我们来看一下 list，list 是一种双向链表。

list 的设计更加复杂一点，好处是每次插入或删除一个元素，就配置或释放一个元素，list 对于空间的运用有绝对的精准，一点也不浪费。而且对于任何位置的元素插入或删除，list 永远是常数空间。

注意：list 源码里其实分了两个部分，一个部分是 list 结构，另一部分是 list 节点的结构。

那这里不妨思考一下，为什么 list 节点分为了两个部分，而不是在一个结构体里面呢? 也就是说为什么指针变量和数据变量分开定义呢？

如果看了后面的源码就晓得了，这里是为了给迭代器做铺垫，因为迭代器遍历的时候不需要数据成员的，只需要前后指针就可以遍历该 list 。　

list 数据结构-节点

__list_node 用来实现节点，数据结构中就储存前后指针和属性。

template <class T> struct __list_node {
    // 前后指针
  	typedef void* void_pointer;
  	void_pointer next;
  	void_pointer prev;
    // 属性
  	T data;
};

来瞅一瞅，list 的节点长啥样，因为 list 是一种双向链表，所以基本结构就是下面这个样子：

基本类型

template<class T, class Ref, class Ptr> struct __list_iterator {
  	typedef __list_iterator<T, T&, T*>     iterator;	// 迭代器
  	typedef __list_iterator<T, const T&, const T*> const_iterator;
  	typedef __list_iterator<T, Ref, Ptr>    self;		
	
    // 迭代器是 bidirectional_iterator_tag 类型
  	typedef bidirectional_iterator_tag iterator_category;
  	typedef T value_type;
  	typedef Ptr pointer;
  	typedef Ref reference;
  	typedef size_t size_type;
  	typedef ptrdiff_t difference_type;
    ... 
};

构造函数

template<class T, class Ref, class Ptr> struct __list_iterator {
    ...
    // 定义节点指针
  	typedef __list_node<T>* link_type;
  	link_type node;
	// 构造函数
  	__list_iterator(link_type x) : node(x) {}
  	__list_iterator() {}
  	__list_iterator(const iterator& x) : node(x.node) {}
   ... 
};

重载

template<class T, class Ref, class Ptr> struct __list_iterator  {
    ...
	// 重载
  	bool operator==(const self& x) const { return node == x.node; }
  	bool operator!=(const self& x) const { return node != x.node; }
    ...

    // ++和--是直接操作的指针指向 next 还是 prev, 因为 list 是一个双向链表
  	self& operator++() { 
	    node = (link_type)((*node).next);
	    return *this;
  	}
  	self operator++(int) { 
	    self tmp = *this;
	    ++*this;
	    return tmp;
  	}
  	self& operator--() { 
	    node = (link_type)((*node).prev);
	    return *this;
  	}
  	self operator--(int)  { 
    	self tmp = *this;
    	--*this;
    	return tmp;
  	}
};

list 结构

list 自己定义了嵌套类型满足 traits 编程，list 迭代器是 bidirectional_iterator_tag 类型，并不是一个普通指针。

list 在定义 node 节点时， 定义的不是一个指针。这里要注意。

template <class T, class Alloc = alloc>
class list {
protected:
    typedef void* void_pointer;
    typedef __list_node<T> list_node;	// 节点
    typedef simple_alloc<list_node, Alloc> list_node_allocator;	// 空间配置器
public:      
    // 定义嵌套类型
    typedef T value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef list_node* link_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    
protected:
    // 定义一个节点, 这里节点并不是一个指针.
    link_type node;
    
public:
    // 定义迭代器
    typedef __list_iterator<T, T&, T*>             iterator;
    typedef __list_iterator<T, const T&, const T*> const_iterator;
	...
};

list 构造和析构函数实现

构造函数前期准备：

每个构造函数都会创造一个空的 node 节点，为了保证我们在执行任何操作都不会修改迭代器。

list 默认使用 alloc 作为空间配置器，并根据这个另外定义了一个 list_node_allocator，目的是更加方便以节点大小来配置单元。

template <class T, class Alloc = alloc>
class list {
protected:
    typedef void* void_pointer;
    typedef __list_node<T> list_node;	// 节点
    typedef simple_alloc<list_node, Alloc> list_node_allocator;	// 空间配置器

其中，list_node_allocator(n)表示配置 n 个节点空间。以下四个函数，分别用来配置，释放，构造，销毁一个节点。

class list {
protected:
	// 配置一个节点并返回
  link_type get_node() { return list_node_allocator::allocate(); }
  // 释放一个节点
  void put_node(link_type p) { list_node_allocator::deallocate(p); }
	// 产生(配置并构造)一个节点带有元素初始值
  link_type create_node(const T& x) {
      link_type p = get_node();
      __STL_TRY {
        construct(&p->data, x);
      }
      __STL_UNWIND(put_node(p));
      return p;
  }
//销毁(析构并释放)一个节点
  void destroy_node(link_type p) {
    destroy(&p->data);
    put_node(p);
  }
  // 对节点初始化
  void empty_initialize() { 
    node = get_node();
    node->next = node;
    node->prev = node;
  }  
};

基本属性获取

template <class T, class Alloc = alloc>
class list {
    ...
public: 
	iterator begin() { return (link_type)((*node).next); }	// 返回指向头的指针
    const_iterator begin() const { return (link_type)((*node).next); }
    iterator end() { return node; }	// 返回最后一个元素的后一个的地址
    const_iterator end() const { return node; }
    
    // 这里是为旋转做准备, rbegin 返回最后一个地址, rend 返回第一个地址. 我们放在配接器里面分析
    reverse_iterator rbegin() { return reverse_iterator(end()); }
    const_reverse_iterator rbegin() const { 
      return const_reverse_iterator(end()); 
    }
    reverse_iterator rend() { return reverse_iterator(begin()); }
    const_reverse_iterator rend() const { 
      return const_reverse_iterator(begin());
    } 
    
    // 判断是否为空链表, 这是判断只有一个空 node 来表示链表为空.
    bool empty() const { return node->next == node; }
    // 因为这个链表, 地址并不连续, 所以要自己迭代计算链表的长度.
    size_type size() const {
      size_type result = 0;
      distance(begin(), end(), result);
      return result;
    }
    size_type max_size() const { return size_type(-1); }
    // 返回第一个元素的值
    reference front() { return *begin(); }
    const_reference front() const { return *begin(); }
    // 返回最后一个元素的值
    reference back() { return *(--end()); }
    const_reference back() const { return *(--end()); }
    
    // 交换
    void swap(list<T, Alloc>& x) { __STD::swap(node, x.node); }
    ...
};
template <class T, class Alloc>
inline void swap(list<T, Alloc>& x, list<T, Alloc>& y) {
  	x.swap(y);
}

list 的头插和尾插

因为 list 是一个循环的双链表, 所以 push 和 pop 就必须实现是在头插入, 删除还是在尾插入和删除。

在 list 中，push 操作都调用 insert 函数, pop 操作都调用 erase 函数。

template <class T, class Alloc = alloc>
class list {
    ...
    // 直接在头部或尾部插入
    void push_front(const T& x) { insert(begin(), x); } 
    void push_back(const T& x) { insert(end(), x); }
    // 直接在头部或尾部删除
    void pop_front() { erase(begin()); } 
    void pop_back() { 
      iterator tmp = end();
      erase(--tmp);
    }
    ...
};

上面的两个插入函数内部调用的 insert 函数。

class list {
    ...
public:
  // 最基本的 insert 操作, 之插入一个元素
  iterator insert(iterator position, const T& x) {
      // 将元素插入指定位置的前一个地址
    link_type tmp = create_node(x);
    tmp->next = position.node;
    tmp->prev = position.node->prev;
    (link_type(position.node->prev))->next = tmp;
    position.node->prev = tmp;
    return tmp;
  }

这里需要注意的是

• 节点实际是以 node 空节点开始的。
• 插入操作是将元素插入到指定位置的前一个地址进行插入的。

删除操作

删除元素的操作大都是由 erase 函数来实现的, 其他的所有函数都是直接或间接调用 erase 。 list 是链表, 所以链表怎么实现删除, list 就在怎么操作：很简单，先保留前驱和后继节点， 再调整指针位置即可。 由于它是双向环状链表，只要把边界条件处理好，那么在头部或者尾部插入元素操作几乎是一样的，同样的道理，在头部或者尾部删除元素也是一样的。

template <class T, class Alloc = alloc>
class list {
    ...
	iterator erase(iterator first, iterator last);
    void clear();   
    // 参数是一个迭代器 修改该元素的前后指针指向再单独释放节点就行了
	iterator erase(iterator position) {
      link_type next_node = link_type(position.node->next);
      link_type prev_node = link_type(position.node->prev);
      prev_node->next = next_node;
      next_node->prev = prev_node;
      destroy_node(position.node);
      return iterator(next_node);
    }
    ...
};
...
}

list 内部提供一种所谓的迁移操作(transfer)：将某连续范围的元素迁移到某个特定位置之前，技术上实现其实不难，就是节点之间的指针移动，只要明白了这个函数的原理，后面的 splice，sort，merge 函数也就一一知晓了，我们来看一下 transfer 的源码：

template <class T, class Alloc = alloc>
class list {
    ...
protected:
    void transfer(iterator position, iterator first, iterator last) {
      if (position != last) {
        (*(link_type((*last.node).prev))).next = position.node;
        (*(link_type((*first.node).prev))).next = last.node;
        (*(link_type((*position.node).prev))).next = first.node;  
        link_type tmp = link_type((*position.node).prev);
        (*position.node).prev = (*last.node).prev;
        (*last.node).prev = (*first.node).prev; 
        (*first.node).prev = tmp;
      }
    }
    ...
};

上面代码的七行分别对应下图的七个步骤，看明白应该不难吧。

另外 list 的其它的一些成员函数这里限于篇幅，就不贴出源码了，简单说一些注意点。

splice 函数： 将两个链表进行合并：内部就是调用的 transfer 函数。

merge 函数： 将传入的 list 链表 x 与原链表按从小到大合并到原链表中(前提是两个链表都是已经从小到大排序了). 这里 merge 的核心就是 transfer 函数。

reverse 函数： 实现将链表翻转的功能：主要是 list 的迭代器基本不会改变的特点, 将每一个元素一个个插入到 begin 之前。

sort 函数： list 这个容器居然还自己实现一个排序，看一眼源码就发现其实内部调用的 merge 函数，用了一个数组链表用来存储 2^i 个元素, 当上一个元素存储满了之后继续往下一个链表存储, 最后将所有的链表进行 merge 归并(合并), 从而实现了链表的排序。

赋值操作： 需要考虑两个链表的实际大小不一样时的操作

• 原链表大 : 复制完后要删除掉原链表多余的元素
• 原链表小 : 复制完后要还要将 x 链表的剩余元素以插入的方式插入到原链表中

resize 操作： 重新修改 list 的大小。

传入一个 new_size，如果链表旧长度大于 new_size 的大小, 那就删除后面多余的节点

clear 操作： 清除所有节点

遍历每一个节点，销毁(析构并释放)一个节点

remove 操作： 清除指定值的元素

遍历每一个节点，找到就移除

unique 操作： 清除数值相同的连续元素，注意只有“连续而相同的元素”，才会被移除剩一个。

遍历每一个节点，如果在此区间段有相同的元素就移除之

感兴趣的读者可以自行去阅读体会。

好啦，list 的内容到这里就结束了。

list 总结

我们来总结一下。

list 是一种双向链表。每个结点都包含一个数据域、一个前驱指针 prev 和一个后驱指针 next 。

由于其链表特性，实现同样的操作，相对于 STL 中的通用算法，list 的成员函数通常有更高的效率，内部仅需做一些指针的操作，因此尽可能选择 list 成员函数。

优点

• 不适用连续内存完成动态操作
• 在内部方便进行插入删除操作。
• 可在两端进行 push 和 pop 操作。

缺点

• 不支持随机访问，即下标操作和.at()。
• 相对于 vector 占用内存多。

deque

下面到了最硬核的内容了，接下来我们学习一下双端队列 deque 。 deque 的功能很强大。 首先来一张图吧。

上面就是 deque 的示例图，deque 和 vector 的最大差异一在于 deque 允许常数时间内对头端或尾端进行元素的插入或移除操作。

二在于 deque 没有所谓的容量概念，因为它是动态地以分段连续空间组合而成随时可以增加一块新的空间并拼接起来。

虽然 deque 也提供 随机访问的迭代器，但它的迭代器和前面两种容器的都不一样，其设计相当复杂度和精妙，因此，会对各种运算产生一定影响，除非必要，尽可能的选择使用 vector 而非 deque 。一一来探究下吧。

由于文字限制，后续内容大家可以点击这个链接： https://mp.weixin.qq.com/s/NcrnwsB2gjq9h7W2hIZ6PQ

最后，来自实践生产环境的一个体会：上面所列的所有容器的一个原则：为了避免拷贝开销，不要直接把大的对象直接往里塞，而是使用指针。

好了，本期的内容就到这里了，我们下期再见。

PS：看有多少人点赞，下期不定期更新关联式容器哦，先买个关子，下期有个硬核的内容带大家手撕红黑树源码，红黑树的应用可以说很广了，像 Java 集合中的 TreeSet 和 TreeMap 、STL 中的 set 和 map 、Linux 虚拟内存的管理都用到了哦。

参考

1 、《 STL 源码剖析》

2 、https://github.com/FunctionDou/STL

推荐阅读：

5 千字长文+ 30 张图解 | 陪你手撕 STL 空间配置器源码

万字长文炸裂！手撕 STL 迭代器源码与 traits 编程技法

更多精彩

🔭 宇宙中心五道口狗厂程序员，爱生活，好读书

🌱 热爱分享: 公众号『 herongwei 』

🤔 个人博客：herongwei.com

📫 微信：icoredump

😄 有问题欢迎知乎 @herongwei

后台回复 [大礼包] 即可获取白嫖后端技术知识+算法电子书~