STL

Alloc

c++内存空间管理模块，包含于:

<memory>:

<stl_construct.h>: 定义全局函数construct(),destory()，负责对象析构与构造
<stl_alloc.h>: 定义一二级配置器，名为alloc
<stl_uninitialized.h>: 一些全局函数用来操作大块内存数据

construct&destory

construct类似C++的placement new。

destory存在两版本：

版本一接收一指针参数，析构掉指针处的对象
版本二接收两指针参数，析构掉两指针之间的所有对象

alloc

alloc空间配置器分一级配置器和二级配置器：

一级配置器就是直接封装malloc和free
二级配置器：
1. 维护16个自由链表组成内存池，分别负责十六种小型区块配置，填充内存池调用malloc
2. 出现内存不足，或要求区块大于128Bytes转一级配置器

二级配置器：

对于所需求区块无空闲块的情况直接去更大区块处查找，找到后出现的碎片会挂到与它大小匹配的区块链表上
都没有就分配40块需求区块，20块挂在链表上，20块作为后备

free

free是如何知道对象的大小呢，这是因为malloc在分配内存时，会在对象的内存块的上下区域添加内存大小的cookie，VC6中malloc添加的是对象大小+1.不管怎么样，这都足够free去get到需要归还给操作系统的内存空间大小了，当然所谓归还也只是还给CRTL的内存池，只有空闲内存到达某种条件（例如整整几页的空间都空闲，他们可能还连续），那就使用系统调用来让内核释放掉这一块虚拟内存（其实也就是进task_struct里找到mm_sturct然后操作里面的bitmap，将要释放的内存对应的块设置为再次可用）。

Iterator

迭代器的根本还是一个指针，当然它是一种智能指针
通过指针萃取到指针所指对象的类型或一些其他信息很重要，这就是traits技法

分类上个侯捷老师的图：

traits

利用template自动推导和偏特化实现普遍可用的萃取特性方法，直接记录代码：

template <class T>
struct MyIter {
    typedef T value_type; // 内嵌型别声明
    T* ptr;
    MyIter(T* p = 0) : ptr(p) {}
    T& operator*() const { return *ptr; }
};
// class type泛化版本
template <class T>
struct iterator_traits {
    typedef typename T::value_type value_type;
};
// 原生指针偏特化版本
template <class T>
struct iterator_traits<T*> {
    typedef T value_type;
};
// const对象指针偏特化版本
template <class T>
struct iterator_traits<const T*> {
    typedef T value_type;
};

template <class I>
typename iterator_traits<I>::value_type //typename 告诉编译器这是一个type
func(I ite) {
    std::cout << "normal version" << std::endl;
    return *ite;
}

当然value_type只是常用的一种，STL还有其他几种，就不写了。

DataStruct

List

链表，而且是双向链表，需要注意的是该双向链表的实现使用了一个无名节点，使得这个双向链表形成了环。这也就是end指向的结尾得“未知值”。侯捷老师的图拿来参考一下：

Vector

贴个侯捷老师的图：

Array

贴个侯捷老师的图：

Forward List

Deque

侯捷老师的图实在是太经典了，一看就懂

具体实现的图中的map是一个原生数组，每一个元素中存有一个指向buffer得指针

buffersize现在是没法调整的，有一套较为复杂的计算方式，需要的话可以查一下

从他的实现可以看到，这个设计可以模拟数组的随机访问，思路很简单就不说了

还有一点需要注意是这个容器可以进行insert操作,在指定位置插入值时需要根据当前元素处于前半段还是后半段选择推前面还是推后面，推移操作直接循环搬就行。

Queue

封装了deque的部分函数实现的，没啥好说的

Stack

封装了deque的部分函数实现的，没啥好说的

RB-tree

stl实现了红黑树，需要注意的是其类定义：

_Rb_tree<int, int, _Identity<int>, less<int>> itree;

其中前两个是K和V，

_Identity是一个从V中得到K的函数，为什么需要这个呢，举例：

key: int Value:pair<int, vector<int», 看出来了吧，这个Value其实是data和key的结合体，所以需要告诉怎么从结合体中取出这个data，逻辑意义上的key和value就对应这里的key和data了。

less是一个重载了operator()的比较函数。

有两种插入： insert_equal和insert_unique，看字面意思就知道是啥

一般来讲rbtree的这个Value是不能修改的，但编译器不阻止

Set&multi_set

Set就是value为Key的rbtree

其Value不能修改

Map&Multi_map

map的key不能改，但是data可以改

Hashtable

使用vector作为buckets，使用一个hash算法来将对象映射到不同bucket上。

使用开链法解决冲突，负载因子大于1就触发扩容，直接扩为原来二倍左右。

Unordered_map&Unorderd_set

底层为hashtable,封装个别方法实现