The Annotated STL Sources-3

前言

在日常的开发生活中，经常会使用一些STL容器。譬如最常使用的vector容器，在使用时可能仅仅是去调用它拥有的元素操作函数。对于它们背后的数据的扩展、数据的遍历的底层实现操作几乎很少有关心。了解它们底层实现，可以有效的帮助你提升代码的执行效率与编译速度。
在STL中，容器被分为两个部分：序列式容器、关联式窗口。序列式容器也是相对来说可能是最常使用的几个STL容器了，它包含的内容见下图：

vector

vector的数据安排以及操作方式与array都十分相似，它们的主要区别就在于空间运用的灵活性。array是静态空间，一旦配置后就无法改变了。vecotr是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新的元素。vector的实现技术，关键在于对空间大小控制与重新配置时数据的移动效率。

vector 基本数据结构

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

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

这些内容也可从vector的源码中探寻到:

template <class T,class Alloc = alloc>
class vector {
public:
	// vecotr嵌套类型定义
	typedef T value_type;
	typedef size_t size_type;
	
	// vecotr 迭代器定义
	// vector 的迭代器是普通指针
	typedef value_type* pointer;
	typedef value_type* iterator;
	typedef value_type& reference;
	
protected:
	// simple_alloc是SGI STL的空间配置器
	typedef simple_alloc<value_type, Alloc> data_allocator;
	iterator start;	// 表示目前使用空间的头
	iterator finish; // 表示目前使用空间的尾
	iterator end_of_storage; // 表示目前可用空间的尾
	....
}

vector 构造与内存管理

vector为了应对不同的初始化，设有了多个构造函数。有的专门用于初始化头尾与可用空间的尾，有的允许我们指定空间的大小与初值。它们的源码如下

template <class T, class Alloc = alloc>
class vector {
	...
public:
	vector() : start(0), finish(0), end_of_storage(0) {}  // 默认初始化
	vector(size_type n,const T& value) {fill_initialize(n,value);}  
	vector(int n,const T& value) {fill_initialize(n,value);}
	vector(long n,const T& value) {fill_initialize(n,value);}
	explicit vector(size_type n) {fill_initialize(n,T());}  // 必须显式的调用构造函数，接受一个值

	// 析构函数
	~vector() {
		destory(start,finish);
		deallocate();
	}
	....
}

vector构造函数中，缺省使用的是alloc空间配置器，并据此定义了一个data_allocator为了更方便的以元素大小为配置单元。以此为前提，再结合下例中的源码分析。从而探究vector的构造函数的参数初始化与空间分配。

template <class T,class Alloc = alloc>
class vector {
	typedef simple_alloc<value_type, Alloc> data_allocator;
	...
}

// 接受一个大小与初始化值
vector(size_type n, const T& value) {fill_initialize(n,value);}

// 填充并初始化
vector fill_initialize(size_type n, const T& value) {
	start = allocate_and_fill(n,value);
	finish = start+n;
	end_of_storage = finish;
}

// 配置而后填充
iterator allocate_and_fill(size_type n,const T& x) {
	iterator result = data_allocator::allocate(n);
	uninitialized_fill_n(result, n, x);
	return result;
}

// 析构
void deallocate() {
	if (start) {]
		data_allocator::deallocate(start,end_of_storage-start);
	}
}

这里使用了uninitialized_fill_n全局函数，它将通过对第一参数的类型是否为POD的判断，从而避免了POD类型对程序性能的拖累。如果是非POD，将在异常处理正确的情况下构造变量。vector的析构是通过直接调用deallocate空间配置器，将区间内对象全部析构且将内存还给空间配置器。

vector 属性获取

vector的数据结构非常的简单，通过start、finish、end_of_storage就轻松解决了头尾标示、大小、容量以及[]运算符等机能的实现。具体到源码中，基本就是对三个迭代器进行处理。

template <class T, class Alloc = alloc>
class vector {
	...
public:
	// 标识头尾
	iterator begin() {return start;}
	iterator end() {return finish;}
	
	// 标识长度
	size_type size() const {return size_type (end() - begin()); }
	// 标识容量
	size_type capacity() const 
	{
		return size_type (end_of_storage - begin());
	}

