SGI STL 源码阅读：序列式容器的内存布局与扩容机制
围绕 vector、list、deque、stack、queue、heap 和 priority_queue，梳理序列式容器的存储结构和适配关系。
阅读地图：先抓住这篇源码的主线
flowchart LR
A[Sequence Containers] --> B[vector: 连续空间]
A --> C[list: 双向链表]
A --> D[deque: 分段连续空间]
D --> E[stack / queue 默认底层]
B --> F[heap algorithms]
F --> G[priority_queue adapter]
B --> H[扩容时搬迁元素并导致迭代器失效]
C --> I[插入删除稳定但随机访问差]
D --> J[中控器 map 管理 buffer]vector三个指针描述连续空间，扩容时重新分配并搬迁元素。
list节点独立分配，迭代器稳定，适合频繁插入删除。
deque用中控器管理多个 buffer，在连续语义和扩展能力之间折中。
序列式容器
所谓序列式容器，其中的元素都可序 （ordered），但未必有序（sorted）。C++语言本身提供了一个序列式容器 array, STL 另外再提供 vector, 1ist, deque，stack, queue, priority-queue 等等序列式容器。其中 stack 和 queue 由于只是将 deque 改头换面而成，技术上被归类为一种配接器（adapter）
vector
vector的数据安排与操作方式与array非常相似，但是与array不同的是，array是静态空间，一旦配置了就不能改变 想扩容可以，但是用户手动需要配置一段新空间，再把原来的元素搬到新空间，再把旧空间销毁。vector相比之下就好 很多，vector是动态空间，内部机制会根据元素的插入而自动扩容，但是vector不是满载以后插入一个元素扩容一个 如果那样的话真的太蠢了，时间成本非常高，稍后我们会详细看到SGI vector的实现策略
vector的定义摘要
这里直接给出vector的源码，所有的知识都将以注释的方式出现
// 在完整的vector定义之前，SGI STL定义了一个基类，如果仔细观察，我们可以发现
// 在这个类中定义的基本都是与内存管理相关的 + 三个重要的指针(start, finish, end_of_storage)
// 这样做的原因主要是为了将 内存管理 和 容器逻辑分开:
// 即_Vector_base = memory layer ；vector = container logic
template <class _Tp, class _Alloc>
class _Vector_base
{
public:
typedef _Alloc allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
_Vector_base(const _Alloc &)
: _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
_Vector_base(size_t __n, const _Alloc &)
: _M_start(0), _M_finish(0), _M_end_of_storage(0)
{
//看似vector的定义很长，但实际上它真正的成员变量只有三个指针:
// _M_start = _M_allocate(__n);
// _M_finish = _M_start;
// _M_end_of_storage = _M_start + __n;
_M_start = _M_allocate(__n); // 指向目前空间的头
_M_finish = _M_start; // 指向目前空间的尾
_M_end_of_storage = _M_start + __n; // 指向可用空间的尾
}
~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
protected:
_Tp *_M_start;
_Tp *_M_finish;
_Tp *_M_end_of_storage;
// simple alloc是对alloc的封装，不管它用的是第一级配置器还是第二级配置器都统一用_Alloc封装起来了
// template <class _Tp, class _Alloc>
// class simple_alloc
// {
// public:
// // 根据对象个数构造
// static _Tp *allocate(size_t __n)
// {
// return 0 == __n ? 0 : (_Tp *)_Alloc::allocate(__n * sizeof(_Tp));
// }
// static _Tp *allocate(void)
// {
// return (_Tp *)_Alloc::allocate(sizeof(_Tp));
// }
// static void deallocate(_Tp *__p, size_t __n)
// {
// if (0 != __n)
// _Alloc::deallocate(__p, __n * sizeof(_Tp));
// }
// static void deallocate(_Tp *__p)
// {
// _Alloc::deallocate(__p, sizeof(_Tp));
// }
// };
// 而容器中又对simple_alloc进行了封装，使simple_alloc的对象从字节大小转换成对象大小
typedef simple_alloc<_Tp, _Alloc> _M_data_allocator;
_Tp *_M_allocate(size_t __n)
{
// 相当于调用simple_alloc<_Tp, _Alloc>::allocate();
return _M_data_allocator::allocate(__n);
}
void _M_deallocate(_Tp *__p, size_t __n)
{
// 相当于调用simple_alloc<_Tp, _Alloc>::deallocate()
_M_data_allocator::deallocate(__p, __n);
}
};
// ================================== 完整vector ==================================
// 这里的内存配置器默认缺省给了SGI的alloc(二级配置器)
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp)>
class vector : protected _Vector_base<_Tp, _Alloc> // 继承管理内存的基类
{
// requirements:
__STL_CLASS_REQUIRES(_Tp, _Assignable);
private:
typedef _Vector_base<_Tp, _Alloc> _Base;
public:
// 内嵌类型的定义
typedef _Tp value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type* iterator; // vector内存空间是线性的，支持随机访问
typedef const value_type* const_iterator; // 所以它的迭代器就是randomaccess itr
typedef value_type& reference; // vector选择直接用原生指针来表示
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef typename _Base::allocator_type allocator_type;
allocator_type get_allocator() const { return _Base::get_allocator(); }
typedef reverse_iterator<const_iterator, value_type, const_reference,
difference_type>
const_reverse_iterator;
typedef reverse_iterator<iterator, value_type, reference, difference_type>
reverse_iterator;
protected:
// =============================== vector的核心扩容机制 ===============================
void _M_insert_aux(iterator __position, const _Tp &__x);
void _M_insert_aux(iterator __position);
// 为了方便观察，将实现提上来
// 注意，当空间不足需要扩容的时候，会导致原有迭代器失效!!!
template <class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp &__x)
{
// 如果还有内部储存空间
if (_M_finish != _M_end_of_storage)
{
// 以vector的最后一个元素为初值在结尾再构造一个对象
construct(_M_finish, *(_M_finish - 1));
// 调整结尾位置
++_M_finish;
// 保存插入对象
_Tp __x_copy = __x;
// 将整体对象移动
copy_backward(__position, _M_finish - 2, _M_finish - 1);
// 在pos插入新构造元素
*__position = __x_copy;
}
else
{
// vector空间不够
const size_type __old_size = size();
// 如果原size() == 0，就给两个空间，否则就给原size的两倍
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
// 构造新的大块空间
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
__STL_TRY
{
// 将插入点之前的元素copy过去
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
// 在pos构造插入对象
construct(__new_finish, __x);
++__new_finish;
// 将插入点后面的元素搬过去
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
// 如果出错则回滚到插入之前
__STL_UNWIND((destroy(__new_start, __new_finish),
_M_deallocate(__new_start, __len)));
// 销毁原有对象
destroy(begin(), end());
// 释放空间
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
// 调整指针位置
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
// 只传入一个迭代器版本的，主要作用就是为了扩容
template <class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::_M_insert_aux(iterator __position)
{
if (_M_finish != _M_end_of_storage)
{
construct(_M_finish, *(_M_finish - 1));
++_M_finish;
copy_backward(__position, _M_finish - 2, _M_finish - 1);
*__position = _Tp();
}
else
{
const size_type __old_size = size();
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
__STL_TRY
{
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
construct(__new_finish);
++__new_finish;
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
__STL_UNWIND((destroy(__new_start, __new_finish),
_M_deallocate(__new_start, __len)));
destroy(begin(), end());
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
public:
// =============================== vector迭代器相关 ===============================
// 这里提供的是获取vector迭代器的函数
// 通过vector的三个指针(start, finish, end_of_storage)可以轻松完成
// 正向迭代器
iterator begin() { return _M_start; }
const_iterator begin() const { return _M_start; }
iterator end() { return _M_finish; }
const_iterator end() const { return _M_finish; }
// 反向迭代器
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());
}
size_type size() const
{
return size_type(end() - begin());
}
size_type max_size() const
{
return size_type(-1) / sizeof(_Tp);
}
size_type capacity() const
{
return size_type(_M_end_of_storage - begin());
}
bool empty() const
{
return begin() == end();
}
// []运算符重载，访问对象
reference operator[](size_type __n) { return *(begin() + __n); }
const_reference operator[](size_type __n) const { return *(begin() + __n); }
// =============================== vector的构造和析构 ===============================
// 把allocator传给基类构造，让基类完成底层内存管理初始化。
// 使用explicit禁止隐式类型转换的原因是防止下面情况出现
// allocator<int> a;
// vector<int> v = a; // 隐式转换
// 编译器会vector<int> v = vector<int>(allocator)，但是这个语意不对的
explicit vector(const allocator_type &__a = allocator_type())
: _Base(__a) {}
// 允许指定初值和大小
vector(size_type __n, const _Tp &__value,
const allocator_type &__a = allocator_type())
: _Base(__n, __a)
{
// 从底层默认调取了uninitialized_fill_n()，这里后面单拎出来讲
_M_finish = uninitialized_fill_n(_M_start, __n, __value);
}
// 指定大小
explicit vector(size_type __n)
: _Base(__n, allocator_type())
{
// _Tp()传入的是一个临时对象，作用只是为了让uninitialized_fill_n()的底层
// uninitialized_fill_n_aux再判断实例化的类型是不是POD(plain old data)原生类型
// uninitialized_fill_n_aux再通过重载选择合适的构造对象的方式
_M_finish = uninitialized_fill_n(_M_start, __n, _Tp());
}
// 拷贝构造
vector(const vector<_Tp, _Alloc> &__x)
: _Base(__x.size(), __x.get_allocator())
{
_M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start);
}
// 通过迭代器构造
vector(const _Tp *__first, const _Tp *__last,
const allocator_type &__a = allocator_type())
: _Base(__last - __first, __a)
{
_M_finish = uninitialized_copy(__first, __last, _M_start);
}
~vector() { destroy(_M_start, _M_finish); }
// =============================== vector的元素操作 ===============================
vector<_Tp, _Alloc> &operator=(const vector<_Tp, _Alloc> &__x);
void reserve(size_type __n)
{
if (capacity() < __n)
{
const size_type __old_size = size();
iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __tmp;
_M_finish = __tmp + __old_size;
_M_end_of_storage = _M_start + __n;
}
}
// assign(), a generalized assignment member function. Two
// versions: one that takes a count, and one that takes a range.
// The range version is a member template, so we dispatch on whether
// or not the type is an integer.
void assign(size_type __n, const _Tp &__val) { _M_fill_assign(__n, __val); }
void _M_fill_assign(size_type __n, const _Tp &__val);
reference front() { return *begin(); }
const_reference front() const { return *begin(); }
reference back() { return *(end() - 1); }
const_reference back() const { return *(end() - 1); }
void push_back(const _Tp &__x)
{
if (_M_finish != _M_end_of_storage)
{
construct(_M_finish, __x);
++_M_finish;
}
else
_M_insert_aux(end(), __x);
}
void push_back()
{
if (_M_finish != _M_end_of_storage)
{
construct(_M_finish);
++_M_finish;
}
else
_M_insert_aux(end());
}
void swap(vector<_Tp, _Alloc> &__x)
{
__STD::swap(_M_start, __x._M_start);
__STD::swap(_M_finish, __x._M_finish);
__STD::swap(_M_end_of_storage, __x._M_end_of_storage);
}
// =============================== 扩容逻辑所在 ===============================
iterator insert(iterator __position, const _Tp &__x)
{
size_type __n = __position - begin();
if (_M_finish != _M_end_of_storage && __position == end())
{
construct(_M_finish, __x);
++_M_finish;
}
else
_M_insert_aux(__position, __x);
return begin() + __n;
}
iterator insert(iterator __position)
{
size_type __n = __position - begin();
if (_M_finish != _M_end_of_storage && __position == end())
{
construct(_M_finish);
++_M_finish;
}
else
_M_insert_aux(__position);
return begin() + __n;
}
void insert(iterator __position,
const_iterator __first, const_iterator __last);
// pos位置插入n个值为x的元素
void insert(iterator __pos, size_type __n, const _Tp &__x)
{
_M_fill_insert(__pos, __n, __x);
}
// 为了方便观察，我把实现提上来
void _M_fill_insert(iterator __pos, size_type __n, const _Tp &__x);
// 注意: 按照C++标准，插入元素的位置在pos之前
template <class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n,
const _Tp &__x)
{
// 如果插入个数n>0才执行
if (__n != 0)
{
// 先计算剩余空间够不够插入新元素所需要的总空间
if (size_type(_M_end_of_storage - _M_finish) >= __n)
{
// 插入元素存一下
_Tp __x_copy = __x;
// 计算插入点后面的以后元素个数
const size_type __elems_after = _M_finish - __position;
// 保存旧的结束点
iterator __old_finish = _M_finish;
// 如果插入点后面的元素个数大于新插入元素个数
if (__elems_after > __n)
{
// 将原有元素后移
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
// 移动目标结尾
_M_finish += __n;
// 拷贝中间部分
copy_backward(__position, __old_finish - __n, __old_finish);
// 填充元素
fill(__position, __position + __n, __x_copy);
}
// 如果插入点后面的元素个数少于插入元素个数
else
{
// 直接在尾部构造
uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
_M_finish += __n - __elems_after;
// 将插入点后面的数据拷贝到结尾
uninitialized_copy(__position, __old_finish, _M_finish);
// 移动结尾
_M_finish += __elems_after;
// 填充中间的值
fill(__position, __old_finish, __x_copy);
}
}
// 储备空间大小不够插入n个元素了
else
{
// 现在要扩容，新空间可以是原空间的两倍或者是原空间 + 新增空间个数，哪个大就用哪个
const size_type __old_size = size();
// 计算新元素个数
const size_type __len = __old_size + max(__old_size, __n);
// 通过内存配置器配置len个对象空间
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
__STL_TRY
{
// 将原起点到插入点的元素copy到新起点
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
// 填充n个对象
__new_finish = uninitialized_fill_n(__new_finish, __n, __x);
// 将插入点后面的元素copy到填充n个的后面
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
// 如果在构造期间出现异常，就析构掉刚构造的元素，回滚到insert前的版本
__STL_UNWIND((destroy(__new_start, __new_finish),
_M_deallocate(__new_start, __len)));
// 销毁原来空间的对象
destroy(_M_start, _M_finish);
// 回收空间
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
// 重新指向新的三个指针
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
}
void pop_back()
{
--_M_finish;
destroy(_M_finish);
}
// 擦除position上的元素
iterator erase(iterator __position)
{
if (__position + 1 != end())
copy(__position + 1, _M_finish, __position);
--_M_finish;
destroy(_M_finish);
return __position;
}
// 擦除first - last的元素
iterator erase(iterator __first, iterator __last)
{
iterator __i = copy(__last, _M_finish, __first);
destroy(__i, _M_finish);
_M_finish = _M_finish - (__last - __first);
return __first;
}
void resize(size_type __new_size, const _Tp &__x)
{
if (__new_size < size())
erase(begin() + __new_size, end());
else
insert(end(), __new_size - size(), __x);
}
void resize(size_type __new_size) { resize(__new_size, _Tp()); }
// 复用erase()擦除起点到终点
void clear() { erase(begin(), end()); }
// =============================== vector核心扩容机制 ===============================
protected:
iterator _M_allocate_and_copy(size_type __n, const_iterator __first,
const_iterator __last)
{
iterator __result = _M_allocate(__n);
__STL_TRY
{
uninitialized_copy(__first, __last, __result);
return __result;
}
__STL_UNWIND(_M_deallocate(__result, __n));
}
};
template <class _Tp, class _Alloc>
inline bool
operator==(const vector<_Tp, _Alloc> &__x, const vector<_Tp, _Alloc> &__y)
{
return __x.size() == __y.size() &&
equal(__x.begin(), __x.end(), __y.begin());
}
template <class _Tp, class _Alloc>
inline bool
operator<(const vector<_Tp, _Alloc> &__x, const vector<_Tp, _Alloc> &__y)
{
return lexicographical_compare(__x.begin(), __x.end(),
__y.begin(), __y.end());
}
// 重载赋值运算符
template <class _Tp, class _Alloc>
vector<_Tp, _Alloc> &
vector<_Tp, _Alloc>::operator=(const vector<_Tp, _Alloc> &__x)
{
// 如果x == this的话，直接结束了
if (&__x != this)
{
// 获取新对象的大小
const size_type __xlen = __x.size();
// capacity() 大于原 capacity()
if (__xlen > capacity())
{
// 直接开辟空间并同时将x拷贝过去
iterator __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
// 销毁原对象并释放空间
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
// 改变指针指向
_M_start = __tmp;
_M_end_of_storage = _M_start + __xlen;
}
// 原size()都大于赋值对象了
else if (size() >= __xlen)
{
// 覆盖前面的
iterator __i = copy(__x.begin(), __x.end(), begin());
// 销毁后面的
destroy(__i, _M_finish);
}
// 原capacity() 够了但是size()不够
else
{
// 直接从头搞了
copy(__x.begin(), __x.begin() + size(), _M_start);
uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish);
}
_M_finish = _M_start + __xlen;
}
return *this;
}
template <class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::_M_fill_assign(size_t __n, const value_type &__val)
{
if (__n > capacity())
{
vector<_Tp, _Alloc> __tmp(__n, __val, get_allocator());
__tmp.swap(*this);
}
else if (__n > size())
{
fill(begin(), end(), __val);
_M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val);
}
else
erase(fill_n(begin(), __n, __val), end());
}
// 用一段迭代器来插入对象，逻辑与_M_fill_Insert类似
// 先判断储备空间够不够
// 够 -> 则原地移动 + 构造
// 不够 -> 三段复制
// 体现了STL的核心设计思想，尽量少移动元素，尽量少构造对象
template <class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::insert(iterator __position,
const_iterator __first,
const_iterator __last)
{
if (__first != __last)
{
size_type __n = 0;
distance(__first, __last, __n);
if (size_type(_M_end_of_storage - _M_finish) >= __n)
{
const size_type __elems_after = _M_finish - __position;
iterator __old_finish = _M_finish;
if (__elems_after > __n)
{
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
_M_finish += __n;
copy_backward(__position, __old_finish - __n, __old_finish);
copy(__first, __last, __position);
}
else
{
uninitialized_copy(__first + __elems_after, __last, _M_finish);
_M_finish += __n - __elems_after;
uninitialized_copy(__position, __old_finish, _M_finish);
_M_finish += __elems_after;
copy(__first, __first + __elems_after, __position);
}
}
else
{
const size_type __old_size = size();
const size_type __len = __old_size + max(__old_size, __n);
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
__STL_TRY
{
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
__new_finish = uninitialized_copy(__first, __last, __new_finish);
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
__STL_UNWIND((destroy(__new_start, __new_finish),
_M_deallocate(__new_start, __len)));
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
}
不难看出，vector的源码中有几个核心函数
- _M_insert_aux()
- _M_fill_insert()
用来在pos处插入一个对象
用来批量插入某个对象，事实上相当于_M_insert_aux()的特殊版，但是当元素相同的时候，可以将时间复杂度从 O(N ^ 2) 降低到O(N)，看明白上面这两个函数，就可以搞懂vector的核心 QWQ!!!
List
相比较于 vector 的连续线性空间，11st 就显得复杂许多，它的好处是每次插入或删除一个元素，就会配置或者 释放一个元素空间。因此，1ist 对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或 元素移除，List永远是O(1)时间复杂度
List的节点(node)
与vector类似，list也将内存管理(不过这里list的是指向管理)与容器逻辑(存储分开)，这里贴出源码对节点的定义
// list节点的基类，用来管理前后方向的指针
struct _List_node_base
{
// 双向链表的前后指向
_List_node_base *_M_next;
_List_node_base *_M_prev;
};
// 派生类，容器逻辑(内容存储)
template <class _Tp>
struct _List_node : public _List_node_base
{
_Tp _M_data;
};
List的迭代器
list的迭代器不能想vector那样使用原生指针了，因为vector的是一块线性的内存空间，而list的节点并不能保证 在内存空间中连续存在，由于list是一个双向链表，必须具备前后移动的能力，这与Bidirection Iterator匹配
list还有一个重要的性质，在插入(insert)和接合(splice)的操作之后，它的迭代器并不会像vector那样失效 因为vector的插入可能导致记忆体重新配置，导致原有的全部迭代器失效
这里贴出list的迭代器实现，在这段代码中，我们仍然可以看到STL的将结构管理和数据管理分离的经典思想
struct _List_iterator_base
{
typedef size_t size_type;
typedef ptrdiff_t difference_type;
// 定义双向迭代器类型
typedef bidirectional_iterator_tag iterator_category;
_List_node_base *_M_node; // iterator中肯定也要有指向节点本身的指针
_List_iterator_base(_List_node_base *__x) : _M_node(__x) {}
_List_iterator_base() {}
// 对it前移和后移的封装，在后续重载++和--操作的时候有用
void _M_incr() { _M_node = _M_node->_M_next; }
void _M_decr() { _M_node = _M_node->_M_prev; }
bool operator==(const _List_iterator_base &__x) const
{
return _M_node == __x._M_node;
}
bool operator!=(const _List_iterator_base &__x) const
{
return _M_node != __x._M_node;
}
};
template <class _Tp, class _Ref, class _Ptr>
struct _List_iterator : public _List_iterator_base
{
typedef _List_iterator<_Tp, _Tp &, _Tp *> iterator;
typedef _List_iterator<_Tp, const _Tp &, const _Tp *> const_iterator;
typedef _List_iterator<_Tp, _Ref, _Ptr> _Self;
typedef _Tp value_type;
typedef _Ptr pointer;
typedef _Ref reference;
typedef _List_node<_Tp> _Node;
// 这里可以通过基类来初始化派生类是因为C++允许派生类指针隐式类型转换成基类指针
_List_iterator(_Node *__x) : _List_iterator_base(__x) {}
_List_iterator() {}
_List_iterator(const iterator &__x) : _List_iterator_base(__x._M_node) {}
reference operator*() const { return ((_Node *)_M_node)->_M_data; }
pointer operator->() const { return &(operator*()); }
// 前置++
_Self &operator++()
{
this->_M_incr();
return *this;
}
// 后置++
_Self operator++(int)
{
_Self __tmp = *this;
this->_M_incr();
return __tmp;
}
// 前置--
_Self &operator--()
{
this->_M_decr();
return *this;
}
// 后置--
_Self operator--(int)
{
_Self __tmp = *this;
this->_M_decr();
return __tmp;
}
};
list的数据结构
SGI list不仅是一个双向链表，它还同时也是一个环形链表，所以它只需要一个指针就可以表示整个list 如果让node刻意指向一个尾部的空白节点，那么它便满足了STL的前闭后开的要求，这样以来begin(), end() 都可以轻松完成，这点从list的基类定义就可以看出来
class _List_base
{
public:
typedef _Alloc allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
_List_base(const allocator_type &)
{
// 初始化一个空list，首尾相连
_M_node = _M_get_node();
_M_node->_M_next = _M_node;
_M_node->_M_prev = _M_node;
}
~_List_base()
{
clear();
_M_put_node(_M_node);
}
void clear();
protected:
// 这里与vector对alloc的封装类似，只不过vector将字节转化为一个对象的大小，list则是转化为一个节点
typedef simple_alloc<_List_node<_Tp>, _Alloc> _Alloc_type;
// 配置一个节点
_List_node<_Tp> *_M_get_node()
{
return _Alloc_type::allocate(1);
}
// 释放一个节点
void _M_put_node(_List_node<_Tp> *__p)
{
_Alloc_type::deallocate(__p, 1);
}
protected:
_List_node<_Tp> *_M_node; // 仅通过一个指针就可以定义链表
};
template <class _Tp, class _Alloc>
void _List_base<_Tp, _Alloc>::clear()
{
_List_node<_Tp> *__cur = (_List_node<_Tp> *)_M_node->_M_next;
while (__cur != _M_node)
{
_List_node<_Tp> *__tmp = __cur;
__cur = (_List_node<_Tp> *)__cur->_M_next;
_Destroy(&__tmp->_M_data);
_M_put_node(__tmp);
}
_M_node->_M_next = _M_node;
_M_node->_M_prev = _M_node;
}
下面继续贴出list的整体源码，一点一点来分析
// 可以看到list的alloc也缺省的给了第二级迭代器
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp)>
class list : protected _List_base<_Tp, _Alloc>
{
__STL_CLASS_REQUIRES(_Tp, _Assignable);
typedef _List_base<_Tp, _Alloc> _Base;
protected:
typedef void * _Void_pointer;
public:
typedef _Tp 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<_Tp> _Node;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef typename _Base::allocator_type allocator_type;
allocator_type get_allocator() const { return _Base::get_allocator(); }
public:
typedef _List_iterator<_Tp, _Tp &, _Tp *> iterator;
typedef _List_iterator<_Tp, const _Tp &, const _Tp *> const_iterator;
typedef reverse_bidirectional_iterator<const_iterator, value_type,
const_reference, difference_type>
const_reverse_iterator;
typedef reverse_bidirectional_iterator<iterator, value_type, reference,
difference_type>
reverse_iterator;
protected:
// 这里与基类对空间配置器的封装是类似的，但是基类只是对空间做了配置和释放
// 这里是对象的构造和销毁
_Node *_M_create_node(const _Tp &__x)
{
_Node *__p = _M_get_node();
__STL_TRY
{
_Construct(&__p->_M_data, __x); // 全局函数，placement new
}
__STL_UNWIND(_M_put_node(__p));
return __p;
}
_Node *_M_create_node()
{
_Node *__p = _M_get_node();
__STL_TRY
{
_Construct(&__p->_M_data);
}
__STL_UNWIND(_M_put_node(__p));
return __p;
}
public:
explicit list(const allocator_type &__a = allocator_type()) : _Base(__a) {}
// begin()和end()可以通过list是双向链表这一点轻松实现
iterator begin() { return (_Node *)(_M_node->_M_next); }
const_iterator begin() const { return (_Node *)(_M_node->_M_next); }
iterator end() { return _M_node; }
const_iterator end() const { return _M_node; }
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的next是不是node即可判断
bool empty() const { return _M_node->_M_next == _M_node; }
// 使用distance可以判断两个迭代器的距离
size_type size() const
{
size_type __result = 0;
distance(begin(), end(), __result);
return __result;
}
size_type max_size() const { return size_type(-1); }
// 获取list的头部元素begin()解引用
reference front() { return *begin(); }
const_reference front() const { return *begin(); }
// 获取尾部元素，因为end()指向是空的，所以要往后退一个
reference back() { return *(--end()); }
const_reference back() const { return *(--end()); }
void swap(list<_Tp, _Alloc> &__x) { __STD::swap(_M_node, __x._M_node); }
// 注意，stl中的在pos处插入节点统一为在pos前面插入
iterator insert(iterator __position, const _Tp &__x)
{
_Node *__tmp = _M_create_node(__x);
__tmp->_M_next = __position._M_node;
__tmp->_M_prev = __position._M_node->_M_prev;
__position._M_node->_M_prev->_M_next = __tmp;
__position._M_node->_M_prev = __tmp;
return __tmp;
}
iterator insert(iterator __position) { return insert(__position, _Tp()); }
void insert(iterator __position, const _Tp *__first, const _Tp *__last);
void insert(iterator __position,
const_iterator __first, const_iterator __last);
void insert(iterator __pos, size_type __n, const _Tp &__x)
{
_M_fill_insert(__pos, __n, __x);
}
void _M_fill_insert(iterator __pos, size_type __n, const _Tp &__x);
void push_front(const _Tp &__x) { insert(begin(), __x); }
void push_front() { insert(begin()); }
void push_back(const _Tp &__x) { insert(end(), __x); }
void push_back() { insert(end()); }
iterator erase(iterator __position)
{
_List_node_base *__next_node = __position._M_node->_M_next;
_List_node_base *__prev_node = __position._M_node->_M_prev;
_Node *__n = (_Node *)__position._M_node;
__prev_node->_M_next = __next_node;
__next_node->_M_prev = __prev_node;
_Destroy(&__n->_M_data);
_M_put_node(__n);
return iterator((_Node *)__next_node);
}
iterator erase(iterator __first, iterator __last);
void clear() { _Base::clear(); }
void resize(size_type __new_size, const _Tp &__x);
void resize(size_type __new_size) { this->resize(__new_size, _Tp()); }
void pop_front() { erase(begin()); }
void pop_back()
{
iterator __tmp = end();
erase(--__tmp);
}
// list的构造函数
list(size_type __n, const _Tp &__value,
const allocator_type &__a = allocator_type())
: _Base(__a)
{
insert(begin(), __n, __value);
}
// 初始化list的大小为n
explicit list(size_type __n)
: _Base(allocator_type())
{
insert(begin(), __n, _Tp());
}
list(const _Tp *__first, const _Tp *__last,
const allocator_type &__a = allocator_type())
: _Base(__a)
{
this->insert(begin(), __first, __last);
}
list(const_iterator __first, const_iterator __last,
const allocator_type &__a = allocator_type())
: _Base(__a)
{
this->insert(begin(), __first, __last);
}
list(const list<_Tp, _Alloc> &__x) : _Base(__x.get_allocator())
{
insert(begin(), __x.begin(), __x.end());
}
// 析构
~list() {}
list<_Tp, _Alloc> &operator=(const list<_Tp, _Alloc> &__x);
public:
// assign(), a generalized assignment member function. Two
// versions: one that takes a count, and one that takes a range.
// The range version is a member template, so we dispatch on whether
// or not the type is an integer.
// 清空容器，按照指定方式重新填充，与重载=的区别是它是重新生成元素的
void assign(size_type __n, const _Tp &__val) { _M_fill_assign(__n, __val); }
void _M_fill_assign(size_type __n, const _Tp &__val);
protected:
// ======================= 据说是list的精华？我来看看怎么个事 ======================
// 将某连续范围的元素移动到某个特定位置之前
void transfer(iterator __position, iterator __first, iterator __last)
{
if (__position != __last)
{
// Remove [first, last) from its old position.
__last._M_node->_M_prev->_M_next = __position._M_node;
__first._M_node->_M_prev->_M_next = __last._M_node;
__position._M_node->_M_prev->_M_next = __first._M_node;
// Splice [first, last) into its new position.
_List_node_base *__tmp = __position._M_node->_M_prev;
__position._M_node->_M_prev = __last._M_node->_M_prev;
__last._M_node->_M_prev = __first._M_node->_M_prev;
__first._M_node->_M_prev = __tmp;
}
}
public:
void splice(iterator __position, list &__x)
{
if (!__x.empty())
this->transfer(__position, __x.begin(), __x.end());
}
void splice(iterator __position, list &, iterator __i)
{
iterator __j = __i;
++__j;
if (__position == __i || __position == __j)
return;
this->transfer(__position, __i, __j);
}
void splice(iterator __position, list &, iterator __first, iterator __last)
{
if (__first != __last)
this->transfer(__position, __first, __last);
}
void remove(const _Tp &__value);
void unique();
void merge(list &__x);
void reverse();
void sort();
};
template <class _Tp, class _Alloc>
inline bool
operator==(const list<_Tp, _Alloc> &__x, const list<_Tp, _Alloc> &__y)
{
typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
const_iterator __end1 = __x.end();
const_iterator __end2 = __y.end();
const_iterator __i1 = __x.begin();
const_iterator __i2 = __y.begin();
while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
{
++__i1;
++__i2;
}
return __i1 == __end1 && __i2 == __end2;
}
template <class _Tp, class _Alloc>
inline bool operator<(const list<_Tp, _Alloc> &__x,
const list<_Tp, _Alloc> &__y)
{
return lexicographical_compare(__x.begin(), __x.end(),
__y.begin(), __y.end());
}
template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::insert(iterator __position,
const _Tp *__first, const _Tp *__last)
{
for (; __first != __last; ++__first)
insert(__position, *__first);
}
template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::insert(iterator __position,
const_iterator __first, const_iterator __last)
{
for (; __first != __last; ++__first)
insert(__position, *__first);
}
#endif /* __STL_MEMBER_TEMPLATES */
template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::_M_fill_insert(iterator __position,
size_type __n, const _Tp &__x)
{
for (; __n > 0; --__n)
insert(__position, __x);
}
template <class _Tp, class _Alloc>
typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::erase(iterator __first,
iterator __last)
{
while (__first != __last)
erase(__first++);
return __last;
}
template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp &__x)
{
iterator __i = begin();
size_type __len = 0;
for (; __i != end() && __len < __new_size; ++__i, ++__len)
;
if (__len == __new_size)
erase(__i, end());
else // __i == end()
insert(end(), __new_size - __len, __x);
}
template <class _Tp, class _Alloc>
list<_Tp, _Alloc> &list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc> &__x)
{
if (this != &__x)
{
iterator __first1 = begin();
iterator __last1 = end();
const_iterator __first2 = __x.begin();
const_iterator __last2 = __x.end();
while (__first1 != __last1 && __first2 != __last2)
*__first1++ = *__first2++;
if (__first2 == __last2)
erase(__first1, __last1);
else
insert(__last1, __first2, __last2);
}
return *this;
}
template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp &__val)
{
iterator __i = begin();
// 全部置换成val
for (; __i != end() && __n > 0; ++__i, --__n)
*__i = __val;
// 原链表长度不够，继续插入
if (__n > 0)
insert(end(), __n, __val);
// 擦除可能长出来的部分
else
erase(__i, end());
}
template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::remove(const _Tp &__value)
{
iterator __first = begin();
iterator __last = end();
while (__first != __last)
{
iterator __next = __first;
++__next;
if (*__first == __value)
erase(__first);
__first = __next;
}
}
// 移除值相同的连续元素
template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::unique()
{
iterator __first = begin();
iterator __last = end();
if (__first == __last)
return;
iterator __next = __first;
while (++__next != __last)
{
if (*__first == *__next)
erase(__next);
else
__first = __next;
__next = __first;
}
}
// 合并两条链表
template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc> &__x)
{
iterator __first1 = begin();
iterator __last1 = end();
iterator __first2 = __x.begin();
iterator __last2 = __x.end();
while (__first1 != __last1 && __first2 != __last2)
if (*__first2 < *__first1)
{
iterator __next = __first2;
transfer(__first1, __first2, ++__next);
__first2 = __next;
}
else
++__first1;
if (__first2 != __last2)
transfer(__last1, __first2, __last2);
}
inline void __List_base_reverse(_List_node_base *__p)
{
_List_node_base *__tmp = __p;
do
{
__STD::swap(__tmp->_M_next, __tmp->_M_prev);
__tmp = __tmp->_M_prev; // Old next node is now prev.
} while (__tmp != __p);
}
template <class _Tp, class _Alloc>
inline void list<_Tp, _Alloc>::reverse()
{
__List_base_reverse(this->_M_node);
}
// 归并排序
template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::sort()
{
// Do nothing if the list has length 0 or 1.
if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node)
{
list<_Tp, _Alloc> __carry;
list<_Tp, _Alloc> __counter[64];
int __fill = 0;
while (!empty())
{
__carry.splice(__carry.begin(), *this, begin());
int __i = 0;
while (__i < __fill && !__counter[__i].empty())
{
__counter[__i].merge(__carry);
__carry.swap(__counter[__i++]);
}
__carry.swap(__counter[__i]);
if (__i == __fill)
++__fill;
}
for (int __i = 1; __i < __fill; ++__i)
__counter[__i].merge(__counter[__i - 1]);
swap(__counter[__fill - 1]);
}
}
deque
vector是单向开口的连续线性内存空间，而deque则是双向开口的"连续线性内存空间"，双向开口意为可以从开头 和结尾很方便的进行插入或者删除操作，而vetor虽然也支持在头部插入，但是效率真的不忍直视
deque和vector的最大差异，一在于 deque 允许于常数时间内对起头端进行元素的插插入或移除操作，二在于deque 没有所谓容量（capacity）观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。 换句话说，像 vector 那样 “因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间” 这样的事情在deque 是不会发生的。也因此，deque没有必要提供所谓的空间保留（reserve）功能。
虽然 deque 也提供 Ramdon Access Iterator，但它的迭代器并不是普通指针，其复杂度和 vector 不可以道里计 (稍后看到源代码，你便知道)，这当然影响了各个运算层面。因此，除非必要，我们应尽可能选择使用 vector 而非 deque。对 deque 进行的排序操作，为了最高效率，可将 deque 先完整复制到一个 vector身上，将vector排序 后(利用 STL sort 算法)，再复制回 deque。
deque的中控器
deque为了实现分段的连续空间，采用了一块map(不是rb-tree的那个map)作为主控器，map是一小段连续空间， 里面每个元素(被称为node)都是指针，指向另一段比较大的线性连续空间(称为缓冲区)，缓冲区才是deque存储空间 的主体，SGI STL允许我们指定缓冲区大小，默认值0将会使用512byte作为缓冲区大小
// map
// ↓
// +----+----+----+----+
// | * | * | * | * |
// +----+----+----+----+
// ↓ ↓ ↓ ↓
// buffer0 buffer1 buffer2 buffer3
template <class _Tp, class _Alloc>
class _Deque_base
{
public:
// ...
protected:
_Tp **_M_map; // 中控器的定义在此
size_t _M_map_size; // map的大小(可以容纳多少个指针)
// ...
};
可以看到这里的中控器map实际上是一个指向指针的指针，而指针指向的则是一段连续的空间
deque的迭代器
值得注意的是，deque是分段连续空间，那么整体连续的任务就落到了迭代器的重载operator++, operator--身上
// 计算一个buffer中的元素个数，如果一个对象大小大于512，就是一个对象，如果小于512就是 512 / __size
inline size_t __deque_buf_size(size_t __size)
{
return __size < 512 ? size_t(512 / __size) : size_t(1);
}
template <class _Tp, class _Ref, class _Ptr>
struct _Deque_iterator
{
typedef _Deque_iterator<_Tp, _Tp &, _Tp *> iterator;
typedef _Deque_iterator<_Tp, const _Tp &, const _Tp *> const_iterator;
// 计算一个buffer中有几个对象
static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
// 线性空间肯定要支持随机访问，但是肯定不能是原生指针了
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Ptr pointer;
typedef _Ref reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef _Tp ** _Map_pointer;
typedef _Deque_iterator _Self;
_Tp* _M_cur; // iterator当前指向的buffer中对象所在位置
_Tp* _M_first; // 当前buffer的起始位置
_Tp* _M_last; // 当前buffer的结尾位置
_Map_pointer _M_node; // 指向map中的当前buffer
// map
// ┌────┬────┬────┐
// │buf0│buf1│buf2│
// └────┴────┴────┘
// ↑
// _M_node
// buffer1
// +---+---+---+---+
// | | X | | |
// +---+---+---+---+
// ↑ ↑ ↑
// first cur last
// 给定map中的buffer和x值
_Deque_iterator(_Tp *__x, _Map_pointer __y)
: _M_cur(__x)
, _M_first(*__y) // 对_Tp** 解引用得_Tp* 所指就是buffer的起始位置
, _M_last(*__y + _S_buffer_size())
, _M_node(__y)
{ }
// 空迭代器
_Deque_iterator()
: _M_cur(0)
, _M_first(0)
, _M_last(0)
, _M_node(0)
{ }
// 从另一个迭代器构造
_Deque_iterator(const iterator &__x)
: _M_cur(__x._M_cur)
, _M_first(__x._M_first)
, _M_last(__x._M_last)
, _M_node(__x._M_node)
{ }
reference operator*() const { return *_M_cur; }
pointer operator->() const { return _M_cur; }
difference_type operator-(const _Self &__x) const
{
return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
(_M_cur - _M_first) + (__x._M_last - __x._M_cur);
}
// !!! 重要函数 !!!，实现运算符重载的核心
// 传入一个新的node指针，改变first和last
void _M_set_node(_Map_pointer __new_node)
{
_M_node = __new_node;
_M_first = *__new_node;
_M_last = _M_first + difference_type(_S_buffer_size());
}
// 前置++
_Self &operator++()
{
++_M_cur;
if (_M_cur == _M_last)
{
_M_set_node(_M_node + 1);
_M_cur = _M_first;
}
return *this;
}
// 后置++
_Self operator++(int)
{
_Self __tmp = *this;
++*this;
return __tmp;
}
// 前置--
_Self &operator--()
{
if (_M_cur == _M_first)
{
_M_set_node(_M_node - 1);
_M_cur = _M_last;
}
--_M_cur;
return *this;
}
// 后置--
_Self operator--(int)
{
_Self __tmp = *this;
--*this;
return __tmp;
}
// 核心关键函数之一
_Self &operator+=(difference_type __n)
{
// 计算偏移量
difference_type __offset = __n + (_M_cur - _M_first);
// 偏移量还在当前buffer
if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
_M_cur += __n;
else
{
// 超出当前buffer了: 分为两种情况，一种是偏移量是负(往前node)，另一个则是向后走
difference_type __node_offset =
// 计算偏移了多少个node
__offset > 0 ? __offset / difference_type(_S_buffer_size())
: -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
_M_set_node(_M_node + __node_offset);
// 计算cur所指位置
_M_cur = _M_first +
(__offset - __node_offset * difference_type(_S_buffer_size()));
}
return *this;
}
// 复用+=
_Self operator+(difference_type __n) const
{
_Self __tmp = *this;
return __tmp += __n;
}
_Self &operator-=(difference_type __n) { return *this += -__n; }
_Self operator-(difference_type __n) const
{
_Self __tmp = *this;
return __tmp -= __n;
}
reference operator[](difference_type __n) const { return *(*this + __n); }
bool operator==(const _Self &__x) const { return _M_cur == __x._M_cur; }
bool operator!=(const _Self &__x) const { return !(*this == __x); }
bool operator<(const _Self &__x) const
{
return (_M_node == __x._M_node) ? (_M_cur < __x._M_cur) : (_M_node < __x._M_node);
}
bool operator>(const _Self &__x) const { return __x < *this; }
bool operator<=(const _Self &__x) const { return !(__x < *this); }
bool operator>=(const _Self &__x) const { return !(*this < __x); }
};
template <class _Tp, class _Ref, class _Ptr>
inline _Deque_iterator<_Tp, _Ref, _Ptr>
operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr> &__x)
{
return __x + __n;
}
#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
template <class _Tp, class _Ref, class _Ptr>
inline random_access_iterator_tag
iterator_category(const _Deque_iterator<_Tp, _Ref, _Ptr> &)
{
return random_access_iterator_tag();
}
template <class _Tp, class _Ref, class _Ptr>
inline _Tp *value_type(const _Deque_iterator<_Tp, _Ref, _Ptr> &) { return 0; }
template <class _Tp, class _Ref, class _Ptr>
inline ptrdiff_t *distance_type(const _Deque_iterator<_Tp, _Ref, _Ptr> &)
{
return 0;
}
deque的数据结构和内存管理
deque的设计仍然遵循了STL的设计规则，将内存管理和容器逻辑分开，deque的基类就是涉及到deque的内存管理 和成员管理
template <class _Tp, class _Alloc>
class _Deque_base
{
public:
typedef _Deque_iterator<_Tp, _Tp &, _Tp *> iterator;
typedef _Deque_iterator<_Tp, const _Tp &, const _Tp *> const_iterator;
typedef _Alloc allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
_Deque_base(const allocator_type &, size_t __num_elements)
: _M_map(0)
, _M_map_size(0)
, _M_start()
, _M_finish()
{
_M_initialize_map(__num_elements);
}
_Deque_base(const allocator_type &)
: _M_map(0)
, _M_map_size(0)
, _M_start()
, _M_finish()
{}
~_Deque_base();
protected:
// 三个重要函数
void _M_initialize_map(size_t);
void _M_create_nodes(_Tp **__nstart, _Tp **__nfinish);
void _M_destroy_nodes(_Tp **__nstart, _Tp **__nfinish);
enum { _S_initial_map_size = 8 };
protected:
// deque的成员变量
_Tp ** _M_map; // 我们上面所说的中控器map就是这个
size_t _M_map_size; // map可以存的指针的数量
iterator _M_start; // 在deque的内部还维护了两个迭代器 start指向第一块缓冲区的第一个元素
iterator _M_finish; // finish则指向最后一块缓冲区的最后一个元素
// 封装了simple_alloc，分别将量化对象从字节转化为缓冲区大小和一个指针的大小
typedef simple_alloc<_Tp, _Alloc> _Node_alloc_type; // 为node分配空间
typedef simple_alloc<_Tp *, _Alloc> _Map_alloc_type; // 为指针分配空间
_Tp *_M_allocate_node()
{
return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
}
void _M_deallocate_node(_Tp *__p)
{
_Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
}
_Tp **_M_allocate_map(size_t __n)
{
return _Map_alloc_type::allocate(__n);
}
void _M_deallocate_map(_Tp **__p, size_t __n)
{
_Map_alloc_type::deallocate(__p, __n);
}
};
template <class _Tp, class _Alloc>
_Deque_base<_Tp, _Alloc>::~_Deque_base()
{
if (_M_map)
{
// 先销毁后释放
_M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
_M_deallocate_map(_M_map, _M_map_size);
}
}
// 初始化map(中控器)，根据要设置的元素数量
template <class _Tp, class _Alloc>
void _Deque_base<_Tp, _Alloc>::_M_initialize_map(size_t __num_elements)
{
// 计算需要多少个node(多备一个)
size_t __num_nodes =
__num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
// 用之前计算出来需要的node + 2与默认的node数量比较取一个最大值，+2的原因是为了两端扩展
_M_map_size = max((size_t)_S_initial_map_size, __num_nodes + 2);
// 给map分配内存
_M_map = _M_allocate_map(_M_map_size);
// 尽量将start和finish设在中间
_Tp **__nstart = _M_map + (_M_map_size - __num_nodes) / 2;
_Tp **__nfinish = __nstart + __num_nodes;
__STL_TRY
{
// 构造节点
_M_create_nodes(__nstart, __nfinish);
}
// 如果有一个构造失败就全部析构
__STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size), _M_map = 0, _M_map_size = 0));
// 设置两个迭代器(start和finish)的node
_M_start._M_set_node(__nstart);
_M_finish._M_set_node(__nfinish - 1);
// 找第一个元素和最后一个元素
_M_start._M_cur = _M_start._M_first;
_M_finish._M_cur = _M_finish._M_first+__num_elements % __deque_buf_size(sizeof(_Tp));
}
template <class _Tp, class _Alloc>
void _Deque_base<_Tp, _Alloc>::_M_create_nodes(_Tp **__nstart, _Tp **__nfinish)
{
_Tp **__cur;
__STL_TRY
{
for (__cur = __nstart; __cur < __nfinish; ++__cur)
*__cur = _M_allocate_node();
}
__STL_UNWIND(_M_destroy_nodes(__nstart, __cur));
}
template <class _Tp, class _Alloc>
void _Deque_base<_Tp, _Alloc>::_M_destroy_nodes(_Tp **__nstart, _Tp **__nfinish)
{
for (_Tp **__n = __nstart; __n < __nfinish; ++__n)
_M_deallocate_node(*__n);
}
deque的内部完整实现
注意，由于deque的结构比vector和list复杂的多，所以源码长度也更长了，为了方便叙述，我在这里直接将所有源码 贴出来，但是并不是一下看完，我们将会从下面几步抽丝剥茧，一点一点窥探deque的奥妙:
- deque的基本访问[begin(), end() ...]
- deque的构造和析构
- deque的元素操作(push_*, pop_*, insert(), erase())
- 辅助函数 ...
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp)>
class deque : protected _Deque_base<_Tp, _Alloc>
{
// requirements:
__STL_CLASS_REQUIRES(_Tp, _Assignable);
typedef _Deque_base<_Tp, _Alloc> _Base;
public: // Basic types
typedef _Tp value_type;
typedef value_type *pointer;
typedef const value_type *const_pointer;
typedef value_type &reference;
typedef const value_type &const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef typename _Base::allocator_type allocator_type;
allocator_type get_allocator() const { return _Base::get_allocator(); }
public: // Iterators
typedef typename _Base::iterator iterator;
typedef typename _Base::const_iterator const_iterator;
typedef reverse_iterator<const_iterator, value_type, const_reference,
difference_type>
const_reverse_iterator;
typedef reverse_iterator<iterator, value_type, reference, difference_type>
reverse_iterator;
protected: // Internal typedefs
// 与迭代器中定义的一样，map_ptr就是指向map的指针
typedef pointer *_Map_pointer;
// 用来计算一个buffer中有多少个独享的函数
static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
public: // Basic accessors
// deque的基本访问
// 在deque的基类中维护了两个迭代器: start, last,
// 通过这两个基本迭代器和重载的迭代器运算符
iterator begin() { return _M_start; }
iterator end() { return _M_finish; }
const_iterator begin() const { return _M_start; }
const_iterator end() const { return _M_finish; }
reverse_iterator rbegin() { return reverse_iterator(_M_finish); }
reverse_iterator rend() { return reverse_iterator(_M_start); }
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(_M_finish);
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(_M_start);
}
reference operator[](size_type __n)
{
return _M_start[difference_type(__n)];
}
const_reference operator[](size_type __n) const
{
return _M_start[difference_type(__n)];
}
reference front() { return *_M_start; }
reference back()
{
iterator __tmp = _M_finish;
--__tmp;
return *__tmp;
}
const_reference front() const { return *_M_start; }
const_reference back() const
{
const_iterator __tmp = _M_finish;
--__tmp;
return *__tmp;
}
size_type size() const { return _M_finish - _M_start; }
size_type max_size() const { return size_type(-1); }
bool empty() const { return _M_finish == _M_start; }
public: // Constructor, destructor.
// 构造
explicit deque(const allocator_type &__a = allocator_type())
: _Base(__a, 0)
{}
// 拷贝构造
deque(const deque &__x)
: _Base(__x.get_allocator() , __x.size())
{
uninitialized_copy(__x.begin(), __x.end(), _M_start);
}
// 给deque构造n个value
deque(size_type __n, const value_type &__value,
const allocator_type &__a = allocator_type())
// 空间已经在构造基类的时候就已经配置好了
// 在构建派生类的时候，如果基类有默认构造可以不显式调用，但是如果没有，则必须在派生类中显示调用
// 默认构造: 无参数或者参数有缺省值或编译器自动生成
: _Base(__a, __n)
{
_M_fill_initialize(__value);
}
// 禁止隐式类型转换
explicit deque(size_type __n) : _Base(allocator_type(), __n)
{
_M_fill_initialize(value_type());
}
deque(const value_type *__first, const value_type *__last,
const allocator_type &__a = allocator_type())
: _Base(__a, __last - __first)
{
uninitialized_copy(__first, __last, _M_start);
}
deque(const_iterator __first, const_iterator __last,
const allocator_type &__a = allocator_type())
: _Base(__a, __last - __first)
{
uninitialized_copy(__first, __last, _M_start);
}
// 析构
~deque() { destroy(_M_start, _M_finish); }
deque &operator=(const deque &__x)
{
const size_type __len = size();
if (&__x != this)
{
if (__len >= __x.size())
erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
else
{
const_iterator __mid = __x.begin() + difference_type(__len);
copy(__x.begin(), __mid, _M_start);
insert(_M_finish, __mid, __x.end());
}
}
return *this;
}
void swap(deque &__x)
{
__STD::swap(_M_start, __x._M_start);
__STD::swap(_M_finish, __x._M_finish);
__STD::swap(_M_map, __x._M_map);
__STD::swap(_M_map_size, __x._M_map_size);
}
public:
// assign(), a generalized assignment member function. Two
// versions: one that takes a count, and one that takes a range.
// The range version is a member template, so we dispatch on whether
// or not the type is an integer.
void _M_fill_assign(size_type __n, const _Tp &__val)
{
if (__n > size())
{
fill(begin(), end(), __val);
insert(end(), __n - size(), __val);
}
else
{
erase(begin() + __n, end());
fill(begin(), end(), __val);
}
}
void assign(size_type __n, const _Tp &__val)
{
_M_fill_assign(__n, __val);
}
public: // push_* and pop_*
// deque的关键之点！！！
// 尾插整个流程
// push_back
// │
// ├─ buffer有空间
// │ construct
// │
// └─ buffer满
// │
// ├─ reserve_map_at_back
// │ │
// │ └─ reallocate_map (必要时)
// │
// ├─ allocate new buffer
// │
// ├─ construct element
// │
// └─ finish移动到新buffer
void push_back(const value_type &__t)
{
// 如果最后一个buffer中有至少！！！两个！！！空位
if (_M_finish._M_cur != _M_finish._M_last - 1)
{
// 直接构造
construct(_M_finish._M_cur, __t);
++_M_finish._M_cur;
}
else
// 空位不足，调用aux
_M_push_back_aux(__t);
}
// deque 的扩展不是扩容数据，而是扩展buffer(node)或map
template <class _Tp, class _Alloc>
void deque<_Tp, _Alloc>::_M_push_back_aux()
{
_M_reserve_map_at_back();
*(_M_finish._M_node + 1) = _M_allocate_node();
__STL_TRY
{
construct(_M_finish._M_cur);
_M_finish._M_set_node(_M_finish._M_node + 1);
_M_finish._M_cur = _M_finish._M_first;
}
__STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
}
void _M_reserve_map_at_back(size_type __nodes_to_add = 1)
{
// 如果map尾端空间不足，则需要调用realloc来换一个map
if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
_M_reallocate_map(__nodes_to_add, false);
}
// ====================== 核心函数(对map的重新布局) ======================
template <class _Tp, class _Alloc>
void deque<_Tp, _Alloc>::_M_reallocate_map(size_type __nodes_to_add,
bool __add_at_front)
{
// 计算原来node数量
size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
// 计算新map中node的数量
size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
// 定义一个新的map起点
_Map_pointer __new_nstart;
// 情况1: 原map的空间够大
if (_M_map_size > 2 * __new_num_nodes)
{
// 重新计算map的起点
__new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2 + (__add_at_front ? __nodes_to_add : 0);
// 向左移动
if (__new_nstart < _M_start._M_node)
copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
// 向后移动
else
copy_backward(_M_start._M_node, _M_finish._M_node + 1,
__new_nstart + __old_num_nodes);
}
// 情况2: 原map的大小也不够了
else
{
// 计算新的map大小
size_type __new_map_size =
_M_map_size + max(_M_map_size, __nodes_to_add) + 2;
// 给新map开辟空间
_Map_pointer __new_map = _M_allocate_map(__new_map_size);
// 居中放置node
__new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 + (__add_at_front ? __nodes_to_add : 0);
// 把原来的map拷贝到新的map中
copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
// 销毁原来map的空间
_M_deallocate_map(_M_map, _M_map_size);
_M_map = __new_map;
_M_map_size = __new_map_size;
}
// 重新定义迭代器指向
_M_start._M_set_node(__new_nstart);
_M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
}
void push_back()
{
if (_M_finish._M_cur != _M_finish._M_last - 1)
{
construct(_M_finish._M_cur);
++_M_finish._M_cur;
}
else
_M_push_back_aux();
}
// push_front流程与push_back()类似，最后如果空间不足都要调用reallocate_map
void push_front(const value_type &__t)
{
// 这里不需要预留一个空位!!!!只需要有空位就能插入
if (_M_start._M_cur != _M_start._M_first)
{
construct(_M_start._M_cur - 1, __t);
--_M_start._M_cur;
}
else
_M_push_front_aux(__t);
}
template <class _Tp, class _Alloc>
void deque<_Tp, _Alloc>::_M_push_front_aux(const value_type &__t)
{
value_type __t_copy = __t;
_M_reserve_map_at_front();
*(_M_start._M_node - 1) = _M_allocate_node();
__STL_TRY
{
_M_start._M_set_node(_M_start._M_node - 1);
_M_start._M_cur = _M_start._M_last - 1;
construct(_M_start._M_cur, __t_copy);
}
__STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
}
void _M_reserve_map_at_front(size_type __nodes_to_add = 1)
{
if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
_M_reallocate_map(__nodes_to_add, true);
}
void push_front()
{
if (_M_start._M_cur != _M_start._M_first)
{
construct(_M_start._M_cur - 1);
--_M_start._M_cur;
}
else
_M_push_front_aux();
}
// 上面两个push_*需要注意的是，在尾插的时候需要最少预留两个空位，而头插只需要有一个空位就行
// 究其原因STL的标准是设计迭代器的时候是[first,finish)前闭后开，为了保证iterator的不变量原则
// 尾插的时候必须要预留一个空间，否则就会导致cur == finish
void pop_back()
{
// 判断这个buffer是不是空了，如果空了就释放整个缓冲区
if (_M_finish._M_cur != _M_finish._M_first)
{
--_M_finish._M_cur;
destroy(_M_finish._M_cur);
}
else
// 释放整个缓冲区
_M_pop_back_aux();
}
void pop_front()
{
// 判断这个buffer是否有两个或以上元素，如果还剩一个就清空整个缓冲区！！！
if (_M_start._M_cur != _M_start._M_last - 1)
{
destroy(_M_start._M_cur);
++_M_start._M_cur;
}
else
// 还剩一个元素，清空整个缓冲区！！！
_M_pop_front_aux();
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_pop_back_aux()
{
_M_deallocate_node(_M_finish._M_first);
_M_finish._M_set_node(_M_finish._M_node - 1);
_M_finish._M_cur = _M_finish._M_last - 1;
destroy(_M_finish._M_cur);
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_pop_front_aux()
{
destroy(_M_start._M_cur);
_M_deallocate_node(_M_start._M_first);
_M_start._M_set_node(_M_start._M_node + 1);
_M_start._M_cur = _M_start._M_first;
}
// 这里逻辑与push是完全反过来的，究其原因仍然还是因为这个STL的左闭右开结构
// 但是这次是头删会访问到边界！！！
public: // Insert
iterator insert(iterator position, const value_type &__x)
{
// 如果插入点在最前面，就直接调用push_front
if (position._M_cur == _M_start._M_cur)
{
push_front(__x);
return _M_start;
}
// 在最后就调用push_back
else if (position._M_cur == _M_finish._M_cur)
{
push_back(__x);
iterator __tmp = _M_finish;
--__tmp;
return __tmp;
}
else
{
// 否则进入插入逻辑
return _M_insert_aux(position, __x);
}
}
template <class _Tp, class _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::_M_insert_aux(iterator __pos, const value_type &__x)
{
// 计算插入点前面的元素数量
difference_type __index = __pos - _M_start;
// 保存插入值
value_type __x_copy = __x;
// 如果插入点前面的值较少
if (size_type(__index) < this->size() / 2)
{
// 在最前面插入第一个元素
push_front(front());
// 然后再将插入点前面的元素前移
iterator __front1 = _M_start;
++__front1;
iterator __front2 = __front1;
++__front2;
__pos = _M_start + __index;
iterator __pos1 = __pos;
++__pos1;
copy(__front2, __pos1, __front1);
}
else
{
// 在最后插入最后一个元素
push_back(back());
// 将插入点后面的元素后移
iterator __back1 = _M_finish;
--__back1;
iterator __back2 = __back1;
--__back2;
__pos = _M_start + __index;
copy_backward(__pos, __back2, __back1);
}
// 将元素插入
*__pos = __x_copy;
return __pos;
}
iterator insert(iterator __position)
{
return insert(__position, value_type());
}
void insert(iterator __pos, size_type __n, const value_type &__x)
{
_M_fill_insert(__pos, __n, __x);
}
void _M_fill_insert(iterator __pos, size_type __n, const value_type &__x);
void insert(iterator __pos,
const value_type *__first, const value_type *__last);
void insert(iterator __pos,
const_iterator __first, const_iterator __last);
void resize(size_type __new_size, const value_type &__x)
{
const size_type __len = size();
if (__new_size < __len)
erase(_M_start + __new_size, _M_finish);
else
insert(_M_finish, __new_size - __len, __x);
}
void resize(size_type new_size) { resize(new_size, value_type()); }
public: // Erase
iterator erase(iterator __pos)
{
iterator __next = __pos;
++__next;
difference_type __index = __pos - _M_start;
if (size_type(__index) < (this->size() >> 1))
{
copy_backward(_M_start, __pos, __next);
pop_front();
}
else
{
copy(__next, _M_finish, __pos);
pop_back();
}
return _M_start + __index;
}
iterator erase(iterator __first, iterator __last);
void clear();
protected: // Internal insert functions
iterator _M_reserve_elements_at_front(size_type __n)
{
size_type __vacancies = _M_start._M_cur - _M_start._M_first;
if (__n > __vacancies)
_M_new_elements_at_front(__n - __vacancies);
return _M_start - difference_type(__n);
}
iterator _M_reserve_elements_at_back(size_type __n)
{
size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
if (__n > __vacancies)
_M_new_elements_at_back(__n - __vacancies);
return _M_finish + difference_type(__n);
}
void _M_new_elements_at_front(size_type __new_elements);
void _M_new_elements_at_back(size_type __new_elements);
};
// Non-inline member functions
template <class _Tp, class _Alloc>
void deque<_Tp, _Alloc>::_M_fill_insert(iterator __pos,
size_type __n, const value_type &__x)
{
if (__pos._M_cur == _M_start._M_cur)
{
iterator __new_start = _M_reserve_elements_at_front(__n);
__STL_TRY
{
uninitialized_fill(__new_start, _M_start, __x);
_M_start = __new_start;
}
__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
}
else if (__pos._M_cur == _M_finish._M_cur)
{
iterator __new_finish = _M_reserve_elements_at_back(__n);
__STL_TRY
{
uninitialized_fill(_M_finish, __new_finish, __x);
_M_finish = __new_finish;
}
__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
__new_finish._M_node + 1));
}
else
_M_insert_aux(__pos, __n, __x);
}
template <class _Tp, class _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::erase(iterator __first, iterator __last)
{
if (__first == _M_start && __last == _M_finish)
{
clear();
return _M_finish;
}
else
{
difference_type __n = __last - __first;
difference_type __elems_before = __first - _M_start;
if (__elems_before < difference_type((this->size() - __n) / 2))
{
copy_backward(_M_start, __first, __last);
iterator __new_start = _M_start + __n;
destroy(_M_start, __new_start);
_M_destroy_nodes(__new_start._M_node, _M_start._M_node);
_M_start = __new_start;
}
else
{
copy(__last, _M_finish, __first);
iterator __new_finish = _M_finish - __n;
destroy(__new_finish, _M_finish);
_M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
_M_finish = __new_finish;
}
return _M_start + __elems_before;
}
}
template <class _Tp, class _Alloc>
void deque<_Tp, _Alloc>::clear()
{
for (_Map_pointer __node = _M_start._M_node + 1;
__node < _M_finish._M_node;
++__node)
{
destroy(*__node, *__node + _S_buffer_size());
_M_deallocate_node(*__node);
}
if (_M_start._M_node != _M_finish._M_node)
{
destroy(_M_start._M_cur, _M_start._M_last);
destroy(_M_finish._M_first, _M_finish._M_cur);
_M_deallocate_node(_M_finish._M_first);
}
else
destroy(_M_start._M_cur, _M_finish._M_cur);
_M_finish = _M_start;
}
template <class _Tp, class _Alloc>
void deque<_Tp, _Alloc>::_M_new_elements_at_front(size_type __new_elems)
{
size_type __new_nodes = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
_M_reserve_map_at_front(__new_nodes);
size_type __i;
__STL_TRY
{
for (__i = 1; __i <= __new_nodes; ++__i)
*(_M_start._M_node - __i) = _M_allocate_node();
}
}
template <class _Tp, class _Alloc>
void deque<_Tp, _Alloc>::_M_new_elements_at_back(size_type __new_elems)
{
size_type __new_nodes = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
_M_reserve_map_at_back(__new_nodes);
size_type __i;
__STL_TRY
{
for (__i = 1; __i <= __new_nodes; ++__i)
*(_M_finish._M_node + __i) = _M_allocate_node();
}
}
// Nonmember functions.
template <class _Tp, class _Alloc>
inline bool operator==(const deque<_Tp, _Alloc> &__x,
const deque<_Tp, _Alloc> &__y)
{
return __x.size() == __y.size() &&
equal(__x.begin(), __x.end(), __y.begin());
}
template <class _Tp, class _Alloc>
inline bool operator<(const deque<_Tp, _Alloc> &__x,
const deque<_Tp, _Alloc> &__y)
{
return lexicographical_compare(__x.begin(), __x.end(),
__y.begin(), __y.end());
}
stack
栈是一种先进后出的数据结构，如果用一种底层容器封装后可以符合这种特性，形成一个stack是挺容易的，因此 SGI STL就是用deque，封住其一端来形成了stack，因此stack的形成比较简单，STL中stack往往不被称为容器 而是一种配接器(adapter)，是一种容器配接器(container adapter)。且由于stack要求先进先出不支持遍历， 所以stack根本就么得迭代器！！！ 完整源码如下:
// 默认用deque作为底层数据结构进行封装
template <class _Tp,
class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(deque<_Tp>)>
class stack;
template <class _Tp, class _Seq>
bool operator==(const stack<_Tp, _Seq> &__x, const stack<_Tp, _Seq> &__y);
template <class _Tp, class _Seq>
bool operator<(const stack<_Tp, _Seq> &__x, const stack<_Tp, _Seq> &__y);
template <class _Tp, class _Sequence>
class stack
{
__STL_CLASS_REQUIRES(_Tp, _Assignable);
__STL_CLASS_REQUIRES(_Sequence, _BackInsertionSequence);
typedef typename _Sequence::value_type _Sequence_value_type;
__STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Sequence_value_type);
friend bool __STD_QUALIFIER
operator== __STL_NULL_TMPL_ARGS(const stack &, const stack &);
friend bool __STD_QUALIFIER
operator<__STL_NULL_TMPL_ARGS(const stack &, const stack &);
public:
typedef typename _Sequence::value_type value_type;
typedef typename _Sequence::size_type size_type;
typedef _Sequence container_type;
typedef typename _Sequence::reference reference;
typedef typename _Sequence::const_reference const_reference;
protected:
// 底层序列式容器 - deque
_Sequence c;
public:
stack() : c() {}
explicit stack(const _Sequence &__s) : c(__s) {}
// stack选择封住deque的头部，只使用deque的尾部来进行插入删除操作
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference top() { return c.back(); }
const_reference top() const { return c.back(); }
void push(const value_type &__x) { c.push_back(__x); }
void pop() { c.pop_back(); }
};
template <class _Tp, class _Seq>
bool operator==(const stack<_Tp, _Seq> &__x, const stack<_Tp, _Seq> &__y)
{
return __x.c == __y.c;
}
template <class _Tp, class _Seq>
bool operator<(const stack<_Tp, _Seq> &__x, const stack<_Tp, _Seq> &__y)
{
return __x.c < __y.c;
}
queue
队列是一种先进先出的数据结构，它与stack类似，也可以通过一种底层容器封装而来，SGI STL仍然使用了deque来 封装，说明queue也是一种container adapter！！！ 下面贴出queue的源码，如果你理解deque了，看下面的源码将会有如砍瓜切菜
template <class _Tp,
class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(deque<_Tp>)>
class queue;
template <class _Tp, class _Seq>
inline bool operator==(const queue<_Tp, _Seq> &, const queue<_Tp, _Seq> &);
template <class _Tp, class _Seq>
inline bool operator<(const queue<_Tp, _Seq> &, const queue<_Tp, _Seq> &);
template <class _Tp, class _Sequence>
class queue
{
__STL_CLASS_REQUIRES(_Tp, _Assignable);
__STL_CLASS_REQUIRES(_Sequence, _FrontInsertionSequence);
__STL_CLASS_REQUIRES(_Sequence, _BackInsertionSequence);
typedef typename _Sequence::value_type _Sequence_value_type;
__STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Sequence_value_type);
friend bool __STD_QUALIFIER
operator== __STL_NULL_TMPL_ARGS(const queue &, const queue &);
friend bool __STD_QUALIFIER
operator<__STL_NULL_TMPL_ARGS(const queue &, const queue &);
public:
typedef typename _Sequence::value_type value_type;
typedef typename _Sequence::size_type size_type;
typedef _Sequence container_type;
typedef typename _Sequence::reference reference;
typedef typename _Sequence::const_reference const_reference;
protected:
_Sequence c;
public:
queue() : c() {}
explicit queue(const _Sequence &__c) : c(__c) {}
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 pop() { c.pop_front(); }
};
template <class _Tp, class _Sequence>
bool operator==(const queue<_Tp, _Sequence> &__x, const queue<_Tp, _Sequence> &__y)
{
return __x.c == __y.c;
}
template <class _Tp, class _Sequence>
bool operator<(const queue<_Tp, _Sequence> &__x, const queue<_Tp, _Sequence> &__y)
{
return __x.c < __y.c;
}
heap
heap并不存在于STL容器组件中，那为什么还要讲它呢？其原因是因为heap是priority_queue的助手， SGI STL的`stl_heap.h`中，heap就是一组算法，heap是一个用数组模拟的完全二叉树，所以heap 底层也借用了vector来实现(push_heap, pop_heap, make_heap, sort_heap) heap源码实现
// 默认实现版本，按照 < 逻辑比较的
template <class _RandomAccessIterator, class _Distance, class _Tp>
// 参数: 数组起始指针，插入元素的位置，堆顶位置， 插入的值
void __push_heap(_RandomAccessIterator __first,
_Distance __holeIndex, _Distance __topIndex, _Tp __value)
{
// 计算插入节点的父节点插入下标: parent = (index - 1) / 2
_Distance __parent = (__holeIndex - 1) / 2;
// 当节点还没调整到根节点且父节点的值小于插入值
while (__holeIndex > __topIndex && *(__first + __parent) < __value)
{
// 就将父节点填到插入位置
*(__first + __holeIndex) = *(__first + __parent);
// 重新计算父亲节点下标更新
__holeIndex = __parent;
__parent = (__holeIndex - 1) / 2;
}
// 将值插入计算的位置
*(__first + __holeIndex) = __value;
}
template <class _RandomAccessIterator, class _Distance, class _Tp>
inline void
// 传入起始节点的迭代器，后面两个用于类型推导
__push_heap_aux(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Distance *, _Tp *)
{
__push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
_Tp(*(__last - 1)));
}
// push_heap顾名思义就是向堆中插入一个数据，stl默认给的是大根堆
template <class _RandomAccessIterator>
inline void
// 传入两个迭代器，分别指向vector的头和尾，假设新增元素已经添加到vector的结尾了
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
__STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
_LessThanComparable);
__push_heap_aux(__first, __last,
__DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
}
// 用户自己传比较函数版本，除了比较逻辑不通，其余逻辑完全相同
template <class _RandomAccessIterator, class _Distance, class _Tp,
class _Compare>
void
__push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
_Distance __topIndex, _Tp __value, _Compare __comp)
{
_Distance __parent = (__holeIndex - 1) / 2;
while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value))
{
*(__first + __holeIndex) = *(__first + __parent);
__holeIndex = __parent;
__parent = (__holeIndex - 1) / 2;
}
*(__first + __holeIndex) = __value;
}
template <class _RandomAccessIterator, class _Compare,
class _Distance, class _Tp>
inline void
__push_heap_aux(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp,
_Distance *, _Tp *)
{
__push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
_Tp(*(__last - 1)), __comp);
}
template <class _RandomAccessIterator, class _Compare>
inline void
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
__push_heap_aux(__first, __last, __comp,
__DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
}
// poo_heap逻辑开始 最重要的调整函数: 注意!!! pop并不直接删除元素，而是逻辑移动!!!
// 堆顶指针，根节点下标，元素个数，保存的元素
template <class _RandomAccessIterator, class _Distance, class _Tp>
void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
_Distance __len, _Tp __value)
{
// 保存根节点位置
_Distance __topIndex = __holeIndex;
// 右孩子位置
_Distance __secondChild = 2 * __holeIndex + 2;
// 当右孩子下标小于heap size的时候
while (__secondChild < __len)
{
// 如果右孩子小于左孩子，更新孩子到左孩子
if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
__secondChild--;
// 把较大的孩子提到hole(第一次的时候就是提到hole)
*(__first + __holeIndex) = *(__first + __secondChild);
// 再把较大孩子的位置设为hole，重新比较左右孩子大小
__holeIndex = __secondChild;
// 更新为右孩子
__secondChild = 2 * (__secondChild + 1);
}
// 右孩子不存在了，只存在左孩子
if (__secondChild == __len)
{
// 依旧迭代
*(__first + __holeIndex) = *(__first + (__secondChild - 1));
__holeIndex = __secondChild - 1;
}
// 最后一步在叶子节点处调用push_heap逻辑插入value，如果不符合则继续上调
__push_heap(__first, __holeIndex, __topIndex, __value);
}
template <class _RandomAccessIterator, class _Tp, class _Distance>
inline void
// 参数: vector的头，vector的尾，pop出的元素要放置的位置，原heap最后一个元素
__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_RandomAccessIterator __result, _Tp __value, _Distance *)
{
// 把最大值放到最后，代表要pop的元素，可以直接覆盖的原因是已经保存了原heap的值
*__result = *__first;
__adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
}
template <class _RandomAccessIterator, class _Tp>
inline void
__pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Tp *)
{
__pop_heap(__first, __last - 1, __last - 1,
_Tp(*(__last - 1)), __DISTANCE_TYPE(__first));
}
// 传入起始的两个迭代器指针分别指向开头和结尾
template <class _RandomAccessIterator>
inline void pop_heap(_RandomAccessIterator __first,
_RandomAccessIterator __last)
{
__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
__STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
_LessThanComparable);
__pop_heap_aux(__first, __last, __VALUE_TYPE(__first));
}
// 自定义比较函数部分
template <class _RandomAccessIterator, class _Distance,
class _Tp, class _Compare>
void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
_Distance __len, _Tp __value, _Compare __comp)
{
_Distance __topIndex = __holeIndex;
_Distance __secondChild = 2 * __holeIndex + 2;
while (__secondChild < __len)
{
if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
__secondChild--;
*(__first + __holeIndex) = *(__first + __secondChild);
__holeIndex = __secondChild;
__secondChild = 2 * (__secondChild + 1);
}
if (__secondChild == __len)
{
*(__first + __holeIndex) = *(__first + (__secondChild - 1));
__holeIndex = __secondChild - 1;
}
__push_heap(__first, __holeIndex, __topIndex, __value, __comp);
}
template <class _RandomAccessIterator, class _Tp, class _Compare,
class _Distance>
inline void
__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_RandomAccessIterator __result, _Tp __value, _Compare __comp,
_Distance *)
{
*__result = *__first;
__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
__value, __comp);
}
template <class _RandomAccessIterator, class _Tp, class _Compare>
inline void
__pop_heap_aux(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Tp *, _Compare __comp)
{
__pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
__DISTANCE_TYPE(__first));
}
template <class _RandomAccessIterator, class _Compare>
inline void
pop_heap(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
__pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp);
}
// 传入一堆值来构造一个堆
template <class _RandomAccessIterator, class _Tp, class _Distance>
void __make_heap(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Tp *, _Distance *)
{
// 长度小于1，不用排序了
if (__last - __first < 2)
return;
_Distance __len = __last - __first;
// 计算最后一个节点的父节点(((__len - 1) - 1) / 2)
// 最后一个节点下标(__len - 1)
_Distance __parent = (__len - 2) / 2;
while (true)
{
// 从最后一个父节点开始调整
__adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
// 调整到根节点停止
if (__parent == 0)
return;
__parent--;
}
}
template <class _RandomAccessIterator>
inline void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
__STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
_LessThanComparable);
__make_heap(__first, __last,
__VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
}
// 自定义比较函数的部分
template <class _RandomAccessIterator, class _Compare,
class _Tp, class _Distance>
void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp, _Tp *, _Distance *)
{
if (__last - __first < 2)
return;
_Distance __len = __last - __first;
_Distance __parent = (__len - 2) / 2;
while (true)
{
__adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
__comp);
if (__parent == 0)
return;
__parent--;
}
}
template <class _RandomAccessIterator, class _Compare>
inline void
make_heap(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
__make_heap(__first, __last, __comp,
__VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
}
// 堆排序 - 在使用之前默认它是一个heap了所以调用之前要先make_heap
template <class _RandomAccessIterator>
void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
__STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
_LessThanComparable);
while (__last - __first > 1)
pop_heap(__first, __last--);
}
template <class _RandomAccessIterator, class _Compare>
void sort_heap(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
__STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
while (__last - __first > 1)
pop_heap(__first, __last--, __comp);
}
priority_queue(优先级队列)
priority_queue是带有权值的队列，它是用一个max-heap封装完成的，而heap又是在vector的基础上 完成的，所以从底层上来看，priority_queue实际上也是一个container adaptor，它是由vector 加上heap的算法来完成的
template <class _Tp,
class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(vector<_Tp>),
class _Compare
__STL_DEPENDENT_DEFAULT_TMPL(less<typename _Sequence::value_type>)>
class priority_queue
{
__STL_CLASS_REQUIRES(_Tp, _Assignable);
__STL_CLASS_REQUIRES(_Sequence, _Sequence);
__STL_CLASS_REQUIRES(_Sequence, _RandomAccessContainer);
typedef typename _Sequence::value_type _Sequence_value_type;
__STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Sequence_value_type);
__STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp);
public:
typedef typename _Sequence::value_type value_type;
typedef typename _Sequence::size_type size_type;
typedef _Sequence container_type;
typedef typename _Sequence::reference reference;
typedef typename _Sequence::const_reference const_reference;
protected:
_Sequence c;
_Compare comp;
public:
priority_queue()
: c()
{}
explicit priority_queue(const _Compare &__x)
: c()
, comp(__x)
{}
priority_queue(const _Compare &__x, const _Sequence &__s)
: c(__s)
, comp(__x)
{
make_heap(c.begin(), c.end(), comp);
}
priority_queue(const value_type *__first, const value_type *__last)
: c(__first, __last)
{ make_heap(c.begin(), c.end(), comp); }
priority_queue(const value_type *__first, const value_type *__last,
const _Compare &__x)
: c(__first, __last)
, comp(__x)
{
make_heap(c.begin(), c.end(), comp);
}
priority_queue(const value_type *__first, const value_type *__last,
const _Compare &__x, const _Sequence &__c)
: c(__c)
, comp(__x)
{
c.insert(c.end(), __first, __last);
make_heap(c.begin(), c.end(), comp);
}
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
const_reference top() const { return c.front(); }
void push(const value_type &__x)
{
__STL_TRY
{
// 先在vector中插入再调用push_heap维护heap的结构
c.push_back(__x);
push_heap(c.begin(), c.end(), comp);
}
__STL_UNWIND(c.clear());
}
void pop()
{
__STL_TRY
{
// 先把vector的元素删掉再调用pop_heap维护heap结构
pop_heap(c.begin(), c.end(), comp);
c.pop_back();
}
__STL_UNWIND(c.clear());
}
};