2 万字 20 图带你⼿撕 STL 序列

式容器源码⼤家好，我是⼩贺。

⽂章每周持续更新，可以微信搜索公众号「herongwei」第⼀时间阅读和催更。

本⽂ GitHub : https://github.com/rongweihe/CPPNotes已经收录，有⼀线⼤⼚⾯试点思维导图，也整理了很多我的⽂档，欢迎点个⼩和完善。⼀起加油，变得更⭐好！

15.1 前⾔

源码之前，了⽆秘密。

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

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

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

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

15.2 容器分类

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

限于篇幅，这篇⽂章⼩贺会来重点讲解⼀下经常使⽤到的那些容器，⽐如 vector，list，deque，以及衍⽣的栈和队列其背后核⼼的设计和奥秘，不多 BB，⻢上就来分析。

15.3 vector写 C++ 的⼩伙伴们，应该对 vector 都⾮常熟悉了，vector 基本能够⽀持任何类型的对象，同时它也是⼀个可以动态增⻓的数组，使⽤起来⾮常的⽅便。

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

vector 基本数据结构基本上，STL ⾥⾯所有的容器的源码都包含⾄少三个部分：

迭代器，遍历容器的元素，控制容器空间的边界和元素的移动；

构造函数，满⾜容器的多种初始化；

属性的获取，⽐如 begin()，end()等；

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

