STL源码

allocator（空间配置器）

定义：是操作系统开辟的一大段内存空间。STL需要扩容申请内存时，就从空间配置器中申请，不需要再经过操作系统。并且，它还能回收释放的空间，供下一次使用。
方法：
1.内存的配置：alloc::allocate();
2.对象的构造：::construct();
3.对象的析构：::destroy();
4.内存的释放：alloc::deallocate();
优点：
1.STL申请空间不需要操作系统申请，而是需要向空间适配器申请，只有当空间适配器空间不够时，才会向操作系统申请
2.避免内存碎片
实现：
内存池 + 哈希桶（一个存放16个free list的数组）
allocate()实现原理：

• 一级空间配置器：当申请的内存大于 128 bytes时调用
  直接对malloc和free进行了封装，并且增加了C++中的set_new_handle思想，即申请空间失败抛异常机制
• 二级空间配置器：管理容器申请空间和释放的空间，专门负责处理小于128字节的小块内存（小额区块）
  小额区块的缺点：在通过malloc申请空间时，需要标注申请空间的大小，也需要向系统申请越界位置，申请的空间需要cookie来记录空间大小，上越界和下越界标记，如果小额区块越多，cookie占用空间越多，也越浪费

哈希桶结构

流程：
容器进行扩容，如果申请的空间是大于128字节，直接向一级空间配置器申请。如果小于128字节，先查找哈希桶对应大小位置是否为空，不为空，直接从该位置申请空间，如果该位置为空，向内存池申请。当内存池空间不够了会直接向OS申请一大块空间。

注意点：

1. 用户向内存池申请一块大小为n的空间时，为了效率，内存池会切割出多块(一般为20块)大小为n的空间，给用户一个，其它剩余的会连接到哈希桶对应下标处。避免下一次申请。
2. 可能用户申请的空间会不是8的整数倍，内存池切割的内存块大小会向上对齐到8的整数倍。比如：申请5字节空间，内存池会切割8字节的空间。
3. 一个进程中有一个空间配置器，进程中所有容器需要的空间都到对应空间配置器申请。进程终止，对应空间配置器空间释放。