序列式容器

序列式容器是线性的，是 ordered 的，但是不一定是 sorted 的。

1. vector

vector 的实现技术关键在于对其大小的控制以及重新分配空间时数据移动的效率。

vector 的迭代器

事实上 vector 仅仅是维护了一个线性的内存空间，普通的原生指针完全可以作为 vector 的迭代器。

vector 的数据结构

vector 是线性结构，使用一对迭代器 first 和 last 来表示存储数据的范围，并使用 end_of_storage 来指向整块连续空间的尾部。一旦容量不足，就要经历“重新分配、元素移动、释放原空间”的操作，重新分配的空间会扩展为两倍，这些操作的 overhead 很大。同时，这也正是为什么一旦重新分配，原有的迭代器会失效，因为都不在同一个内存区域了。

vector 的 constructor 和内存管理

2. list

vector 是连续的线性空间，list作为链表，可以在常数时间内插入删除一个节点。STL List是一个双向链表，节点大概的结构：

template <class T>
struct _List_node {
_List_node *next;
_List_node *prev;
T _M_data;
}

list 不能像 vector 一样使用原生指针作为迭代器，因为 list 元素在内存中不是连续存储的。list 有一个重要的性质，插入（insert）操作不会导致原有的迭代器失效，甚至删除操作也仅仅是使得那个被删除元素的迭代器失效，而其他的迭代器都不会失效。

3. deque

vector 是单向开口的线性空间的容器，而 deque 是双向开口的线性空间的容器，deque 允许在常数时间内在头、尾插入、移除元素。事实上，vector 可以动态增长是一个假象，仅仅利用了（1）开辟更大空间（2）将原来的数据复制过去（3）释放原来的空间这三部曲带来的。如果不是分配空间的时候提前预支了一部分空间，这三部曲带来的 overhead 将会非常高。

同样的，deque 也是在努力维持一个假象——不会因为空间不足为需要重新分配空间，移动数据，释放旧空间。deque 是由一段一段定量连续的空间构成的，一旦需要在 deque 的首或尾分配新的空间，那么就继续分配一段新的定量的连续的空间，连接在首部或者尾部。这也使得 deque 的迭代器更加复杂。

deque 迭代器

template<typename _Tp, typename _Ref, typename _Ptr>
struct _Deque_iterator {
public:
    //这里可以看出来deque的迭代器要比vector的迭代器要复杂
  _Elt_pointer _M_cur; // 当前的元素
  _Elt_pointer _M_first; // 当前迭代器所指向的缓冲区的头节点
  _Elt_pointer _M_last; // 当前迭代器所指向的缓冲区的尾(包含备用空间)
  _Map_pointer _M_node;// 指向管控中心map
};

由于 deque 是分段连续的，要维持整个 deque 整体连续的假象，主要就是要依靠迭代器的 operator++ 和 operator– 这两个运算符。指针的加、减、前进、后退一旦遇到缓冲区边界，需要跳到下一个缓冲区。

// _M_set_node() 是一个很关键的函数,用来在遇到缓冲区边缘的时候跳到下一个缓冲区
void _M_set_node(_Map_pointer __new_node) _GLIBCXX_NOEXCEPT
{
    _M_node = __new_node; // 换成新的缓冲区 
	_M_first = *__new_node; // 头节点换成新缓冲区的头 
	_M_last = _M_first + difference_type(_S_buffer_size()); // 尾节点换成新缓冲区的尾
}

// 关键的是迭代器各种运算符的重载
reference operator*() const _GLIBCXX_NOEXCEPT { return *_M_cur; }

pointer operator->() const _GLIBCXX_NOEXCEPT { return _M_cur; }

// 前置--，先检查当前节点是否当前缓冲区的头节点，如果是则跳转到上一个缓冲区
_Self& operator--() _GLIBCXX_NOEXCEPT {
	if (_M_cur == _M_first) { // 如果已经到了当前缓冲区的头
	    _M_set_node(_M_node - 1); // 跳转到前一个缓冲区
	    _M_cur = _M_last; // 最后一个缓冲区的下一个位置
	  }
	--_M_cur; // 切换到前一个元素
	return *this;
}
_Self operator--(int) _GLIBCXX_NOEXCEPT { // 后置--
	_Self __tmp = *this;
	--*this; // 标准写法，调用前置--
	return __tmp;
}
_Self& operator++() _GLIBCXX_NOEXCEPT {
	++_M_cur; // 切换到下一个元素
	if (_M_cur == _M_last) { // 是否到了最后的位置
	    _M_set_node(_M_node + 1); // 切换到下一个缓冲区
	    _M_cur = _M_first; // 切换到头元素
	}
	return *this;
}
_Self operator++(int) _GLIBCXX_NOEXCEPT { // 标准写法
	_Self __tmp = *this;
	++*this;
	return __tmp;
}