	// 空容器判断
	bool empty() const  {return begin() == end();}
	// []运算子
	reference operator[] (size_type n) {return *(begin() + n);}

	// 最前端元素
	reference front() {return *begin();}
	// 最后端元素
	reference back() {return *(end() - 1);}
	...
};

如果对源码的表示不存在困惑，可通过下图的案例进行综合的理解

vector push与pop

vector中push_back()的作用就是将新元素插入vector尾端。不过对于插入，我们需要面对空间配置的问题:
  1. 若备用空间充足，则在备用空间上直接构造元素,并调整迭代器finish
  2. 如果不够，就扩充空间(重新配置、移动数据、释放空间)
push_back在源码中的定义如下：

template <class T,class Alloc = alloc>
void push_back(const T& x) {
	if (finish != end_of_storage) { // 仍有备用空间
		construct(finish, x);
		++finish;					// 使用后，调整水位高度
	}
	else 
		insert_aux(end(), x);		// 没有备用空间了，使用insert_aux进行分情况处理
}

在insert_aux()中，它又对是否仍有备用空间进行了一次判断。这样的做法是否合理呢？合理的，因为对于insert_aux，不仅只有push_back会调用它，还有其它的函数会调用它。具体到源码如下：

template <class T,class Alloc = alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
	if (finish != end_of_storage) {		// 仍有备用空间
		// 在备用空间起始处构造一个元素,并以vector最后一个元素值为其初值
		construct(finish, *(finish-1));
		// 调整水位
		++finish;
		T x_copy =x;
		copy_backward(position, finish-2,finish-1);
		*position = x_copy;
	}
	...
}

当真的等到备用空间不足时，我们需要根据配置原则合理分配空间: 如果原大小为0，则配置1(个元素大小);如果原大小不为0，则配置原大小的两倍;前半段用来放置原数据，后半段准备用来放置新数据;

	else {		
		// 已无备用空间
		const size_type old_size = size();
		const size_type len = old_size != 0 ? 2 * old_size : 1;
		// 以上配置原则：如果原大小0，则配置1(个元素大小)
		// 如果原大小不为0，则配置原大小的两倍
		// 前半段用来放置原数据，后半段准备用来放置新数据

		iterator new_start = data_allocator::allocate(len); 
		iterator new_finish = new_start;

		try {
			// 将原vector的内容拷贝到新vector
			new_finish = uninitialized_copy(start,position,new_start);
			// 为新元素设定实值x
			construct(new_finish, x);
			// 调整水位
			++new_finish;
			// 将安插点的原内容也拷贝过来(提示：本函数也可能被insert(p,x)调用)
			new_finish = uninitialized_copy(position, finish, new_finish);
		}
		catch(...) {
			destroy (new_start, new_finish);
			data_allocator::deallocate(new_start,len);
			throw;
		}

		// 析构并释放原vector
		destroy(begin(), end());
		deallocate();

		// 调整迭代器，指向新的vector
		start = new_start;
		finish = new_finish;
		end_of_storage = new_start + len;
	}
}

pop_back的作用就是将尾端元素析构掉，并适当的调整大小

void pop_back() {
	--finish;
	destroy(finish);
}

vector 元素删除erase()

在vector中提供了两个版本的erase(),一个用于清除[first,last)中的所有元素，一个用于清除某个位置上的元素。earse()就是将要删除的元素后面的内容复制到前面，然后再删除要删除的元素，并调整迭代器finish。

// 清除[first,last)中的所有元素
iterator erase (iterator first,iterator last) {
	// 将[last,finish)内容复制到区间[first,first+(last-finish))	
	iterator i = copy(last, finish, first);
	destroy(i,finish);  // 释放[i,finish)区间内存
	finish = finish - (last - finish); // 调整迭代器finish位置
	return first; // 迭代器并没有改变，改变的是内容
}

// 清除某个位置上的元素
iterator erase(iterator position) {
	if (position + 1 != end()) {
		// 将[position+1,finish)内容复制到区间[position,position+(position+1-finish))
		copy(position+1, finish,position);
	}
	--finish;
	destroy(finish);
	return position;
}

STL中的clear就是通过调用erase(begin(),end());实现的，earse(first,end);操作过程如下图所示：

