stl源码剖析 pdf_读书笔记：《STL源码剖析》-I

624b871e37494c4bfd37832fd8d58ab2.png
此篇章为《STL源码剖析》的读书笔记。对应于C++高级教程-前导篇 在需要作出解释的地方，我会添加相应的注释，结合视频学习，与笔者的知识储备。如果有任何错误，或者疑虑，请发送邮件至 ashior@qq.com。

导论

STL六大组件

  1. 容器(containers)：各种数据结构，如vector，list，deque，set，map，用来存放数据。
  2. 算法(algorithms)：各种常见的算法如sort，search，copy，erase等。
  3. 迭代器(iterators)：一种将operator*，operator->，operator++，operator--等指针相关操作予以重载的class template。
  4. 仿函数(functors)：一种重载了operator()的class或class template。一般函数指针可以视为狭义的仿函数。
  5. 配接器(adapters)：用来修饰容器或者仿函数或迭代器接口的东西。诸如queue和stack，其实只能算是一种容器配接器，因为他们的底部完全借助deque。
  6. 配置器(allocators)：实现了动态空间配置、空间管理、空间释放的class template。

753a14450af06199c74f36be20126906.png

阅读前的知识储备

临时对象的产生与运用

静态常量整数成员在class内部直接初始化

in-class static constant integer initialization

如果class内含有const static integerdata member，我们可以在class之内，直接给予初值。所谓的integer泛指所有整数型别，不单指int。

注意：static类型的数据在声明之后，应该在类外进行定义(初始化)。

increment/decrement/dereference 操作符

increment/decrement：迭代器必须能够移动(operator++)

dereference：取值操作(operator*)

前闭后开区间表示法[)

任何一个STL算法， 都需要获得由一对迭代器(泛型指针)所标示的区间，用意标示操作范围。以[first, last)表示。

1a6f3af48edf75c35bfc3280be1e7364.png

function call操作符(operator())

e.g.

#include <iostream>
using namespace std;

// 由于将operator()重载，因此plus成了一个仿函数
template<class T>
struct plus {
    T operator() (const T& x, const T& y) const { return x + y; }
}

// 由于将operator()重载，因此minus成了一个仿函数
template<class T>
struct minus {
    T operator() (const T& x, const T& y) const { return x - y; }
}

int main()
{
    // 以下产生仿函数
    plus<int> plusobj;
    minus<int> minusobj;

    // 以下使用仿函数，就像使用一般函数一样
    cout << plusobj(3, 5) << endl;  // 8
    cout << minusobj(3, 5) << endl; // -2

    // 以下直接产生仿函数的临时对象(第一对小括号)，并调用之(第二队小括号)
    cout << plus<int>()(43, 50) << endl;  // 93
    cout << minus<int>()(43, 50) << endk; // -7
}

上述的plus<T>和minus<T>已经非常接近STL的实现，唯一的差别在于它缺乏“可配接能力”。在以后的章节，我们会继续探讨。

注意：此篇对应于原书第一章，内容为看懂书籍的前置条件，阅读本书之前，最好是有相关的C++基础，同时对上述的内容能够有一定的了解，方便后续学习。

空间配置器(allocator)

为什么不说allocator是内存配置器而说它是空间配置器呢？因为空间不一定是内存，空间也可以是磁盘或其他辅助存储介质。

空间配置器的标准接口

在网站 中给出了allocator的介绍，下图为部分截图，阐述其原型设计。

fd136f741761601f3ff606da68c30f31.png

SGI特殊的空间配置器

SGI STL 的配置器与众不同，也与标准规范不同，其名称是alloc而非allocator，而且不接受任何参数。换句话说，如果你要在程序中明白采用SGI配置器，则不能采用标准写法：

vector<int, std::allocator<int> iv; // in VC or CB
vector<int, std::alloc> iv;         // in GCC

SGI STL 的每一个容器都已经指定其缺省的空间配置器为alloc。例如下面的vector声明：

