一、STL概述
- 容器：各种数据结构，如vector、list、deque、set、map，用来存放数据
- 算法：算法可以独立出来，通过迭代器作用到多种容器
- 迭代器：迭代器用来实现容器中元素的访问，是算法和容器之间的桥梁
- 仿函数：仿函数是一种用来实现函数功能的class
- 适配器：适配器用做对象的包装，使之适应不同的接口实现
- 空间配置器：空间配置器用来给容器分配内存大小
各个组件之间的联系如下：
container通过allocator取得数据存储空间，algorithm通过iterator存取container内容，functor协助algorithm完成不同策略变化，adapter可以修饰或套接functor。
二、空间配置器
此处涉及的知识点有点复杂。。。说实话我也没有怎么看明白。从一个例子开始介绍：当用户创建了一个vector容器之后，STL内部所做的工作如图所示：
从用户代码std::vector<int> v;开始，vector的模板参数class T被替换为int，同时第二个模板参数因为没有指定，所以为默认模板参数，即allocator<int>，这个vector对象v会在内部实例一个allocator<int>的对象，用来管理内存。
2.1 allocator 标准空间配置器
allocator是空间配置器，是所有标准库容器所用的默认分配器。其中allocator类中最重要的四个接口为：
- allocate：构造函数
- deallocate：释放先前配置的空间
- construct：调用对象的构造函数
- destroy：调用对象的析构函数
一个最简单的allocator就可以理解为对是对new和delete做了一层薄薄的封装，以及对构造函数和析构函数的直接调用。
SGI STL 实现了两个allocator：一个是标准的std::allocator，另一个是特殊的std::alloc。标准的std::allocator仅在于为用户提供一个兼容老代码的折衷方法，其实现仅仅是对new和delete的简单包装。接下来主要介绍特殊的配置器std::alloc
2.2 特殊空间配置器 std::alloc
这个配置器是SGI STL的默认配置器，它在<memory>中实现：
- <stl_alloc.h>：内存配置和释放在此处实现，其内部有两级配置器，第一级结构简单，封装malloc()和free()，第二级实现了自由链表和内存池，用于提升大量小额内存配置时的性能。
- <stl_construct.h>：定义了全局函数construct()和destroy()，负责对象构造和析构。
- <stl_uninitialiezed.h>：一些用于用于填充和拷贝大块内存的全局函数。
在申请内存空间中，会申请很多小块内存导致内存碎片(fragment)问题，并且一直在因为小块内存而进行内存申请，调用malloc，系统调用产生性能问题。
内碎片：因为内存对齐/访问效率（CPU取址次数）而产生 如 用户需要3字节，实际得到4或者8字节的问题，其中的碎片是浪费掉的。
外碎片：系统中内存总量足够，但是不连续，所以无法分配给用户使用而产生的浪费。
所以 SGI的空间配置器就设计了双层级配置器：
- 一级空间配置器直接封装malloc，free进行处理
- 二级空间配置由内存池以及伙伴系统：自由链表组成
- 当配置区块超过128byte时，视之为足够大，使用第一级配置器，当小于128byte时，视之为过小，采用第二级配置器。
二级空间配置器的实现：
采用内存池的方式实现：
参考
《STL源码剖析》提炼总结：空间配置器(allocator)
STL空间配置器那点事
三、迭代器（iterator）
3.1 迭代器
迭代器是一种行为类似指针的对象，指针的最常见最重要的是内容提领（取出指标所指物体的内容dereference）和成员访问（member access）。
要设计出相应的迭代器需要对容器的实现细节有非常丰富的了解。因此，为了更好地实现封装，可为每一种STL容器提供专属迭代器。
3.2 获取迭代器得相应型别
可以利用function template的参数推导（argument deducation）机制：
template<class I, class T>
void func_impl(I iter, T t)
{
T tmp; //在这里推导出类型，T就是迭代器所指的型别
//func()的内容
}
template<class I>
inline void func()(I iter)
{
//func()只作为对外的接口
func_impl(iter, *iter); //func的工作全部交给了func_impl
}
int mian()
{
int i;
func(&i);
}局限性：无法推导函数的返回值类型
3.3 Traits编程技法
3.3.1 偏特化
首先要先了解什么是偏特化（Partial Specialization）：如果class template拥有一个以上的template参数，我们可以针对其中某个（或数个，非全部）template参数进行特化。即可在泛化设计中提供一个特化版本（将泛化版本中的某些template参数赋予明确的指定）
//泛化版本
template<typename T>
class C { ... }; //允许接受T为任何型别
//偏特化版本
template<typename T>
class C<T*> { ... }; //特化版本仅适用于“T为原生指针”的情况
//“T为原生指针”便是“T为任何型别”的更进一步的条件限制
3.3.1 traits编程技法
构造iterator_traits类来提取迭代器的型别，可通过进行偏特化处理，以使traits提取出正确的value type。
template<class I>
struct iterator_traits {
typedef typename I::value_type value_type;
}
template<class I>
struct iterator_traits<T*> { //偏特化版，迭代器是原生指针
typedef I value_type;
}
template<class I>
struct iterator_traits<const T*> { //偏特化版，迭代器是指向常数的指针“point to const”
typedef I value_type;
}
作用如下图所示：
3.4 迭代器相应型别
3.4.1 value type
迭代器所指对象的型别。
3.4.2 difference_type
- 表示两个迭代器之间的距离，可用于表示容器的最大容量。
- 在针对原生指针的特化版本中，以C++内建的ptrdiff_t（定义于<cstddef>头文件）作为原生指针的difference type。
3.4.3 reference type
代表迭代器所指对象的引用类型。分为const和非const，不允许/允许改变所指内容的对象。
3.4.4 pointer type
代表迭代器所指对象的指针类型。
Item& operator*() const { return *ptr; } //reference type
Item* operator->() const { return ptr; } //pointer type3.4.5 iterator_category：
用来标记迭代器型别，让函数重载机制有效运作起来。
- Input Iterator：这种迭代器所指的对象，不允许外界改变，只读(read only)；
- Output Iterator：只写(write only)；
- Forward Iterator：允许 “写入型算法”，在此种迭代器所形成的区间上操作
- Bidirectional Iterator：可双向移动；
- Random Access Iterator：前四种迭代器都只供应一部分指针算术能力（前三种支持 operator++，第四种再加上operator–），Random Access Iterator则支持所有指针的算术操作，包括 p+n，p-n，p[n]，p1-p2，p1
各种迭代器类型的关系如下图：
四、容器（container）
- 序列式容器：数据的有序存放入list、vector
- 关联式容器：数据的相互关联入map和pair
五、序列式（Sequence）容器
5.1 vector
5.1.1 vector迭代器
vector维护一个线性连续空间，所以不论其元素型别为何，普通指针都可以作为vector的迭代器而满足所有必要条件。所以vector的迭代器是指向元素型别的普通指针，支持随机存取，其类型为Random Access Iterators。
template <class T, class Alloc = alloc>
class vector {
public:
// vector 的嵌套型别定义
typedef T value_type;
typedef value_type* iterator; //vector 的迭代器是普通指针
...
};5.1.2 vector数据结构
vector是一种可自适应增长的动态数组。vector采用的数据结构为线性连续空间。
在STL源码中的一小部分定义：
template <class T,class Alloc=alloc>
class vector
{
//vector维护三个迭代器
protected:
iterator start; //start指向vector的第一个元素
iterator finish; //finish指向vector已经使用的空间的最后一个元素的下一个元素
iterator end_of_storage;//end_of_storage指向vector总共可用空间的最后一个元素的下一个元素
....
pubic:
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());}
reference front {return *begin()}
}
5.1.3 vector接口
5.1.3.1 push_back()
以push_back()将新元素插入vector尾端时，该函数首先检查是否还有备用空间，如果有直接在备用空间上构造元素，并调整迭代器finish，使vector变大，如果没有备用空间，就扩充空间（重新配置、移动数据、释放原空间）。
void push_back(const T& x) {
if(finish != end_of_storage) { //还有备用空间
//在备用空间起始处构造一个元素，并以x赋值
construct(finish, x);
++finish; //调整finish位置
}
else //已无备用空间
insert_aux(end(), x);
}insert_aux()：
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
if(finish != end_of_storage) { //还有备用空间
//在备用空间起始处构造一个元素，并以vector最后一个元素为其初始值
construct(finish,*(finish-1));
//移动finish指针
++finish;
//拷贝内容
T x_copy=x;
//执行拷贝
copy_backward(position,finish-2,finish-1);
*position=x_copy;
}
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);
//为新元素设定初值 value
construct(new_finish, value);
++new_finish;
//将安插点的原内容也拷贝过来
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;
}
}
}所谓动态增加内存大小，并不是在原空间之后接续新空间（因为无法保证原空间之后尚有可配置的空间），而是以原大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对vector的任何操作，一旦容易引起空间重新配置，指向原vector的所有迭代器就都失效了。
5.1.3.2 pop_back()
删除尾端元素
void pop_back() {
--finish; //将尾端标记往前移一格，表示将放弃尾端元素
destory(finish)； //destory是全局函数
}5.1.3.2 erase()
- 清除某个位置上的元素
iterator erase(iterator position) { if(position + 1 != end()) copy(position + 1, finish, position); --finish; destory(finish); return position; } - 清除指定范围内[first, last)的所有元素
iterator erase(iterator first, iterator last) { //将[last, finish)的元素拷贝到first，返回last-1 iterator i = copy(last, finish, first); //copy是全局函数 destory(i, finish); finish = finish - (last - first); return first; }
5.1.3.3 insert()
5.2 list
对于任何位置的元素插入或元素删除，list永远是常数时间。
list无法像vector一样以普通指针作为迭代器，因为其节点不保证在储存空间中连续存在。
对于list而言，插入操作和接合操作都不会造成原有的list迭代器失效
5.2.1 list结点
//双向链表
template <class T>
struct __list_node {
typedef void* void_pointer;
void_pointer prev;
void_pointer next;
T data;
}5.2.2 list迭代器
list不能像vector那样使用普通指针作为迭代器，因为其节点不保证子啊存储空间中连续存在。迭代器在递增时指向下一个节点，递减时指向上一个节点。所以list提供的是Bidirectional Iterators。
list的插入和接合(splice)都不会造成原有的list迭代失效，这在vector中是不成立的。但是它会使得操作指向的迭代器失效。
template <class T, class Ref, class Ptr>
struct __list_iterator {
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, Ref, Ptr> self;
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;
link_type node; //迭代器内部需要一个普通指针，指向list的节点
//constructor
__lint_iterator(link_type x) : node(x) {}
__lint_iterator() {}
__list_iterator(const iterator& x) : node(x.node) {}
bool operator==(const self& x) const { return node == x.node; }
bool operator!=(const self& x) const { return node != x.node; }
//以下是对迭代器取值(dereference)，取的是节点的数据值
reference operator*() const { return (*node).data; }
//以下是迭代器的成员存取(member access)运算子的标准做法
pointer operator->() const { return &(operator*()); }
//对迭代器累加1，就是前进一个节点
self& operator++() { //前置将对象本身作为左值返回
node = (link_type)((*node).next);
return *this;
}
self operator++(int) {
self tmp = *this;
++*this;
return tmp;
}
//对迭代器递减1，就是后退一个节点
self& operator--() {
node = (link_type)((*node).prev);
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
}5.2.3 list数据结构
SGI list不仅是一个双向链表，而且还是一个环状双向链表，所以它只需一个指针，便可以完整表现整个链表：
template <class T, class Alloc = alloc> //缺省使用alloc为配置器
class list {
protected:
typedef __list_node<T> list_node;
public:
typedef list_node* link_type;
protected:
link_type node; //只要一个指针，便可完整表示整个环状双向链表
...
}
5.2.4 list元素操作
5.2.4.1 push_front()和push_back()以及insert()
//插入一个节点，作为头节点
void push_front(const T& x) { insert(begin(), x); }
//插入一个节点，作为尾节点
void push_back(const T& x) { insert(end(), x); }
//函数目的：在迭代器position所指位置插入一个节点，内容为x
iterator insert(iterator position, const T& x) {
link_type tmp = create_node(x); //产生一个节点（设妥内容为x）
//调整双向指针，使tmp插入进去
tmp->next = position.node;
tmp->prev = position.node->prev;
(link_type(position.node->prev))->next = tmp;
position.node->prev = tmp;
return tmp;
}5.2.4.2 erase()
//移除迭代器 position 所指节点，返回 position 的下一个节点
iterator erase(iterator position) {
link_type next_node = link_type(position.node->next);
link_type prev_node = link_type(position.node->prev);
prev_node->next = next_node;
next_node->prev = prev_node;
destory_node(position.node);
return iterator(next_node);
}5.2.4.3 迁移操作transfer()
list内部提供一个所谓的迁移操作（transfer）：将某连续范围的元素迁移到某个特定位置之前。技术上很简单，节点间的指针移动而已。这个操作为其他的复杂操作如splice,sort,merge奠定了基础。
//将[first, last)内的所有元素移动到position之前
void transfer(iterator position, iterator first, iterator last) {
if(position != last) {
(*(link_type((*last.node).prev))).next = position.node; //(1)
(*(link_type((*first.node).prev))).next = last.node; //(2)
(*(link_type(*position.node).prev))).next = first.node; //(3)
link_type tmp = link_type((*position.node).prev); //(4)
(*position.node).prev = (*last.node).prev; //(5)
(*last.node).prev = (*first.node).prev; //(6)
(*first.node).prev = tmp; //(7)
}
}
5.2.4.4 接合操作splice()
//将x接合于position所指位置之前。x必须不同于*this
void splice(iterator position, list& x) {
if(!x.empty()) transfer(position, x.begin(), x.end());
}
//将i所指元素接合于position所指位置之前，position和i可指向同一个list
void splice(iterator position, list&, iterator i) {
iterator j = i;
++j;
if(position == i || position == j) return;
transfer(position, i, j);
}
//将[first, last)内的所有元素接合于position所指位置之前
//position和[first, last)可指向同一个list
//但position不能位于[first, last)之内
void splice(iterator position, list&, iterator first, iterator last ) {
if(first != last) transfer(position, first, last);
}5.3 deque
vector是单向开口的连续线性空间，deque则是一种双向开口的连续线性空间。所谓双向开口，意思是可以再头尾两端分别做元素的插入和删除操作。
5.3.1 deque的中控器
deque由一段一段的定量连续空间组成。deque的最大任务便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。避开了“重新配置，复制，释放”的轮回，代价则是复杂的迭代器架构。
deque采用一块所谓的map(并非STL map容器)作为主控，这里所谓map是一小块连续空间，其中每个元素（此处称为一个节点，node）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是deque的储存空间主体。SGI STL允许我们指定缓冲区大小，默认值0表示将使用512bytes缓冲区.
template<class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
public: //basic types
typedef T value_type;
typedef value_type* pointer;
...
protected: //internal typedefs
//元素的指针的指针(pointer of pointer of T)
typedef pointer* map_pointer;
protected: //data members
map_pointer map; //指向map，map是块连续空间，其内的每个元素都是一个指针（称为节点），指向一块缓冲区
size_type map_size; //map内科可容纳多少指针
...
}
5.3.2 deque的迭代器
deque迭代器应具备的结构：
- 能够指出分段连续空间（缓冲区）在哪里
- 能够判断自己是否已经处于其所在缓冲区的边缘，如果是，一旦前进或后退就必须跳跃至下一个或上一个缓冲区
template<class T, class Ref, class Ptr, size_t BufSize>
struct __deque_iterator { //未继承std::iterator
typedef __deque_iterator<T, T&, T*, BufSize> iterator;
typedef __deque_iterator<T, const T&, const T*, BufSize> const_iterator;
staticsize_tbuffer_size() { return __deque_buf_size(BufSiz, sizeof(T)); }
//未继承std::iterator，所以必须自行撰写五个必要的迭代器相应型别
typedef random_access_iterator_tag iterator_category;
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; //此迭代器所指之缓冲区中的现行元素
T* first; //此迭代器所指之缓冲区的头部元素
T* last; //此迭代器所指之缓冲区的尾（含备用空间）
map_pointer node; //指向管控中心
...
}
5.3.3 deque的数据结构
deque需要维护：
- 一个指向map的指针
- start，finish两个迭代器
- 目前的map大小
template<class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
public: //basic types
typedef T value_type;
typedef value_tpe* pointer;
typedef size_t size_type;
public: //iterators
typedef __deque_iterator<T, T& T*, BufSiz> iterator;
protected:
//元素的指针的指针
typedef pointer* map_pointer;
protected: //Data members
iterator start; //第一个节点
iterator finish;//最后一个节点
map_pointer map; //指向map，map是块连续空间，其每个元素都是个指针，指向一个节点（缓冲区）
size_type map_size; //map内有多少指针
...
}5.3.4 deque的元素操作
5.3.4.1 pop_back()和pop_front()
所谓pop，是将元素拿掉。无论从deque的最前端或最尾端取元素，都需考虑在某种条件下，将缓冲区释放掉。
void pop_back() {
if(finish.cur != finish.first) {
//最后缓冲区有一个（或更多）元素
--finish.cur; //调整指针，相当于排除了最后元素
destory(finish.cur); //将最后元素析构
}
else
//最后缓冲区没有任何元素
pop_back_aux(); //此处将进行缓冲区的释放工作
}
//只有当finish.cur == finish.first时才会被调用
template<class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::pop_back_aux() {
deallocate_node(finish.first); //释放最后一个缓冲区
finish.set_node(finish.node - 1); //调整finish的状态，使指向上一个缓冲区的最后一个元素
finish.cur = finish.last - 1;
destory(finish.cur); //将该元素析构
}5.3.4.2 insert()
以下insert()函数允许在某个点（之前）插入一个元素，并设定其值：
//在position处插入一个元素，其值为x
iterator insert(iterator position, const value_type& x) {
if(position.cur == start.cur) { //如果插入点是deque最前端
push_front(x); //交给push_front()
return start;
}
else if(position.cur == finish.cur) { //如果插入点是deque最尾端
push_back(x); //交给push_back()
iterator tmp = finish;
--tmp;
return tmp;
}
else {
return insert_aux(position, x);
}
}
//辅助插入函数insert_aux()：
iterator insert_aux(iterator pos, const value_type& x) {
difference_type index = pos - start; //插入点之前的元素个数
value_type x_opy = x;
if(index < (size() >> 1)) { //如果插入点之前的元素较少
push_front(front()); //在最前端加入与第一元素同值的元素
iterator front1 = start;//以下标示记号，然后进行元素操作
++front1;
iterator front2 = front1;
++front2;
pos = start + index;
iterator pos1 = pos;
++pos1;
copy(front2, pos1, front1); //元素移动
}
else { //插入点之后的元素较少
push_back(back()); //在最尾端加入与最后元素同值的元素
iterator back1 = finish;//以下标示记号，然后进行元素操作
--back1;
iterator back2 = back1;
--back2;
pos = start + index;
copy_backward(pos, back2, back1); //元素移动
}
*pos = x_copy; //在插入点上设定新值
return pos;
}
5.4 stack
stack是一种先进后出（First In Last Out, FILO)的数据结构。它只有一个出口。stack允许新增元素、移除元素、取得最顶端元素。但除了最顶端外，没有任何其他办法可以存取stack的其他元素。换言之，stack不允许遍历行为。因此stack没有迭代器
由于stack系以底部容器完成其所有工作，而具有这种“修改某物接口，形成另一种风貌”之性质者，称为adapter（配接器），因此，STL stack往往不被归类为container（容器），而被归类为container adapter。
SGI STL便是以deque作为缺省情况下的stack底部结构实现stack。
template<class T, class Sequence = deque<T>>
class stack {
//__STL_NULL_TMPL_ARGS会开展为<>
friend bool operator==__STL_NULL_TMPL_ARGS (const stack&, const stack&);
friend bool 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 typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c; //底层容器
public:
//通过Sequence c的操作完成stack的操作
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(); }
//deque是双向开口的线性连续空间，可两头进出，stack是末端进，末端出（所以后进者先出）
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_back(); }
};
template<class T, class Sequence>
bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
return x.c == y.c;
}
template<class T, class Sequence>
bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
return x.c < y.c;
}5.5 queue
queue是一种先进先出(First In First Out, FIFO)的数据结构。它有两个出口。queue允许新增元素、移除元素、从最底端加入元素、取得最顶端元素。但除了最底端可以加入、最顶端可以取出外，没有任何其他办法可以存取queue的其他元素。queue不允许有遍历行为，因此queue没有迭代器
SGI STL便是以deque作为底部结构并封闭其底部出口和前端入口，实现queue。
template<class T, class Sequence = deque<T>>
class queue {
//__STL_NULL_TMPL_ARGS会开展为<>
friend bool operator==__STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
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; //底层容器
public:
//通过Sequence c的操作完成queue的操作
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(); }
//deque是双向开口的线性连续空间，可两头进出，queue是末端进，前端出（所以先进者先出）
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_front(); }
};
template<class T, class Sequence>
bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
return x.c == y.c;
}
template<class T, class Sequence>
bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
return x.c < y.c;
}5.6 heap
heap并不是归属于STL容器组件，它是个幕后英雄，扮演priority queue的助手。可以使用arry的i表示某一个节点，那么左子节点就必须位于array的2i处，右子节点必须位于array的2i+1处。 根据元素排列方式，heap可以分为：
- max-heap: 每个节点键值都大于或者等于其子节点的键值
- min-heap: 每个节点键值都小于或者等于其子节点的键值
详细会在堆算法中阐述
5.7 priority_queue
priority_queue是一个具有权值观念的queue，它允许加入新元素、移除旧元素、审视元素值等功能。其内部的函数是按照权值进行排序的。priority queue允许用户以任何次序将任何元素推入容器内，但取出时一定是从优先权最高（也就是数值最高）的元素开始取。
缺省情况下priority_queue系利用一个max-heap完成，后者是一个vector表现的complete binary tree。max-heap可以满足priority_queue所需要的“依权值高低自动递增排序”的特性。
priority_queue以vector为底部容器，再加上heap的处理规则。具有这种“修改某物接口，形成另一种风貌”之性质者，称为adapter
template<class T, class Sequence = vector<T>, class Compare = less<typename Sequence::value_type>>
class priority_queue {
//...
protected:
Sequence c; //底层容器
Compare comp; //元素大小比较标准
public:
priority_queue() : c() {}
explicit priority_queue(const Compare& x) : c(), comp(x) {}
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Compare& x)
: c(first, last), comp(x) {make_heap(c.begin(), c.end(), comp);}
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
: c(first, last) {make_heap(c.begin(), c.end(), comp);}
bool empty() const {return c.empty();}
//...
void push(const value_type& x) {
__STL_TRY {
//push_heap是泛型算法，先利用底层容器的push_back()将新元素推入末端，再重排heap。
c.push_back(x);
push_heap(c.begin(), c.end(), comp);
}
__STL_UNWIND(c.clear());
}
void pop() {
__STL_TRY {
//pop_heap是泛型算法，它并不是真正将元素弹出，而是重排heap，然后再以底层容器的pop_back()取得被弹出的元素
pop_heap(c.begin(), c.end(), comp);
c.pop_back();
}
__STL_UNWIND(c.clear());
}
};
五、关联式（associative）容器
当元素被插入到关联式容器中时，容器内部结构(可能是RB-tree或者hash-table)便依照其键值大小，以某种特定规则将这个元素放置于合适的位置，关联式容器没有所谓头尾(只有最大元素和最小元素)；所以不会有所谓push_back()、push_front()等行为的操作。 一般而言关联式容器的内部结构是一个二叉平衡树，以便获得良好的搜寻效率。二叉平衡树有许多变形包括：AVL-tree、RB-tree、AA-tree；其中RB-tree被广泛应用于关联式容器。
5.1 树
5.1.1二叉树
5.1.2 二叉搜索树
任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值
二叉搜索树可提供对数时间的元素插入和访问。
结点插入：
结点删除：
5.1.3 AVL树
是一种结构平衡的二叉搜索树，即叶节点高度差的绝对值不超过1。
AVL树平衡破坏有4中情况：
- 插入点位于X的左子节点的左子树-左左
- 插入点位于X的左子节点的右子树-左右
- 插入点位于X的右子节点的左子树-右左
- 插入点位于X的右子节点的右子树-右右
1和4彼此对称，称为外侧插入，可以采用单旋转操作调整情况。
2和3彼此对称，称为内侧插入，可以采油双旋转操作调整情况。
单旋转
双旋转
5.1.4 红黑树
首先红黑树是一个AVL树，其次还需满足以下条件：
- 每个节点不是红色就是黑色
- 根节点为黑色
- 每个叶节点是黑色
- 父子两节点不得同时为红
- 任意节点到叶节点（树尾端）的任何路径，所含黑节点数目必须相同
5.1.4.1 插入结点
插入新节点破坏RB-tree的规则，必须调整树形，即旋转树形并改变节点颜色：
- S为黑色X为外侧插入，对此情况，先对P,G做一次单旋转，再更改P,G颜色，即可重新满足红黑树的规则3。
- S为黑且x为内侧插入，对此情况，我们必须先对P,X做一次单旋转并更改G,X颜色，再将结果对G做一次单旋转，级可再次满足红黑树规则3.
- S为红色且X为外侧插入，对此情况，先对P和G做一次单旋转，并改变X的颜色。此时如果GG为黑，一切搞定，如果GG为红，则是状况4
- S为红且X为外侧插入。对此情况，先对P和G做一次单旋转，并改变X的颜色。此时如果GG亦为红，还得持续往上做，直到不再有父子连续为红的情况发生。
自上而下的程序
5.1.4.2 RB-Tree的结点设计
//节点双层结构
typedef bool __rb_tree_color_type;
const _rb_tree_color_type __rb_tree_red = false; //红色为0
const _rb_tree_color_type __rb_tree_black = true; //黑色为1
struct __rb_tree_node_base {
typedef __rb_tree_color_type color_type；
typedef __rb_tree_node_base* base_ptr;
color_type color; //节点颜色，非红即黑
base_ptr parent; //各种操作常需要上溯其父节点
base_ptr left; //指向左节点
base_ptr right; //指向右节点
static base_ptr minimum(base_ptr x) {
while(x->left != 0) x = x->left; //一直向左走，就能找到最小值
return x;
}
static base_ptr maximum(base_ptr x) {
while(x->right != 0) x = x->right; //一直向右走，就能找到最大值
return x;
}
};
template<class Value>
struct __rb_tree_node : public __rb_tree_node_base {
typedef __rb_tree_node<Value>* link_type;
Value value_field; //节点值
};5.1.4.3 RB-Tree的迭代器
RB-tree的迭代器属于双向迭代器，但不具备随机定位能力。RB-tree迭代器的前进操作operator++()调用了基层迭代器的increment()，RB-tree迭代器的后退操作operator–()则调用了基层迭代器的decrement()。
//基层迭代器
struct __rb_tree_base_iterator {
typedef __rb_tree_node_base::base_ptr base_ptr;
typedef bidirectional_iterator_tag iterator_category;
typedef ptrdiff_t difference_type;
base_ptr node;
void increment() {
if(node->right != 0) { //如果有右子节点
node = node->right;
while(node->left != 0) node = node->left;
}
else { //没有右子节点
base_ptr y = node->parent;
while(node == y->right) { //判断当前节点是否为右子节点
node = y; //若是，则一直上溯，直到不为右子节点
y = y->parent;
}
if(node->right != y) node = y; //右子节点不等于此时的父节点
}
}
void decrement() {
if(node->color == __rb_tree_red && node->parent->parent == node) //如果是红节点且父节点的父节点等于自己
node = node->right;
else if(node->left != 0) { //如果有左子节点
base_ptr y = node->left;
while(y->right != 0) y = y->right;
node = y;
}
else { //既非根节点也无左子节点
base_ptr y = node->parent;
while(node == y->left) { //当前节点为左子节点
node = y;
y = y->parent; //上溯至不为左子节点
}
node = y;
}
}
};
//正规迭代器
template <class Value, class Ref, class Ptr>
struct __rb_tree_iterator : public _rb_tree_base_iterator {
//...
self& operator++() { increment(); return *this; }
self operator++(int) {
self tmp = *this;
increment();
return tmp;
}
self& operator--() { decrement(); return *this; }
self operator--(int) {
self tmp = *this;
decrement();
return tmp;
}
};5.1.4.3 RB-Tree的数据结构
template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree {
protected:
typedef void* void_pointer;
typedef __rb_tree_node_base* base_ptr;
typedef __rb_tree_node<Value> rb_tree_node;
typedef simple_alloc<__rb_tree_node, Alloc> rb_tree_node_allocator;
typedef __rb_tree_color_type color_type;
public:
typedef Key key_type;
typedef Value value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef rb_tree_node* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
//维护RB-tree的三笔数据：
protected:
size_type node_count; //记录树的大小（节点数量）
link_type header; //实现上的一个技巧
Compare key_compare; //节点间的键值大小比较准则
//节点配置和销毁：
protected:
link_type get_node() { return rb_tree_node_allocator::allocate(); }
void put_node(link_type p) { rb_tree_node_allocator::deallocate(p); }
link_type create_node(const value_type& x) {
link_type tmp = get_node(); //配置空间
__STL_TRY {
construct(&tmp->value_field, x); //构造内容
}
__STL_UNWIND(put_noed(tmp));
return tmp;
}
void destory_node(link_type p) {
destory(&p->value_field); //析构内容
put_node(p); //释放内存
}
//构造与析构
private:
void init() {
header = get_node(); //产生一个节点空间，令header指向它
color(header) = _rb_tree_red;
root() = 0;
leftmost() = header; //令header的左子节点为自己
rightmost() = header; //令header的右子节点为自己
}
public：
rb_tree(const Compare& comp = Compare()) : node_conut(0), key_compare(comp) {
init();
}
~rb_tree() {
clear();
put_node(header);
}
};RB-tree的构造方式有两种，一种是拷贝构造，一种是空值构造。其中init()的原理如图所示：
5.1.4.3 RB-Tree的关键操作
元素插入 insert_equal()
template <class Key,class Value,class KeyOfValue,class Compare,class Alloc>
typename rb_tree<Key,Value,KeyOfValue,Compare,Alloc>::iterator
rb_tree<Key,Value,KeyOfValue,Compare,Alloc>::insert_equal(const Value& v)
{
link_type y=header;
link_type x=root();
//从根节点开始向下寻找适当的传播节点，直到到根节点，注意这里y为x的parent节点
while(x!=0) {
y=x;
//遇大则左，遇小或者等于就右--v<x向左，v>=x向右
x=key_compare(KeyOfValue()(v),key(x))?left(x):right(x);
}
//x为新值插入点，y为插入点之父节点，v为新值
return __insert(x,y,v);
}元素插入操作insert_unique()
template <Class Key,class Value,class KeyOfValue,class Compare, class Alloc>
pair<typename rb_tree<Key,Value,KeyOfValue,Compare,Alloc>::iterator,bool>
rb_tree<Key,Value,KeyOfValue,Compare,Alloc>::insert_unique(const Value& v)
{
link_type y=header;
//从根节点开始
link_type x=root();
//判断是否相同
bool comp=true;
//一直遍历到根节点
while(x!=0)
{
y=x;
//v是否小于目前节点的键值
comp=key_compare(KeyOfValue()(v),key(x));
//遇“大”向左，否则向右
x=comp?left(x):right(x);
}
//离开while循环之后，即插入父节点
//令迭代器j指向插入点的父节点
iterator j=iterator(y);
//如果在左边插入
if(comp)
{
//如果插入节点为最左节点
if(j==begin())
{
return pair<iterator,bool>(__insert(x,y,v),true);
}else{
//调整j准备回头进行测试
--j;
}
}
//如果小于新值，将插入右侧
//比较是否存在重复的值
if(key_compare(key(j.node),KeyOfValue()(v))){
return pair<iterator,bool>(__insert(x,y,v),true);
}
return pair<iterator,bool>(j,false);
}
//关键插入程序
template <class Key,class Value,class KeyOfValue,class Compare,class Alloc>
typename rb_tree<Key,Value,KeyOfValue,Compare,Alloc>::iterator
rb_tree<Key,Value,KeyOfValue,Compare,Alloc>::__insert(base_ptr x_,base_ptr y_,const Value& v)
{
//将值隐式转换为节点指针，x插入位置，y插入父节点，v插入的值
link_type x=(link_type)x_;
link_type y=(link_type)y_;
link_type z;
//判断是否为首节点
if(y==header||x!=0||key_compare(KeyOfValue()(v),key(y)))
{
//产生一个新节点
z=create_node(v);
//重新调整最由节点
left(y)=z;
if(y==header){
root()=z;
rightmost()=z;
//如果y为最左节点
}else if(y==leftmost()){
//让最左节点永远指向z
leftmost()=z;
}
//不是head节点或者空节点
}else{
//产生一个新节点
z=create_node(v);
//令新节点作为插入节点的右兄弟节点
right(y)=z;
//更新最右指针位置
if(y==rightmost()){
rightmost()=z;
}
}
//设置新节点的父节点,右子节点和左子节点
parent(z)=y;
left(z)=0;
right(z)=0;
//调整和设置新节点的颜色
__rb_tree_rebalance(z,header->parent);
++node_count;
//返回插入的迭代器
return iterator(z);
}
//调整rb-tree(旋转和改变颜色)，节点和节点的父节点
inline void __rb_tree_rebalance(__rb_tree_node_base* x,__rb_tree_node_base*& root)
{
//新节点毕为红
x->color=__rb_tree_red;
//假设父节点为红色,按照之前的4种情况进行判断然后调整
while(x!=root&&x->parent->color==__rb_tree_red){
//判断父节点是否为左子节点
if(x->parent==x->parent->parent->left){
//y指向右伯节点
__rb_tree_node_base* y=x->parent->parent->right;
//如果y存在并且也为红色
if(y&&y->color==__rb_tree_red)
{
//更改父节点为黑色
x->parent->color=__rb_tree_black;
//更改父节点为黑色
y->color=__rb_tree_black;
//更改祖父节点为红
x->parent->parent->color=__rb_tree_red;
//x重新指向祖节点,再次循环迭代更改
x=x->parent->parent;
//无伯父节点，或者伯父节点为黑
}else{
//如果新节点为右子节点
if(x==x->parent->right){
//x重新指向父节点
x=x->parent;
//第一参数为左旋点进行左旋
__rb_tree_rotate_left(x,root);
}
//改变颜色
x->parent->color=__rb_tree_black;
x->parent->parent->color=__rb_tree_red;
//第一参数为右旋点
__rb_tree_rotate_right(x->parent->parent,root);
}
//父节点为祖父节点之右子节点
}else{
//y为左伯父节点
__rb_tree_node_base* y=x->parent->parent->left;
//左伯父节点存在且为红色
if(y&&y->color==__rb_tree_red)
{
//更改父节点为黑
x->parent->color=__rb_tree_black;
//伯父节点为黑色
y->color=__rb_tree_black;
//更改祖父节点为红色
x->parent->parent->color=__rb_tree_red;
//移动指针准备继续向上查
x=x->parent->parent;
//无伯父节点或伯父节点为黑
}else{
//如果新节点为父节点之左子节点
if(x==x->parent->left){
x=x->parent;
//第一参数为右旋点
__rb_tree_rotate_right(x,root);
}
x->parent->color=__rb_tree_black;
x->parent->parent->color=__rb_tree_red;
//第一参数为左旋点
__rb_tree_rotate_left(x->parent->parent,root);
}
}
}//end while
//root节点永远为黑
root->color=__rb_tree_black;
}
//左旋函数，主要是将x和它的右子节点进行交换
inline void __rb_tree_rotate_left(__rb_tree_bode_base* x,__rb_tree_bode_base*& root)
{
//x为旋转点，y为旋转点的右子节点
__rb_tree_node_base* y=x->right;
//将x的右子节点为其右子节点的左节点
x->right=y->left;
//存在且不为0，则交换指针位置，指直接将x的右子节点与x交换位置
if(y->left!=0){
//更新x指针位置
y->left->parent=x;
}
y->parent=x->parent;
//这里分空节点和单左/右节点进行讨论
if(x==root){
root=y;
}else if(x==x->parent->left){
x->parent->left=y;
}else{
x->parent->right=y;
}
y->left=x;
x->parent=y;
}
inline void __rb_tree_rotate_right(__rb_tree_node_base* x,__rb_tree_node_base*& root)
{
//x为旋转点,y为旋转的左子节点
__rb_tree_node_base* y=x->left;
x->left=y->right;
if(y->right!=0){
y->right->parent=x;
}
y->parent=x->parent;
//令y完全顶替x的地位(必须将x对其父节点的关系完全接收过来)
if(x==root){
root=y;
}else if(x==x->parent->right){
x->parent->right=y;
}else{
x->parent->left=y;
}
y->right=x;
x->parent=y;
}
//rb-tree的查找函数
template <class Key,class Value,class KeyOfValue,class Compare,class Alloc>
typename rb_tree<Key,Value,KeyOfValue,Compare,Alloc>::iterator
rb_tree<Key,Value,KeyOfValue,Compare,Alloc>::find(const Key& k){
//rb树的头部
link_type y=header;
link_type x=root();
while(x!=0){
if(!key_compare(key(x),k)){
//x大于k向左走
y=x;
x=left(x);
}else{
//x小于k,遇到小值就向右走
x=right(x);
}
}
iterator j=iterator(y);
return (j==end()|| key_compare(k,key(j.node)))?end():j;
}
5.2 set和map
set的特点：
- 所有元素会根据元素的键值自动被排序
- set元素的键值就是实值，实值就是键值，不允许元素重复
- 无法通过set的迭代器修改set的元素值（键值关系到元素的排列规则）
- set<T>::iterator被定义为底层RB-tree的const_iterator，杜绝写入操作
- STL特别提供了一组set/multiset相关算法，包括交集、联集、差集、对称差集
- set以RB-tree为底层机制，几乎所有的set操作行为皆是转调用RB-tree的操作行为
map的特点：
- 所有元素会根据元素的键值自动被排序。
- map的所有元素都是pair，同时拥有实值（value）和键值（key）。pair的第一元素被视为键值，第二元素被视为实值。
下面为pair的定义
//pair定义
template<class T1, class T2>
struct pair {
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair() : first(T1()), second(T2()) {}
pair(const T1& a, const T2& b) : first(a), second(b) {}
}set和map都不允许两个元素拥有相同的键值，因此它的插入操作采用的是底层RB-tree的insert_unique() 。
5.4 multiset&multimap
mutliset/multimap的特性及用法与set/map完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层RB-tree的insert_equal() 。
5.5 hashtable
5.5.1 hashtale的概述
碰撞问题解决办法：
- 线性探测：使用hash function计算出插入位置后，发现位置不可用，则循序往下一一寻找
- 二次探测：如果位置不可用，尝试H+1^2, H+2^2, H+3^2
- 开链：在每个表格元素中维护一个list;hash function 为我们分配某一个list,然后我们在那个list上执行元素的相关操作。SGI STL的hash table就是这种做法
5.5.2 hashtale的桶子(buckets)与节点(nodes)
5.5.3 hashtable的迭代器
hashtable 的迭代器没有后退操作，也没有所谓的反向迭代器。hash tble 没有供应default constructor
5.5.4 hashtable的数据结构
node* new_node(const value_type& obj)
{
node* n=node_allocator::allocate();
n->next=0;
__STL_TRY{
construct(&n->val,obj);
return n;
}
__STL_UNWIND(node_allocator::deallocate(n));
}
void delete_node(node* n)
{
destroy(&n->val);
node_allocator::deallocate(n);
}
hashtable(size_type n,
const HashFcn& hf,
const EqualKey& eql)
:hash(hf),equals(eql),get_key(ExtractKey()),num_elements(0)
{
initialize_buckets(n);
}
void initialize_buckets(size_type n)
{
const size_type n_buckets=next_size(n);
buckets.reserve(n_buckets);
buckets.insert(buckets.end(),n_buckets,(node*)0);
num_elements=0;
}
//返回接近n并大于n的质数
size_type next_size(size_type n) const {return __stl_next_prime(n);}
pair<iterator,bool> insert_unique(const value_type& obj)
{
//表格重建与否的判断函数：将新增元素计入后的元素个数和buckets vector的大小来比。如果前者大于后者，就重建表格。由此可判断，每个bucket（list）的最大容量和buckets vector的大小相同
//是否需要重建表格
resize(num_elements+1);
return insert_unique_noresize(obj);
}
template <class V,class K,class HF,class Ex,class Eq,class A>
void hashtable<V,K,HF,Ex,Eq,A>::resize(size_type num_elements_hint)
{
//将元素个数(新增元素计入后)与bucket vector的大小比较。如果大于就重建表格
//这里的buckets是 vector<node*,Alloc> buckets
const size_type old_n=buckets.size();
//是否重新配置元素
if(num_elements_hint>old_n)
{
//找出下一个质数
const size_type n=next_size(num_elements_hint);
//确定下一个质数是否越界
if(n>old_n){
//设立新的桶
vector<node*,A> tmp(n,(node*)0);
__STL_TRY{
//处理每一个旧的bucket
for(size_type buckets=0;buckets<old_n;++buckets)
{
//指向节点所对应串行的起始节点
node* first=buckets[buckets];
//以下处理每个就bucket所含(串行)的每个节点
//遍历串行
while(first){
//找出节点落在那个新bucket内
size_type new_bucket=bkt_num(first->val,n);
//令旧bucket指向其所对应串行的下一个节点(以便迭代处理)
buckets[bucket]=first->next;
//将当前节点插入到新bucket内，成为对应串行的第一个节点
first->next=tmp[new_bucket];
//回到旧bucket所指的待处理串行，准备处理下一个节点
first=buckets[bucket];
}
}
//对调两个新旧桶
buckets.swap(tmp);
//注意，对调两方，如果大小不同，大的会变小，小的会变大
//离开时释放local tmp的内存
}
}
}
}
//插入节点的关键函数
template <class V,class K,class HF,class Ex,class Eq,class A>
void hashtable<V,K,HF,Ex,Eq,A>::insert_unique_noresize(const value_type& obj)
{
//决定obj的桶位置
const size_type n=bkt_num(obj);
//first指向bucket对应之串行头部
node* first=buckets[n];
//如果位置已经被占用，即first!=0;循环遍历查找新位置
for(node* cur=first;cur;cur=cur->next)
{
if(equals(get_key(cur->val),get_key(obj))){
return pair<iterator,bool>(iterator(cur,this),false);
}
}
//离开以上循环，first指向bucket所值链表的头部节点
//产生新节点
node* tmp=new_node(obj);
tmp->next=first;
//令节点成为链表的第一个节点
buckets[n]=tmp;
//节点个数累加1
++num_elements;
return pair<iterator,bool>(iterator(tmp,this),true);
}
5.6 unordered_set
- hash_set以hashtable为底层机制。
- 使用set的目的：快速搜寻元素。而由于RB-tree有自动排序而hashtable没有，因此set的元素能够自动排序而hsh_set没有。
- hash_set的键值就是实值，实值就是键值。
- 插入操作使用insert_unique()，不允许键值重复
5.7 unordered_map
- hash_map也以hashtable为底层机制，因此没有自动排序
- hash_map的每一个元素同时拥有一个实值和键值（使用方式与map相同）
- 插入操作使用insert_unique()，不允许键值重复
5.8 unordered_multiset&unordered_multimap
- hash_multiset/hash_multimap也以hashtable为底层机制，因hash_multiset/hash_multimap的元素不会被自动排序。
- 与hash_set/hash_map的唯一区别：元素插入采用insert_equal()
六、算法
STL中算法汇总：
七、仿函数
仿函数也叫对象函数；在STL提供的各种算法中，都允许用户自定义相关算法。以结果的false或者true来进行相关的排序操作，用来执行函数的就是仿函数。一般步骤是先设计一个函数，在将函数的相关指针指向函数对应的结果。
八、配接器
Adapter实际上是一种设计模式，将一个class的借口转换为另外一个class的接口。
参考
《STL源码剖析这本书》 侯捷