vector 元素插入insert()

vector元素插入就涉及到了内存空间的配置，我们将它们的情况分成了三种进行分析：
   1. 插入点之后的现有元素个数 > 新增元素个数

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

   3. 如果备用空间不足时

vector 迭代器失效

由于迭代器是连续动态内存的封装，对于vector迭代器来说仅仅是一个普通的原生指针。对于以下两种操作都会导致迭代器失效：
   1. 元素删除： vector为了保证元素的连续排列，需要将vector的删除元素之后的元素向前移动。
   2. 元素插入： 当vector的备用空间不足时，它将重新申请更大的内存，之后将对应的元素拷贝过去。
这样的操作之后就会导致一个问题：指针将所指向的内存将不再存储对应的vector元素。

vector 优缺点总结

最后还需要提醒的一点是：vector的成员函数是都不会去做边界检查(at会抛出异常)，在编写程序时应保证迭代器与索引值的合法性。
我们一起来总结一下vector的的优缺点:
优点
  1. 在内存中是一块连续内存的内存空间进行存储，可以像数组一样的操作，并且支持动态扩容。
  2. 因此元素的随机的访问方便，支持下标访问与vector.at()操作。
  3. 节省空间
缺点
  1. 由于vector的顺序存储的结构特性，vector的插入与删除的时间复杂复为O(n)
  2. vector的pop与push仅可在末端进行
  3. 当插入长度过大时，需要重新的分配、拷贝与释放

list

相对于vecotr的连续线性空间，作为SGI STL中的双向链表list就显得复杂许多。但是复杂的list对于空间的配置堪称绝妙，每插入一个元素或删除一个元素就对应的配置或释放一个元素空间。因而list对于数据的插入与删除的时间复杂度永远都是O(1)。相对于vector，它更适合大量数据的插入与删除的环境中使用。

list 数据结构——节点

一个list通常采用的都是分开设计，对于使用或设计过list的同学这几乎算是一个通识了。但是为何需要分开设计呢？其实节点指针只是为迭代器提供便利，在使用迭代器遍历时根本无需使用到list的数据成员。它的节点大致如下图所示：

它的源码如下：

template <class T>
struct __list_node {
  typedef void* void_pointer;
  void_pointer next;
  void_pointer prev;
  T data;
};

list 数据结构－迭代器