// 随机存取，直接跳转n个距离
_Self& operator+=(difference_type __n) _GLIBCXX_NOEXCEPT {
	const difference_type __offset = __n + (_M_cur - _M_first);
	if (__offset >= 0 && __offset < difference_type(_S_buffer_size())) // 目标在同一个缓冲区
	  _M_cur += __n;
	else {
	    const difference_type __node_offset =
	      __offset > 0 ? __offset / difference_type(_S_buffer_size())
			   : -difference_type((-__offset - 1) / _S_buffer_size()) - 1; // 不在同一个缓冲区
	    _M_set_node(_M_node + __node_offset);
	    _M_cur = _M_first + (__offset - __node_offset * difference_type(_S_buffer_size()));
	}
	return *this;
}

operator+(difference_type __n) const _GLIBCXX_NOEXCEPT { // 调用+=
    _Self __tmp = *this;
    return __tmp += __n;
}

_Self& operator-=(difference_type __n) _GLIBCXX_NOEXCEPT { // 调用+= 
    return *this += -__n;
}

_Self operator-(difference_type __n) const _GLIBCXX_NOEXCEPT { // 调用-=
	_Self __tmp = *this;
	return __tmp -= __n;
}

reference operator[](difference_type __n) const _GLIBCXX_NOEXCEPT { return *(*this + __n); }

4. stack

stack 是一种后进先出的数据结构，在C++ STL中不将 stack 作为容器的一种，因为 stack 默认是以 deque 作为底层结构,用其他容器完成所有的工作。“修改某种容器，表现出不同的行为”在C++ STL 中称为适配器（adapter），因此 stack 不被当成是容器，而是被当成适配器。

stack 的源代码真的很简单，也就三百行。默认使用 deque 作为底层容器，当然也可以指定底层容器和内存分配器。stack 的成员函数 empty、size、top、push、pop等都是依靠底层容器来实现的。因为 stack 只能访问顶端的元素，不能随机访问，也不需要提供迭代器。除了默认的 deque 作为底层容器之外，也可以用 list 作为底层容器：

#include <deque>
using std::deque;

// 默认使用 deque 为底层容器
template<typename _Tp, typename _Sequence = deque<_Tp>>
class stack {
template<typename _Tp1, typename _Seq1>
friend bool operator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
template<typename _Tp1, typename _Seq1>
friend bool operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);

public:
typedef typename _Sequence::value_type         value_type;
typedef typename _Sequence::refefence          refefence;
typedef typename _Sequence::const_reference    const_reference;
typedef typename _Sequence::size_type          size_type;
typedef          _Sequence                     container_type;

protected:
_Sequence c; // stack 的底层容器

public:
    stack() : c() { } // 空stack
    explicit stack(const _Sequence &__c) : c(__c) { } // 指定底层容器
    
    // 几个 stack 的成员, 完成都是利用底层容器的操作实现的
    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
    refefence top() { return c.back(); }
    const_reference top() const { return c.back(); }
    void push(const  value_type& __x) { c.push_back(__x); }
};

template<typename _Tp, typename _Seq>
inline bool operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) {
    return __x.c == __y.c;
}

template<typename _Tp, typename _Seq>
inline bool operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) {
    return __x.c == __y.c;
}

以 list 作为底层容器

#include <stack>
#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

int main() {
    stack<int, list<int>> istk;
    istk.push(1);
    istk.push(2);
    istk.push(3);
    istk.push(4);
    istk.push(5);

    cout << istk.size() << endl;
    cout << istk.top() << endl;
    istk.pop();
    cout << istk.top() << endl;
}

5. queue

以某种既有容器作为底层容器，改变其接口使得其符合 queue 的“先进先出”的特性，因此 queue 也是一种适配器，而不是容器。同样的，queue 也是以 deque 作为底层容器。queue 的所有元素都要符合 “先进先出”的原则，因此只有队头才有被访问的机会，没有必要可以提供迭代器。

 #include <deque>
using std::deque;

// 默认使用 deque 为底层容器
template<typename _Tp, typename _Sequence = deque<_Tp> >
class queue {
template<typename _Tp1, typename _Seq1>
friend bool operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
template<typename _Tp1, typename _Seq1>
friend bool operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);