template <classT, classAlloc = alloc>
classvector {
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的缺点也很明显, 在频率较⾼的插⼊和删除时效率就太低了15.4 list好了，下⾯我们来看⼀下 list，list 是⼀种双向链表。

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

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

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

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

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

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

来瞅⼀瞅，list 的节点⻓啥样，因为 list 是⼀种双向链表，所以基本结构就是下⾯这个样⼦：

基本类型

template<classT, classRef, classPtr> 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<classT, classRef, classPtr> 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<classT, classRef, classPtr> struct__list_iterator  {
...
  // 重载
  booloperator==(const self& x) const { return node == x.node; }
  booloperator!=(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 <classT, classAlloc = alloc>
classlist {
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 <classT, classAlloc = alloc>
classlist {
protected:
	typedefvoid* void_pointer;
  typedef __list_node<T> list_node; // 节点
  typedef simple_alloc<list_node, Alloc> list_node_allocator; // 空间配置器

其中，list_node_allocator(n)表示配置 n 个节点空间。

以下四个函数，分别⽤来配置，释放，构造，销毁⼀个节点。

classlist {
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 <classT, classAlloc = alloc>
classlist {
...
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 <classT, classAlloc>
inline void swap(list<T, Alloc>& x, list<T, Alloc>& y) {
	x.swap(y);
}

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

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

template <classT, classAlloc = alloc>
classlist {
...
  // 直接在头部或尾部插⼊
  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 函数。

classlist {
...
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 <classT, classAlloc = alloc>
classlist {
  ...
  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 <classT, classAlloc = alloc>
classlist {
...
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占⽤内存多。

15.5 deque下⾯到了最硬核的内容了，接下来我们学习⼀下双端队列 deque 。

deque 的功能很强⼤。

⾸先来⼀张图吧。

上⾯就是 deque 的示例图，deque 和 vector 的最⼤差异⼀在于 deque 允许常数时间内对头端或尾端进⾏元素的插⼊或移除操作。

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

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

deque 的中控器deque 在逻辑上看起来是连续空间，内部是由⼀段⼀段的定量连续空间构成。

⼀旦有必要在 deque 的前端或尾端增加新空间，便配置⼀段定量的连续空间，串接在整个deque 的头部或尾部。

设计 deque 的⼤师们，想必是让 deque 的最⼤挑战就是在这些分段的定量连续空间上，维护其整体连续的假象，并提供其随机存取的接⼝，从⽽避开了像 vector 那样的“重新配置-复制-释放”开销三部曲。这样⼀来，虽然开销降低，却提⾼了复杂的迭代器架构。

因此数据结构的设计和迭代器前进或后退等操作都⾮常复杂。

deque 采⽤⼀块所谓的 map （注意不是STL⾥⾯的map容器）作为中控器，其实就是⼀⼩块

连续空间，其中的每个元素都是指针，指向另外⼀段较⼤的连续线性空间，称之为缓冲区。，在后⾯我们看到，缓冲区才是 deque 的储存空间主体。

#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
template <classT, classRef, classPtr, size_t BufSiz>
classdeque {
public:
typedef T value_type;
typedef value_type* pointer;
...
protected:
typedef pointer** map_pointer;
  map_pointer map;//指向 map，map 是连续空间，其内的每个元素都是⼀个指针。
  size_type map_size;
...
};

其示例图如下：deque 的结构设计中，map 和 node-buffer 的关系如下：

deque 的迭代器deque 是分段连续空间，维持其“整体连续”假象的任务，就靠它的迭代器来实现，也就是operator++ 和 operator-- 两个运算⼦上⾯。

在看源码之前，我们可以思考⼀下，如果让你来设计，你觉得 deque 的迭代器应该具备什么样的结构和功能呢？

⾸先第⼀点，我们能想到的是，既然是分段连续，迭代器应该能指出当前的连续空间在哪⾥；

其次，第⼆点因为缓冲区有边界，迭代器还应该要能判断，当前是否处于所在缓冲区的边缘，如果是，⼀旦前进或后退，就必须跳转到下⼀个或上⼀个缓冲区；

第三点，也就是实现前⾯两种情况的前提，迭代器必须能随时控制中控器。

有了这样的思想准备之后，我们再来看源码，就显得容易理解⼀些了。

template <classT, classRef, classPtr, size_t BufSiz>
struct__deque_iterator {
  // 迭代器定义
  typedef __deque_iterator<T, T&, T*, BufSiz>             iterator;
  typedef __deque_iterator<T, const T&, const T*, BufSiz>
  const_iterator;
  static size_t buffer_size() {return __deque_buf_size(BufSiz,
  sizeof(T)); }
  // deque是random_access_iterator_tag类型
  typedef random_access_iterator_tag iterator_category;
  // 基本类型的定义, 满⾜traits编程
  typedef T value_type;
  typedef Ptr pointer;
  typedef Ref reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  // node
  typedef T** map_pointer;
  map_pointer node;
  typedef __deque_iterator self;
  ...
};

deque 的每⼀个缓冲区由设计了三个迭代器（为什么这样设计？）

struct__deque_iterator {
...
typedef T value_type;
T* cur;
T* first;
T* last;
typedef T** map_pointer;
map_pointer node;
...
};

那，为什么要这样设计呢？回到前⾯我们刚才说的，因为它是分段连续的空间，下图描绘了deque 的中控器、缓冲区、迭代器之间的相互关系：

看明⽩了吗，每⼀段都指向⼀个缓冲区 buffer，⽽缓冲区是需要知道每个元素的位置的，所以需要这些迭代器去访问。

其中 cur 表示当前所指的位置；

first 表示当前数组中头的位置；

last 表示当前数组中尾的位置。

这样就⽅便管理，需要注意的是 deque 的空间是由 map 管理的，它是⼀个指向指针的指针，所以三个参数都是指向当前的数组，但这样的数组可能有多个，只是每个数组都管理这3个变量。

那么，缓冲区⼤⼩是谁来决定的呢？这⾥呢，⽤来决定缓冲区⼤⼩的是⼀个全局函数:

inlinesize_t__deque_buf_size(size_t n, size_t sz) {
return n != 0 ? n : (sz < 512 ? size_t(512 / sz): size_t(1));
}
//如果 n 不为0，则返回 n，表示缓冲区⼤⼩由⽤户⾃定义
//如果 n == 0，表示缓冲区⼤⼩默认值
//如果 sz = (元素⼤⼩ sizeof(value_type)) ⼩于 512 则返回 521/sz
//如果 sz 不⼩于 512 则返回 1

假设我们现在构造了⼀个 int 类型的 deque，设置缓冲区⼤⼩等于 32，这样⼀来，每个缓冲区可以容纳 32/sizeof(int) = 8（64位系统）个元素。经过⼀番操作之后，deque 现在有 20 个元素了，那么成员函数 begin() 和 end() 返回的两个迭代器应该是怎样的呢？如下图所示：

20 个元素需要 20/(sizeof(int)) = 5（图中只展示3个）个缓冲区。所以 map 运⽤了三个节点。

迭代器 start 内的 cur 指针指向缓冲区的第⼀个元素，迭代器 finish 内的 cur 指针指向缓冲区的最后⼀个元素(的下⼀个位置)。

注意，最后⼀个缓冲区尚有备⽤空间，如果之后还有新元素插⼊，则直接插⼊到备⽤空间。

deque 迭代器的操作前进和后退operator++ 操作代表是需要切换到下⼀个元素，这⾥需要先切换再判断是否已经到达缓冲区的末尾。

self& operator++() {
  ++cur; //切换⾄下⼀个元素
  if (cur == last) { //如果已经到达所在缓冲区的末尾
    set_node(node+1); //切换下⼀个节点
    cur = first;
  }
  return *this;
}

operator-- 操作代表切换到上⼀个元素所在的位置，需要先判断是否到达缓冲区的头部，再后退。

self& operator--() {
  if (cur == first) { //如果已经到达所在缓冲区的头部
    set_node(node - 1); //切换前⼀个节点的最后⼀个元素
    cur = last;
}
  --cur;           //切换前⼀个元素
  return *this;
}

deque 的构造和析构函数构造函数. 有多个重载函数, 接受⼤部分不同的参数类型. 基本上每⼀个构造函数都会调⽤create_map_and_nodes, 这就是构造函数的核⼼, 待会就来分析这个函数实现.

template <classT, classAlloc = alloc, size_t BufSiz = 0>
classdeque {
...
public:                         // Basic types
  deque() : start(), finish(), map(0), map_size(0){
  	create_map_and_nodes(0);
  } // 默认构造函数
  deque(const deque& x) : start(), finish(), map(0), map_size(0) {
    create_map_and_nodes(x.size());
    __STL_TRY {
    uninitialized_copy(x.begin(), x.end(), start);
    }
    __STL_UNWIND(destroy_map_and_nodes());
	}
  // 接受 n:初始化⼤⼩, value:初始化的值
  deque(size_type n, const value_type& value) : start(), finish(),
  map(0), map_size(0) {
  	fill_initialize(n, value);
  }
  deque(int n, const value_type& value) : start(), finish(), map(0),
  map_size(0) {
  	fill_initialize(n, value);
  }
  deque(long n, const value_type& value) : start(), finish(), map(0),
  map_size(0){
  	fill_initialize(n, value);
	}
...

下⾯我们来学习⼀下 deque 的中控器是如何配置的

void
deque<T,Alloc,BufSize>::create_map_and_nodes(size_type_num_elements) {
  //需要节点数= (每个元素/每个缓冲区可容纳的元素个数+1)//如果刚好整除，多配⼀个节点
  size_type num_nodes = num_elements / buffer_size() + 1;
  //⼀个 map 要管理⼏个节点，最少 8 个，最多是需要节点数+2
  map_size = max(initial_map_size(), num_nodes + 2);
	map = map_allocator::allocate(map_size);
  // 计算出数组的头前⾯留出来的位置保存并在nstart.
  map_pointer nstart = map + (map_size - num_nodes) / 2;
	map_pointer nfinish = nstart + num_nodes - 1;
  map_pointer cur;//指向所拥有的节点的最中央位置
  ...
}

注意了，看了源码之后才知道：deque 的 begin 和 end 不是⼀开始就是指向 map 中控器⾥开头和结尾的，⽽是指向所拥有的节点的最中央位置。

这样带来的好处是可以使得头尾两边扩充的可能性和⼀样⼤，换句话来说，因为 deque 是头尾插⼊都是 O(1)，所以 deque 在头和尾都留有空间⽅便头尾插⼊。

那么，什么时候 map 中控器本身需要调整⼤⼩呢？触发条件在于 reserve_map_at_back 和reserve_map_at_front 这两个函数来判断，实际操作由 reallocate_map 来执⾏。

那 reallocate_map ⼜是如何操作的呢？这⾥先留个悬念。

// 如果 map 尾端的节点备⽤空间不⾜，符合条件就配置⼀个新的map(配置更⼤的，拷⻉原来的，释放原来的)
void reserve_map_at_back (size_type nodes_to_add = 1) {
if (nodes_to_add + 1 > map_size - (finish.node - map))
reallocate_map(nodes_to_add, false);
}

// 如果 map 前端的节点备⽤空间不⾜，符合条件就配置⼀个新的map(配置更⼤的，拷⻉原来的，释放原来的)
void reserve_map_at_front (size_type nodes_to_add = 1) {
  if (nodes_to_add > start.node - map)
  reallocate_map(nodes_to_add, true);
}

deque 的插⼊元素和删除元素因为 deque 的是能够双向操作，所以其 push 和 pop 操作都类似于 list 都可以直接有对应的操作，需要注意的是 list 是链表，并不会涉及到界线的判断，⽽deque 是由数组来存储的，就需要随时对界线进⾏判断。

push 实现

template <classT, classAlloc = alloc, size_t BufSiz = 0>
classdeque {
...
public:                         // push_* and pop_*
  // 对尾进⾏插⼊
  // 判断函数是否达到了数组尾部. 没有达到就直接进⾏插⼊
  void push_back(const value_type& t) {
  if (finish.cur != finish.last - 1) {
  construct(finish.cur, t);
  ++finish.cur;
  }
  else
  push_back_aux(t);
  }
  // 对头进⾏插⼊
  // 判断函数是否达到了数组头部. 没有达到就直接进⾏插⼊
  void push_front(const value_type& t) {
  if (start.cur != start.first) {
    construct(start.cur - 1, t);
    --start.cur;
  }
  else
  	push_front_aux(t);
  }
  ...
};

pop 实现

template <classT, classAlloc = alloc, size_t BufSiz = 0>
classdeque {
...
public:
  // 对尾部进⾏操作
  // 判断是否达到数组的头部. 没有到达就直接释放
  void pop_back() {
  if (finish.cur != finish.first) {
    --finish.cur;
    destroy(finish.cur);
  }
  else
  	pop_back_aux();
 }
  // 对头部进⾏操作
  // 判断是否达到数组的尾部. 没有到达就直接释放
  void pop_front() {
  if (start.cur != start.last - 1) {
    destroy(start.cur);
    ++start.cur;
  }
  else
  pop_front_aux();
}
...
};

reserve_map_at⼀类函数. pop和push都先调⽤了reserve_map_at_XX函数, 这些函数主要是为了判断前后空间是否⾜够.

删除操作不知道还记得，最开始构造函数调⽤ create_map_and_nodes 函数，考虑到 deque 实现前后插⼊时间复杂度为O(1)，保证了在前后留出了空间，所以 push 和 pop 都可以在前⾯的数组进⾏操作。

现在就来看 erase，因为 deque 是由数组构成，所以地址空间是连续的，删除也就像 vector⼀样，要移动所有的元素。

deque 为了保证效率尽可能的⾼，就判断删除的位置是中间偏后还是中间偏前来进⾏移动。

template <classT, classAlloc = alloc, size_t BufSiz = 0>
classdeque {
...
public:                         // Erase
  iterator erase(iterator pos)
  {
  iterator next = pos;
  ++next;
  difference_type index = pos - start;
  // 删除的地⽅是中间偏前, 移动前⾯的元素
  if (index < (size() >> 1))
  {
  copy_backward(start, pos, next);
  pop_front();
  }
  // 删除的地⽅是中间偏后, 移动后⾯的元素
  else {
  copy(next, finish, pos);
  pop_back();
  }
  return start + index;
  }
  // 范围删除, 实际也是调⽤上⾯的erase函数.
  iterator erase(iterator first, iterator last);
  void clear();
  ...
};

最后讲⼀下 insert 函数deque 源码的基本每⼀个insert 重载函数都会调⽤了 insert_auto 判断插⼊的位置离头还是尾⽐较近。

如果离头进：则先将头往前移动，调整将要移动的距离，⽤ copy 进⾏调整。

如果离尾近：则将尾往前移动，调整将要移动的距离，⽤ copy 进⾏调整。

注意 : push_back是先执⾏构造在移动 node, ⽽ push_front 是先移动 node 在进⾏构造. 实现的差异主要是finish是指向最后⼀个元素的后⼀个地址⽽first指向的就只第⼀个元素的地址. 下⾯ pop 也是⼀样的。

源码⾥还有⼀些其它的成员函数，限于篇幅，这⾥就不贴源码，简单的过⼀遍还有⼀些函数：

reallocate_map：判断中控器的容量是否够⽤，如果不够⽤，申请更⼤的空间，拷⻉元素过去，修改 map 和 start，finish 的指向。

fill_initialize 函数：：申请空间，对每个空间进⾏初始化，最后⼀个数组单独处理. 毕竟最后⼀个数组⼀般不是会全部填充满。

clear函数.删除所有元素. 分两步执⾏:⾸先从第⼆个数组开始到倒数第⼆个数组⼀次性全部删除，这样做是考虑到中间的数组肯定都是满的，前后两个数组就不⼀定是填充满的，最后删除前后两个数组的元素。

deque的swap操作也只是交换了start, finish, map, 并没有交换所有的元素.

resize函数.重新将deque进⾏调整, 实现与list⼀样的.

**析构函数：分步释放内存.**deque 总结deque 其实是在功能上合并了 vector 和 list。

优点：

1、随机访问⽅便，即⽀持 [ ] 操作符和 vector.at()；

2、在内部⽅便的进⾏插⼊和删除操作；

3、可在两端进⾏ push、pop

缺点：因为涉及⽐较复杂，采⽤分段连续空间，所以占⽤内存相对多。

使⽤区别：

1、如果你需要⾼效的随即存取，⽽不在乎插⼊和删除的效率，使⽤ vector。

2、如果你需要⼤量的插⼊和删除，⽽不关⼼随机存取，则应使⽤ list。

3、如果你需要随机存取，⽽且关⼼两端数据的插⼊和删除，则应使⽤ deque 。

15.6 以 deque 为底层容器的适配器

最后要介绍的三种常⽤的数据结构，准确来说其实是⼀种适配器，底层都是已其它容器为基准。

栈-stack：先⼊后出，只允许在栈顶添加和删除元素，称为出栈和⼊栈。

队列-queue：先⼊先出，在队⾸取元素，在队尾添加元素，称为出队和⼊队。

优先队列-priority_queue：带权值的队列。

常⻅栈的应⽤场景包括括号问题的求解，表达式的转换和求值，函数调⽤和递归实现，深度优先遍历DFS等；

常⻅的队列的应⽤场景包括计算机系统中各种资源的管理，消息缓冲队列的管理和⼴度优先遍历BFS等。

源码之前，了⽆秘密，翻⼀下源码，就知道 stack 和 queue 的底层其实就是使⽤ deque，⽤deque 为底层容器封装。

stack 的源码：

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <classT, classSequence = deque<T> >
#else
template <classT, classSequence>
#endif
classstack {
public:
  typedef typename Sequence::value_type value_type;
  typedef typename Sequence::size_type size_type;
  typedef typename Sequence::reference reference;
  typedef typename Sequence::const_reference const_reference;
protected:
Sequence c;

queue 的源码：

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <classT, classSequence = deque<T> >
#else
template <classT, classSequence>
#endif
classqueue {
public:
  typedef typename Sequence::value_type value_type;
  typedef typename Sequence::size_type size_type;
  typedef typename Sequence::reference reference;
  typedef typename Sequence::const_reference const_reference;
protected:
	Sequence c;

heap最后我们来看⼀下，heap ，heap 并不是⼀个容器, 所以他没有实现⾃⼰的迭代器, 也就没有遍历操作, 它只是⼀种算法。

push_heap 插⼊元素插⼊函数是push_heap. heap只接受RandomAccessIterator类型的迭代器.

template <classRandomAccessIterator>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
  __push_heap_aux(first, last, distance_type(first), value_type(first));
 }
  template <classRandomAccessIterator, classDistance, classT>
  inline void __push_heap_aux(RandomAccessIterator first,
RandomAccessIterator last, Distance*, T*) {
  // 这⾥传⼊的是两个迭代器的⻓度, 0, 还有最后⼀个数据
  __push_heap(first, Distance((last - first) - 1), Distance(0),  T(*(last - 1)));
}

pop_heap 删除元素pop操作其实并没有真正意义去删除数据, ⽽是将数据放在最后, 只是没有指向最后的元素⽽已, 这⾥arrary也可以使⽤, 毕竟没有对数组的⼤⼩进⾏调整. pop的实现有两种, 这⾥都罗列了出来, 另⼀个传⼊的是 cmp 伪函数.

template <classRandomAccessIterator, classCompare>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp) {
	__pop_heap_aux(first, last, value_type(first), comp);
}
template <classRandomAccessIterator, classT, classCompare>
inline void __pop_heap_aux(RandomAccessIterator first,
RandomAccessIterator last, T*, Compare comp)
{
  __pop_heap(first, last - 1, last - 1, T(*(last - 1)), comp,
  distance_type(first));
}
template <classRandomAccessIterator, classT, classCompare, class Distance>
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator result, T value, Compare comp, Distance*) {
   *result = *first;
  __adjust_heap(first, Distance(0), Distance(last - first), value, comp);
}
template <classRandomAccessIterator, classT, classDistance>
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator
last,
RandomAccessIterator result, T value, Distance*)
{
  *result = *first; // 因为这⾥是⼤根堆, 所以first的值就是最⼤值, 先将最⼤值保存.
  __adjust_heap(first, Distance(0), Distance(last - first), value);
}

make_heap 将数组变成堆存放

template <classRandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator
last) {
	__make_heap(first, last, value_type(first), distance_type(first));
}
template <classRandomAccessIterator, classT, classDistance>
void __make_heap(RandomAccessIterator first, RandomAccessIterator last,
T*,
Distance*) {
	if (last - first < 2) return;
  // 计算⻓度, 并找出中间的根值
  Distance len = last - first;
  Distance parent = (len - 2)/2;
  while (true) {
    // ⼀个个进⾏调整, 放到后⾯
    __adjust_heap(first, parent, len, T(*(first + parent)));
    if (parent == 0) return;
    parent--;
    }
}

sort_heap 实现堆排序其实就是每次将第⼀位数据弹出从⽽实现排序功能.

template <classRandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
	while (last - first > 1) pop_heap(first, last--);
}
template <classRandomAccessIterator, classCompare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp) {
	while (last - first > 1) pop_heap(first, last--, comp);
}

priority_queue最后我们来看⼀下 priority_queue上⼀节分析 heap 其实就是为 priority_queue 做准备. priority_queue 是⼀个优先级队列, 是带权值的. ⽀持插⼊和删除操作, 其只能从尾部插⼊,头部删除, 并且其顺序也并⾮是根据加⼊的顺序排列的。

priority_queue 因为也是队列的⼀种体现, 所以也就跟队列⼀样不能直接的遍历数组, 也就没有迭代器. priority_queue 本身也不算是⼀个容器, 它是以 vector 为容器以 heap为数据操作的配置器。

类型定义

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <classT, classSequence = vector<T>,
class Compare = less<typename Sequence::value_type> >
#else
template <classT, classSequence, classCompare>
#endif
class priority_queue {
public:
  // 符合traits编程规范
  typedef typename Sequence::value_type value_type;
  typedeft ypename Sequence::size_type size_type;
  typedeft ypename Sequence::reference reference;
  typedeft ypename Sequence::const_reference const_reference;
protected:
  Sequence c; // 定义vector容器的对象
  Compare comp; // 定义⽐较函数(伪函数)
  ...
};

属性获取priority_queue 只有简单的 3 个属性获取的函数, 其本身的操作也很简单, 只是实现依赖了vector 和 heap 就变得⽐较复杂。

class priority_queue {
...
public:
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
const_reference top() const { return c.front(); }
...
};

push 和 pop 实现push 和 pop 具体都是采⽤的 heap 算法。

priority_queue 本身实现是很复杂的，但是当我们已经了解过 vector，heap 之后再来看，它其实就简单了。

就是将 vector 作为容器， heap 作为算法来操作的配置器，这也体现了 STL 的灵活性：通过各个容器与算法的结合就能实现另⼀种功能。

最后，来⾃实践⽣产环境的⼀个体会：上⾯所列的所有容器的⼀个原则：为了避免拷⻉开销，不要直接把⼤的对象直接往⾥塞，⽽是使⽤指针。

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

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

参考

1、《STL 源码剖析》

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