相对于vector线性存储是使用的内存中一块连续区域，list则无法保证节点在内存中的连续。因此，对于list的迭代器的就必须要正确的指向每一个节点。并且可以保证正确的递增、递减、取值与成员操作等。list本身还是一个双向链表，因而它还必须具备前移、后移的能力。
所以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;

  // list的迭代器类型是bidirectional iterator
  typedef bidirectional_iterator_tag iterator_category;
  typedef T value_type;
  typedef Ptr pointer;
  typedef Ref reference;
  typedef __list_node<T>* link_type;
  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; }
    // 对*和->操作符进行重载
  	reference operator*() const { return (*node).data; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
  	pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

    // ++和--是直接操作的指针指向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 构造与析构

list提供了多个构造函数，其中主要的两类就是：配置n个节点空间、空链表。它们的构造过程如下图所示：

list 基本元素获取

在了解了对象构造与析构的基础上，我们再继续深入list的基本元素操作有获取头尾、判断链表为空等元素操作。它所包括的基本操作如下所示：

list 元素操作

list所提供的元素操作很多，无法在有限的篇幅中详细讲解。在这里将着重讲解以下几个元素操作：push_front、push_back、pop_front、pop_back。这此包括了元素的插入与删除的基本操作，其它的操作可自行阅读源码进行深入理解。

list 元素操作——插入

在list中，经常使用push_back()与push_front()实现头部插入与尾部插入,其实现大多是通过调用insert()函数来实现这一功能的。在此，仅介绍一种insert的简单形式，通过它来一窥双链表中的头插与尾插。

list 元素操作——删除

对应push_back()与push_front()，它们的删除操作是由pop_back()与pop_front()来管理的。其实实现就是通过对prev、next移动来实现。

迭代器失效

在list迭代器中，插入与接合操作均不会造成原有的list迭代器失效。当然，如果earse()会导致迭代器失效，不过仅限于当前这个节点,其余的迭代器均不受影响。

list 优缺点总结

list是一个双向链表,因为其具有链表的特性，在仅需一些指针操作时，应尽可能的使用list成员函数
优点
   * 插入删除元素效率很高
   * 可在两端进行数据进行操作

缺点
   * 不支持随机访问
   * 相对于vector占用内存过多

deque

vector 是单向开口的连续线性空间,对应的deque则是一个双向开口的线性空间。双向开口的意思是deque的两端皆可以做插入与删除操作，deque大致描述图：

deque相对于vector不同点还在于，它并没有所谓的容量的一个概念,原因是它是动态的以分段连续空间组合而成的。deque也提供随机访问迭代器，不过它的设计不同于vector以普通指针的迭代器。它的迭代器也直接影响了deque算法的效率，因此非必要则最好使用vector代替deque。具体个中的奥妙，静看源码剖析。

deque中控器

deque是连续空间(至少逻辑上来看是这样的),内部也是由一段一段的连续空间构成，一旦有必要在deuqe前端或尾端增加新空间，便配置一段宣连续空间，串接在整个deque的头端或尾端。对于这一段一段的空间，如何使它成为一段连续的空间。维护整体空间连续的假象，同时还要避免与vector(重新配置、移动数据、释放空间)的复杂操作呢？这里STL提供是办法是设计一个复杂的迭代器。
作为算法与容器的粘合剂，为了更好的实现效果，deque 数据结构的设计和迭代器前进或后退等操作都非常复杂。deque采用一块所谓的map(非stlmap容器),其实就是就是一块小的连续空间，其中的每个元素都是指针，指向另外一段较大的连续线性空间，称之为缓冲区。在之后的内容中，你就可以了解到缓冲区才是deque的依存空间主体。SGI STL允许我们指定缓冲区大小，默认值为0表示将使用512bytes缓冲区。

#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
template <class T, class Ref, class Ptr, size_t BufSiz>
class deque {
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 <class T, class Ref, class Ptr>
struct __deque_iterator {
  typedef __deque_iterator<T, T&, T*>             iterator;
  typedef __deque_iterator<T, const T&, const T*> const_iterator;
  static size_t buffer_size() {return __deque_buf_size(0, sizeof(T)); }

  // deque是random_access_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;
  typedef T** map_pointer;

  typedef __deque_iterator self;
  
  // 三个迭代器类型
  T* cur;  // 迭代器所指缓冲区中的当前(current)元素
  T* first; // 此迭代器所指的缓冲区的头
  T* last; // 此迭代器所指的缓冲区的尾(含有备用空间)
  map_pointer node;
  ...

};

deque的中控器、缓冲区、迭代器的相互关系如下图所示：

每一段都指向一个缓冲区buffer，而缓冲区是需要知道每个元素的位置的，所以需要这些迭代器去访问。这样就十分方便管理，需要注意的是deque的空间是由map管理的，它是一个指向指针的指针，所以三个参数都是指向当前的数组。但是这样的数组可能有多个，只是每个数组都管理这三个变量。
之前在deque实现的差不多了，我们还有一个问题存在——缓冲区的大小由谁来决定？在SGI STL提供了一个全局函数来解决这个问题。

inline size_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，缓冲区大小为8(个)元素大小的deque(总大小为32)。经过一番操作后，deque现在在20个元素，那么成员函数begin()与end()返回的两个迭代器应该是怎样的？
如下图所示：

20个元素需要20/(sizeof(int)) = 3 个缓冲区。
所以map运用了三个节点，迭代器start内的cur指针指向缓冲区的第一个元素，迭代器finish内的指针指向缓冲区的最后一个元素(的下一个位置)。
注意：如果最后一个缓冲区尚有备用空间，那么之后若仍有新元素插入，则直接插入到备用空间之中。

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 构造与析构函数

deque的构造函数有多个重载函数，接受大部分不同的参数类型，基本上每一个构造函数都会调用create_map_and_nodes,这就是构造函数的核心，之后会对这个函数进行一个具体的分析。

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
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的构造函数后，再来了解一下deque都会调用的中控器(create_map_and_nodes)的实现

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来执行。
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与pop实现

push 实现

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
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 <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
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();
  }
    ...
};