public:
    typedef typename _Sequence::value_type         value_type;
    typedef typename _Sequence::refefence          reference;
    typedef typename _Sequence::const_reference    const_reference;
    typedef typename _Sequence::size_type          size_type;
    typedef          _Sequence                     container_type;

protected:
    _Sequence c; // queue 的底层容器

queue() : c() { }
explicit queue(const _Sequence& __c) : c(__c) { }
template <typename __Alloc, typename _REquires = _Uses<_Alloc>>
explicit queue(const _Alloc& __a) : c(__a) { }
// ...省略了一些constructor

// 成员函数
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference front() { return c.front(); }
const_reference front() const { return c.front(); } 
reference back() { return c.back(); }
const_reference back() const { return c.back(); }
void push(const value_type& __x) { c.push_back(__x); }

void push(value_type&& __x) { c.push_back(std::move(__x)); }
};


template<typename _Tp, typename _Seq>
inline bool operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y){
    return __x.c == __y.c;
}

template<typename _Tp, typename _Seq>
inline bool operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) {
    return __x.c < __y.c;
}

类似于 stack ，queue 同样也可以用 list 作为底层容器：

#include <queue>
#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

int main() {
    queue<int, list<int>> ique;
    ique.push(2);
    ique.push(4);
    ique.push(6);
    ique.push(8);

    cout << ique.size() << endl;
    cout << ique.front() << endl;

    ique.pop(); cout << ique.front() << endl;
    ique.pop(); cout << ique.front() << endl;
    ique.pop(); cout << ique.front() << endl;
    cout << "size = " << ique.size() << endl;
    return 0;
}

6. heap(implicit representation)

所谓的 binary heap 就是 complete binary tree（完全二叉树）。如果完全二叉树的根节点从 1 开始编号，那么就有以下的性质：

1
2
3

   i
  /\
2i  2i+1

如果用数组表示一棵完全二叉树，索引 1 表示跟节点，接下来依次按层编号，那么对于某个节点 i ，它的左孩子就是 2i , 右孩子就是 2i+1 ，父节点就是 i / 2。

heap 可以分开 max-heap 和 min-heap，因此用 vector 实现 heap 时，对于 max-heap ，最大节点总是在 vector 的开头，对于 min-heap ，最小节点总是在开头。STL提供了一系列的 heap 算法，用来在一个底层容器(通常是vector)创建一个 heap。

push_heap 算法
push_heap 将一个值插入到一个堆中，并通过调整这个插在容器尾部的值的位置，使得整个堆重新满足 max-heap 或者 min-heap 的特性，push_heap 的核心代码如下：

// 调用__push_heap的时候，新的元素已经加入到容器的尾部
template<typename _RandomAccessIterator, typename _Distance, typename _Tp, typename _Compare>
void __push_heap(_RandomAccessIterator __first,
		_Distance __holeIndex, _Distance __topIndex, _Tp __value,
		_Compare& __comp) {

      _Distance __parent = (__holeIndex - 1) / 2; // 父节点的位置
      // while 还没有到跟节点的位置,并且自己还大于父节点(max-heap中)
      while (__holeIndex > __topIndex && __comp(__first + __parent, __value)) {
	    // 交换当前节点和父节点的值
	  *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); // 令当前节点位置的值为父节点的值
	  __holeIndex = __parent; // 当前节点的 index 是父节点的位置
	  __parent = (__holeIndex - 1) / 2; // 更新父节点的位置
	}
      *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); // 找到应该属于的位置,更新上值
}

pop_heap 算法
无论是 max-heap 还是 min-heap，其最大或最小值必然是在跟节点，pop_heap 算法就是为了取走跟节点（其实是调整根节点到到容器尾部，但是还没有弹出来），然后重新调整使其满足 heap 的性质。要注意的是，在使用 pop_heap 之后，跟节点仅仅是被放到了容器的最后，而没有被真正弹出来，如果要弹出根节点，还是需要调用底层容器的 pop_back 。pop_heap 关键代码：

 // 此时堆顶已经放置到了容器尾部
 // __adjust_heap用来调整堆, 现在要插入的元素使value,
 // first: 第一个元素
 // holeIndex: 要调整的位置
 // len: 容器元素数量
 // value: 要调整的值, 也就是原来容器末尾的值
 template<typename _RandomAccessIterator, typename _Distance, typename _Tp, typename _Compare>
   void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
	  _Distance __len, _Tp __value, _Compare __comp)
   {
     const _Distance __topIndex = __holeIndex;
     _Distance __secondChild = __holeIndex;
     while (__secondChild < (__len - 1) / 2)
{
  __secondChild = 2 * (__secondChild + 1);
  if (__comp(__first + __secondChild, __first + (__secondChild - 1)))
    __secondChild--;

  *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
  __holeIndex = __secondChild;
}

     if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
{
  __secondChild = 2 * (__secondChild + 1);
  *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
					     + (__secondChild - 1)));
  __holeIndex = __secondChild - 1;
}
     __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