template <class T, class Alloc = alloc> //缺省使用alloc为配置器
class vector { ... };

使用临时对象分配/释放内存。

// 分配512bits
int* p = allocator<int>().allocator(512, (int*)0);
// 释放512bits
allocator<int>().deallocate(p, 512);

allocator只时基层内存配置/释放行为(也就是::operator new和::operator delete)的一层薄薄的包装。而实际上前者也是调用C语言的malloc()，这每次调用都会产生额外的空间，后者调用C语言的free()。一般而言，我们使用C++内存配置操作和释放操作为：

class Foo { ... };
Foo *pf = new Foo;   // 配置内存，然后构造对象
delete pf;           // 将对象析构，然后释放内存

其中new算式内含两阶段操作：1.调用::operator new配置内存；2.调用Foo::Foo()构造对象内容。 delete算式也包含两阶段操作：1.调用~Foo::Foo()将对象析构；2.调用::operator delete释放内存。

为了细化分工，STL allocator将两阶段操作区分开来。内存配置操作由alloc::allocate()负责，内存释放操作由alloc::deallocate()负责；对象构造操作由::construct负责，对象析构操作由::destroy()负责。

construct()和destroy()

60fee5e03db37c5d82ad8e68f8fe24b8.png

construct()接受一个指针p和一个初值value，该函数的用途就是将初值设定到指针所指的空间上。

destroy()第一个版本接受一个指针，准备将指针所指之物析构掉，直接调用该对象的析构函数。第二个版本为接收一个区间[first, last)，将区间范围内的所有对象析构掉。

trivial destructor表示对象的析构函数都无关痛痒，如果区间一大，析构这些函数又无关痛痒，所以十分消耗资源。因为通过value_type()获得迭代器所指对象的型别，再利用__type_traits<T>判断该型别的析构函数是否无关痛痒。具体如何判断以后再说。

考虑到小型区块所可能造成的内存破碎问题，SGI设计了双层级配置器，第一级配置器直接使用malloc()和free()，第二级配置器则视情况采用不用的策略(需求区块是否大于128bytes)。

263598314106a0be7e968285aadaedc8.png

94a751d01f07715d2f1ae72e9f2d4595.png

第一级适配器以malloc()，free()，reaclloc()等C函数执行实际的内存配置、释放、重配置操作。第二级配置器多了一些机制，避免太多小额区块造成内存的碎片。

813c0fa96e09df1eb1feaaf818fa52dc.png

SGI第二级配置器的做法是，如果区块够大，超过128字节时，就移交第一级配置器处理。当区块小于128字节时，则以内存池(memory pool)管理，此法又称为次层配置(sub-allocation)：每次配置一大块内存，并维护对应的自由链表(free-list)。下次若再有相同大小的内存需求，就直接从free-lists中拔出。如果没有，则向系统要一大块内存，然后做切割，此时切割出来的小内存块，不带cookie。如果客户端释放小额区块，就由配置器回收。为方便管理，任何小额区块的内存需求量上调至8的倍数，并维护16个free-lists，各自管理大小分别为8,16,24...128字节。

bae4c120db8e7f60c9ccb07ab732c22a.png

在G4.9中编译器使用的是不作任何优化的空间配置器，如果需要制定，则需要指明第二参数：

vector<string, __gnu_cxx::__pool_alloc<string>> vec;

如果free-list中没有可用的区块，将区块大小上调至8的倍数边界，然后调用refill()，准备为free-list重新填充空间。refill()之后介绍。

空间的释放，大于128字节就调用第一级配置器，小于128字节就找出对应的free list，将区块回收。

d91decd28cc3bfeaf3e030fdf3d7074a.png

refill()重新填充空间，新的空间将取自内存池(经由chunk_alloc()完成)。内存池实际操练结果如下图：

d6bb87138827f022163c6ec0e57d9fdd.png

1801fb0f1b436eff93d63041972a4afb.png