pop与push都先调用了reserve_map_at_XX函数，这些函数主要是为了判断前后空间是否足够。

元素删除

回想deque的构造函数，我们使用调用了中控器(create_map_and_nodes)函数。这样保证了前后都留有空间，所以push与pop皆可以在前面的数组中进行操作。
现在对于删除操作erase,因为deque是由数组构成，所以地址空间是连续，删除因此也需要像vector一样移到所有元素。

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
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迭代器造成影响。因为这些操作都不会对现有的元素进行移动，如果一个分段数组满了。仅需创建亲的分段数组，并把对应的分段数组加入索引数组中就可以了。删除其实也是大致的意思，均不会对现有元素作移到操作。
但是除了这些操作，其它的插入与删除均会导致deque元素的任何pointers、reference、iterators失效。不过，效率相对于vector会好一些，毕竟不需要复制所有的元素。

deque 总结

deque 其实就是在功能上合并了vector与list

优点：
  1. 随机访问方便，即支持[]操作符与vector.at();
  2. 在内部方便的进行插入与删除操作
  3. 可在两端进行push、pop

缺点：因为设计比较复杂，采用分段连续空间，所以相对的占用空间会更多。

使用区别

1. 如果你需要高效的随机存取，而不在乎插入与删除的效率，使用vector
2. 如果你需要大量的插入与删除，并不关心随机存取，则应该使用list
3. 如果你随机存取，而且关心两端数据的插入与删除，则应该使用deque

stack And queue

以deque为底部容器的适配器
最后的要介绍的这三种容器，准确来说其实是一种适配器(就是通过将不适用的序列式容器变得适用)
栈——stack: 先入后出，只允许在栈顶添加与删除元素，称为出栈与入栈。

队列——queue: 先入先出，在队首取元素，在队尾添加元素，称为出队与入队。

优先队列: 带权值的队列。

常见的队列的应用场景包括计算机系统中的各种资源管理，消息缓冲队列的管理与广度优先遍历BFS等。在stack与queue的底层其实都是使用deque容器作为它们的底层数据结构。

信赖于deque的stack与queue的实现，就变得十分容易，具体到源码可见：

stack 源码

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class T, class Sequence = deque<T> >
#else
template <class T, class Sequence>
#endif
class stack {
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 <class T, class Sequence = deque<T> >
#else
template <class T, class Sequence>
#endif
class queue {
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 并不归属于STL容器组件之中，它的没有一个实现自己的迭代器，同时也没有遍历操作。准确来说，它只算是一种算法。

push_heap插入元素

插入函数是push_heap,heap仅接受RandomAccessIterator类型的迭代器。

template <class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
  __push_heap_aux(first, last, distance_type(first), value_type(first));
}

template <class RandomAccessIterator, class Distance, class T>
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操作其实并没有真正意义去凹陷数据，而是将数据放在最后，只是没有指向最后的元素而已，这里使用array也可以，毕竟没有对数据的大小进行调整。
pop的实现有两种，这里都罗列了出来，另一个传入的是cmp仿函数。

template <class RandomAccessIterator, class Compare>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp) {
    __pop_heap_aux(first, last, value_type(first), comp);
}
template <class RandomAccessIterator, class T, class Compare>
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 <class RandomAccessIterator, class T, class Compare, 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 <class RandomAccessIterator, class T, class Distance>
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 <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
  __make_heap(first, last, value_type(first), distance_type(first));
}
template <class RandomAccessIterator, class T, class Distance>
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 <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
  while (last - first > 1) pop_heap(first, last--);
}
template <class RandomAccessIterator, class Compare>
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 <class T, class Sequence = vector<T>, 
          class Compare = less<typename Sequence::value_type> >
#else
template <class T, class Sequence, class Compare>
#endif
class  priority_queue {
public:
 // 符合traits编程规范
  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; // 定义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本身实现是很复杂的，但是将其剖析开，就是vector与heap的组合。将vector作为容器，heap作为算法来操作的配置器。这样同样的显示出了STL的灵活性：通过各个容器与算法的结合就能实现另一种功能。

总结

在实际的使用中，为了避免拷贝的开销。还是还要直接把大的对象直接往里存放，而是使用指针来替代。