__cmp(_GLIBCXX_MOVE(__comp));
     std::__push_heap(__first, __holeIndex, __topIndex, _GLIBCXX_MOVE(__value), __cmp);
   }

sort_heap 算法
每次 pop_heap 都可以将堆顶元素放置到最后的位置，那么持续作 pop_heap 操作就可以完成排序，这就是 sort_heap 的工作。sort_heap 之后，heap 就不再是 heap 了。sort_heap() 核心代码:

    // 被sort_heap调用,用来不断pop_heap,使得堆被排序
template<typename _RandomAccessIterator, typename _Compare>
void __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
        // 每当还有元素没有被pop出到容器范围的末尾
    while (__last - __first > 1) {
        // last 指向最后一个元素
        --__last;
        // 每次pop出一个元素
        // 不断pop就可以排序
        std::__pop_heap(__first, __last, __last, __comp);
    }
}

make_heap 算法
make_heap 算法将一段既有的数据转化成一个 heap，也就是将这段数据转换成用序列表达的完全二叉树。核心代码如下所示：

template<typename _RandomAccessIterator, typename _Compare>
void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
    typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
    typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType;
    // 如果没有元素或者仅仅有一个元素,就直接返回
    if (__last - __first < 2) return;
    const _DistanceType __len = __last - __first; // 元素数量
    _DistanceType __parent = (__len - 2) / 2;
    while (true) {
      _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
      std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value), __comp);
      if (__parent == 0) return;
      __parent--;
    }
}

7. priority_queue

priority_queue 默认情况下由一个 max-heap ，底层容器用 vector 来实现。priority_queue 往往不被归类为容器，而是被归类为 container adapter。类似于 queue 和 stack，他们的实现源代码都很简单，priority_queue 的实现源代码在 stl_queue.h 中。

 // 空的 priority_queue
 template<typename _Tp, typename _Sequence = vector<_Tp>,
	   typename _Compare  = less<typename _Sequence::value_type> >
class priority_queue {

protected:
    //  See queue::c for notes on these names.
    _Sequence  c; // 底层容器
    _Compare   comp; // 比较标准

public:
      template<typename _Seq = _Sequence, typename _Requires = typename
	       enable_if<__and_<is_default_constructible<_Compare>,
				is_default_constructible<_Seq>>::value>::type>
	priority_queue()
	: c(), comp() { }
    
      // 构造就是 调用 make_heap
      explicit priority_queue(const _Compare& __x, const _Sequence& __s)
      : c(__s), comp(__x)
      { std::make_heap(c.begin(), c.end(), comp); }

      explicit
      priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence())
      : c(std::move(__s)), comp(__x)
      { std::make_heap(c.begin(), c.end(), comp); }

      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
	explicit
	priority_queue(const _Alloc& __a)
	: c(__a), comp() { }

      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
	priority_queue(const _Compare& __x, const _Alloc& __a)
	: c(__a), comp(__x) { }

      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
	priority_queue(const _Compare& __x, const _Sequence& __c,
		       const _Alloc& __a)
	: c(__c, __a), comp(__x) { }

      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
	priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a)
	: c(std::move(__c), __a), comp(__x) { }

      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
	priority_queue(const priority_queue& __q, const _Alloc& __a)
	: c(__q.c, __a), comp(__q.comp) { }

      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
	priority_queue(priority_queue&& __q, const _Alloc& __a)
	: c(std::move(__q.c), __a), comp(std::move(__q.comp)) { }

    bool empty() const { return c.empty(); }

    size_type size() const{ return c.size(); }

    const_reference top() const {
        __glibcxx_requires_nonempty();
        return c.front();
    }

    void push(const value_type& __x) {
        c.push_back(__x);
        std::push_heap(c.begin(), c.end(), comp);
    }

    void pop() {
        __glibcxx_requires_nonempty();
        std::pop_heap(c.begin(), c.end(), comp);
        c.pop_back();
    }

};

It is hard to say goodbye! 😝