STL源码剖析Note

侯捷老师的《STL源码剖析》阅读笔记（个人理解向）

第2章 空间配置器（allocator）

• SGI STL实现了一种具有次层配置（sub-allocation）能力的特殊空间配置器

SGI标准的空间配置器：std::allocator

效率低下，仅仅是把::operator new, ::operator delete做了一层封装而已

SGI特殊的空间配置器：std::alloc

• new的过程：先调用::operator new分配内存，再调用::construct()构造对象

• delete的过程：先调用::destroy()调用对象的析构函数，再调用::operator delete释放内存

在实现上，对象的构造析构 与 内存的分配释放分开实现，alloc::allocate()和alloc::deallocate()负责内存分配和释放，::construct()和::destroy()负责构造析构。

构造和析构

::construct()：使用<new.h>中的placement new运算子在特定指针所指空间上构造对象（注意与new区分）

::destroy()：直接调用析构函数（另外需要考虑是否具有trivial destructor，如果有就什么也不做，否则遍历整个范围一个个释放）

内存分配与释放

特点：双层级配置器，第一层直接使用malloc(), free()，第二层（STL默认使用的）采用内存池（memory pool）和第一层结合的方式。简单来说，第二层是为了减小多次分配和释放内存的开销（因为malloc会附带一些额外的占空间的cookie和内存）而设计的。具体地，在第二层维护一个长度为16（default）的数组，数组元素是一个链表，因此叫他自由链表（free lists，类似块状链表，不过是反过来的），负责16种内存大小的次配置能力（每个元素负责8的倍数个byte的内存大小的区块）。如下所示，因此最多是128bytes，超过这个值得内存分配就会直接调用第一层的配置器。

|       |        |     |           |
| [0,8) | [8,16) | ... | [120,128) |
|       |        |     |           |

在这个数据结构的实现上，采用了union结构以节省内存开销，也就是说，这个数组中的每个元素既能指向另一个相同类型元素，又能指向实际区块。

union obj{
    union obj *free_list_link;
    char client_data[1];
}

allocate()和deallocate()函数的实现就如上方所讲，首先找到符合的内存对应的自由链表位置，然后分配和释放内存。

refill()函数的作用：重新填充free list的空间（默认值20个新区块），新空间取自内存池（由chunk_alloc()完成）

chunk_alloc()函数作用：从内存池取空间给free lists，具体实现如下：

• 如果内存池剩余空间完全满足需求量：取空间分配给free lists

• 如果内存池剩余空间不能完全满足需求量（但满足>=1个）：取上限量分配给free lists

• 如果内存池空：如果内存池还有零头可用，则先编入，再调用malloc()从heap空间申请（两倍+附加量）的内存

内存基本处理工具

construct();
destroy();
uninitialized_copy();
uninitialized_fill();
uninitialized_fill_n();

第3章 迭代器（iterators）与traits编程技法

迭代器所指对象型别的实现——traits与偏特化

采用一个迭代器traits来“萃取”迭代器特性：

如果类I定义了自己的value type（类似的，还有difference type, pointer, reference, iterator category），那么就可以直接获取。如果I是原生指针或常量指针，则可以通过类模板偏特化自己实现：

类似地，以下迭代器型别都需要针对原生指针定义偏特化版本：

value_type：迭代器所指对象的型别

difference_type：表示两个迭代器之间的距离

reference_type：(*迭代器)的型别

piointer_type：一个地址，指向迭代器所指的量

iterator_category：迭代器的类别（5种）

对于iterator_category，在偏特化的时候，只需偏特化定义random_access_iterator_tag即可，因为：

任何一个迭代器，其类型永远应该落在“该迭代器所隶属之各种类型中，最强化的那个”。

但是，在定义STL算法的时候，函数可以接受各种类型的迭代器，因此：

以算法所能接受之最低阶迭代器类型，来为其迭代器型别参数命名。

任何迭代器都应该提供这五个内嵌型别，因此为了统一定义，STL提供iterator class，每个新设计的迭代器都继承自它：（注意到后三个参数都有默认值）

__type_traits

除了iterator可以有traits技法之外，SGI-STL将其扩展为用于萃取型别的特性的__type_traits

此举允许针对不同的型别属性，在编译时期就完成函数派送决定（例如，如果一个型别具备trivial_default_constructor等等，就可以不用constructor等，而是直接采用内存处理操作，比如malloc(),memecpy())

在定义__type_traits类时，初始将所有内嵌型别都默认为__false_type，随后再针对所有标量型别进行特化，这样就可以实现这一功能。

注意在定义__true_type, __false_type时直接定义了一个类，以满足函数传参的自动推导：