第1页 / 共166页
第2页 / 共166页
第3页 / 共166页
第4页 / 共166页
第5页 / 共166页
第6页 / 共166页
第7页 / 共166页
第8页 / 共166页
STL源码剖析读书笔记.doc
第 1 章 STL 概论
1.2 STL 六大组件
STL 提供六大组件，彼此可以组合套用：
1.容器（container）：各种数据结构，如 vector,list,deque,set,map 等
2.算法（algorithm）：各种常用算法如 sort,search,copy,erase......
3.迭代器（iterator）：扮演容器与算法之间的胶着剂。所以 STL 容器都附带有自己专属的迭
代器。指针也是一种迭代器。
4.仿函式（functors）：行为类似函数，可作为算法的某种策略，从实现的角度讲，仿函式是
一种重载了 operator()的 class 或 class template。仿函式是否就是 c++primer 中的函数对象？
5.适配器（adaptor）：一种用来修饰容器或仿函式或迭代器接口的东西，有 function adaptor，
container adaptor，iterator adaptor。
6.分配器（allocator）：负责空间分配与管理。
1.7 STLport 版本
STLport 版本是以 SGI STL 为蓝本的高度可移植性版本。
第 2 章 空间分配器
2.1 空间配置器的标准接口
根据 STL 规范，以下是 allocator 的必要接口：
第一组：各种 type 类型
//以下各种 type 的设计原由，第三章详述。
allocator::value_type
allocator::pointer
allocator::const_pointer
allocator::reference
allocator::const_reference
allocator::size_type
allocator::difference_type
第二组：构造与析构函数
Allocator::rebind
一个嵌套的（nested）class template。class rebind拥有唯一成员 other， 那是一个 typedef，
代表 allocator。
allocator::allocator()---默认构造函数
allocator::allocator(const allocator&)---拷贝构造函数
template allocator::allocator(const allocator&) --- 泛化的拷贝构造函数
allocator::~allocator()---默认的析构函数
第三组：取地址函数
pointer allocator::address(reference x) const ---传回某个对象的地址，算式 a.address(x)等同于
&x。
const_pointer allocator::address(const_reference x) const --- 传回某个 const 对象的地址，算式
a.address(x)等同于&x。
第四组：空间分配与释放
pointer allocator::allocate(size_type n, cosnt void* = 0) --- 配置空间，足以储存 n 个 T 对象。第
二自变量是个提示。实作上可能会利用它来增进区域性（locality），或完全忽略之。
void allocator::deallocate(pointer p, size_type n) ---归还先前分配的空间。
size_type allocator::max_size() const --- 传回可成功分配的最大量。
第五组：construct 和 destroy 函数
void allocator::construct(pointer p, const T& x) --- 等同于 new((const void*) p) T(x)。
void allocator::destroy(pointer p) --- 等同于 p->~T()。
2.1.1 设计一个空间配置器 JJ：：allocator
在书中，侯捷先生写了一个分配器 JJ：：allocator。代码见书。
2.2 具备 sub-alloction 的 SGI allocator
SGI STL 配置器与标准规范不同，其名称是 alloc 而非 allocator，而且不接受任何自变
量。如果要在程序中使用 SGI STL 配置器，则不能采用标准写法：
Vector> iv;//在 vc 或 c++ builder 中这么写
Vector iv; //在 GCC 中这么写
但是令人欣慰的是，我们通常使用预设的空间配置器，很少需要自行指定配置器，而
SGI STL 的每一个容器都已经指定其预设的空间配置器为 alloc。
2.2.1 SGI 标准的空间配置器 std::allocator
该配置器符号部分标准，但效率差，SGI 自己不用，也不建议我们使用。
2.2.2 SGI 特殊的空间配置器 std::alloc
看下面的代码：
Class Foo{
......
}
Foo *of = new Foo;//配置内存，然后构造对象
Delete pf;//将对象析构，然后释放内存
为 了 精 密 分 工 ， STL alloctor 提 供 四 个 动 作 ： alloc::allocate() 负 责 内 存 分 配 ，
alloc::deallocate()负责内存释放，::construct() 负责对象构造，::destroy()负责对象析构。
配置器定义于中，其中包括如下两个头文件：
#include //负责内存分配与释放
#include //负责对象构造和析构
2.2.3 构造和析构函数：construct 和 destroy
下面代码是中的部分内容：
#include
//construct()接受一个指针 p 和一个初值 value
Template
Inline void construct(T1* p,
const T2& value){
New(p) T1(value);//placement new 用法;调用构造函数 T1::T1(value)。这里用到了
placement new，它能实现在指定的内存地址上用指定类型的构造函数构造一个对象
}
//destroy()的第一个版本，接受一个指针
Template
Inline void destroy(T* pointer){
Pointer->~T(); //调用析构函数 ~T()
}
在调用 destroy()函数同时释放 n 个对象（假设类型为 T）时，SGI 提供了方法可以判定
对象是否有 non-trivial destructor(trival:琐碎的，无价值的，不重要的)，如果没有则不必要循
环为每个对象调用 T::~T()，以提高效率代码如下：
//以下是 destroy()的第二版本，接受两个迭代器，准备将[first, last)范围内的所有物件析
//构掉，因为不知道这个范围有多大，万一很大，但是每个物件的析构函数都是无关痛
//痒的（triaval destructor），那么一次次呼叫这些无关痛痒的析构函数，对效率是一种损
//害，所以此函数设法找出元素的数值类型，进而利用__type_traits<>选 // 择 适 当 措
//施
template
// __false_type 表明是具有 non trivial destructor，所以要循环调用 destroy
inline void
__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {
for ( ; first < last; ++first)
destroy(&*first);
}
template
//__true_type 表明是具有 trivial destructor 不需要调用 destroy
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {} //空函数体
//判断元素的型别，是否有 trival destructor
template
inline void __destroy(ForwardIterator first, ForwardIterator last, T*) {
typedef typename __type_traits::has_trivial_destructor trivial_destructor;
__destroy_aux(first, last, trivial_destructor());
}
template
inline void destroy(ForwardIterator first, ForwardIterator last) {
__destroy(first, last, value_type(first));
}
//以下是 destroy()第二版本针对迭代器为 char*和 wchar*的特化版
Inline void destroy(char*, char*){}
Inline void destroy(wchar_t*, wcht_t*){}
但是 c++本身并不直接支持对“指针所指之物”的型别判断，也不支持“对象析构函数
是否是 trival”的判断，这需要借助于 Traits 编程技法来完成的：
typedef typename __type_traits::has_trivial_destructor
首先使用 value_type()获取迭代器指向的物体类型，然后使用__type_traits查看 T 是
trivial_destructor;
否有 non-trivial destructor。
2.2.4 空间的配置与释放 std::alloc
对象构造前的空间分配和对象析构之后的空间释放，由负责，SGI 对此的
设计哲学如下：
向 system heap 申请空间；
考虑多线程情况；
考虑内存不足时的应对措施；
考虑过多小型区块可能造成的内存碎片（fragment）问题；
下面摘录的代码都暂时没有考虑多线程情况的处理。
C++内存分配基本动作是::operator new(),内存释放动作是::operator delete().这两个全域
函数相当于 c 的 malloc()和 free()，SGI 正是以 malloc()和 free()完成内存的分配与释放。
考虑小型区块可能造成的内存碎片问题，SGI 设计了双层级配置器，低一级分配器直接
使用 malloc()和 free(), 第二级分配器则视情况采用不同策略：当分配区块超过 128bytes，则
视之“足够大”，便使用低一级分配器；当分配区块小于 128bytes，则视之“过小”，便采用
复杂的 mempool 方式。
究竟使用哪种分配器，取决于__USE_MALLOC 是否被定义：
# ifdef __USE_MALLOC
...
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc; //令 alloc 为第一级配置器
# else
...
//令 alloc 为第二级配置器
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
#endif /* ! __USE_MALLOC */
其中，__malloc_alloc_template 就是第一级分配器，__default_alloc_template 就是第二级
分配器。
下面的小节中，我想以自底向上的顺序介绍 STL 的 allocator，首先讨论 STL 内建的两
种分配器，然后介绍 STL 如何封装这两种分配器对外提供统一的接口，最后用一个 vector
的例子看看容器如何使用这个 allocator。
2.2.5 第一级分配器__malloc_alloc_template
该分配器是对 malloc、alloc、free 的封装，并作出类似 c++ new-handler 的机制（所谓
new-handler 机制是指，你可以要求系统在内存分配无法被满足时，唤起一个你所指定的函
数，也就是说在::operator::new 无法完成任务，在丢出 std::bad_alloc 异常之前，会先调用用
户指定的处理例程，即 new-handler），这里作出类似 c++ new-handler 机制，而不能直接用
c++ new-handler 机制，是因为他不是使用::operator new 来分配内存：
include
define __THROW_BAD_ALLOC throw bad_alloc
#if 0
#
#
#elif !defined(__THROW_BAD_ALLOC)
#
#
#endif
include
define __THROW_BAD_ALLOC cerr<<"out of memory"<
//注意，无「template 型别参数」。至于「非型别参数」inst，完全没派上用场。
template
class __malloc_alloc_template {
private:
//以下都是函数指针，所代表的函式将用来处理内存不足的情况。
// oom : out of memory.
static void *oom_malloc(size_t);
static void *oom_realloc(void *, size_t);
static void (* __malloc_alloc_oom_handler)();
public:
static void * allocate(size_t n)
{
*result =malloc(n);//第一级配置器直接使用 malloc()
void
// 以下，无法满足需求时，改用 oom_malloc()
if (0 == result) result = oom_malloc(n);
return
result;
}
static void deallocate(void *p, size_t /* n */)
{
free(p); //第一级配置器直接使用 free()
}
static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
{
result =realloc(p, new_sz);//第一级配置器直接使用 realloc()
*
void
// 以下，无法满足需求时，改用 oom_realloc()
if (0 == result) result = oom_realloc(p, new_sz);
return
result;
}
//以下模拟 C++的 set_new_handler(). 换句话说，你可以透过它，
//指定你自己的 out-of-memory handler
static void (* set_malloc_handler(void (*f)()))()//蓝色部分作为参数，最后一个()和 void(*)
//一起组成 void(*)()表示返回值是一个函数指针
{
}
old)() = __malloc_alloc_oom_handler;
(*
void
__malloc_alloc_oom_handler = f;
return(old);
};
// malloc_alloc out-of-memory handling
//初值为 0。有待用户设定。 __malloc_alloc_oom_handler 是一个函数指针
template
void (* __malloc_alloc_template::__malloc_alloc_oom_handler)() = 0;
template
void * __malloc_alloc_template::oom_malloc(size_t n)
{
void
void
(* my_malloc_handler)();
*result;
for (;;)
{
(0 == my_malloc_handler)
//不断尝试释放、配置、再释放、再配置…
my_malloc_handler = __malloc_alloc_oom_handler;
if
(*my_malloc_handler)();//呼叫处理例程，企图释放内存。
result = malloc(n);
if
//再次尝试配置内存。
return(result);
(result)
{
__THROW_BAD_ALLOC; }
}
}
template
void * __malloc_alloc_template::oom_realloc(void *p, size_t n)
{
void
void
(* my_malloc_handler)();
*result;
for (;;)
{
(0 == my_malloc_handler)
//不断尝试释放、配置、再释放、再配置…
my_malloc_handler = __malloc_alloc_oom_handler;
if
(*my_malloc_handler)();//呼叫处理例程，企图释放内存。
result = realloc(p, n);//再次尝试配置内存。
if
return(result);
(result)
{
__THROW_BAD_ALLOC; }
}
}
//注意，以下直接将参数 inst 指定为 0。
typedef __malloc_alloc_template<0> malloc_alloc;
当 调 用 malloc 和 realloc 申 请 不 到 内 存 空 间 的 时 候 ， 会 改 调 用 oom_malloc() 和
oom_realloc()，这两个函数会反复调用用户传递过来的 out of memory handler 处理函数，直
到能用 malloc 或者 realloc 申请到内存为止。如果用户没有传递__malloc_alloc_oom_handler，
__malloc_alloc_template 会抛出__THROW_BAD_ALLOC 异常。
所以，内存不足的处理任务就交给类客户去完成。
2.2.6 第二级分配器__default_alloc_template
第二级配置器多了一些机制，避免太多小额区块造成内存的碎片。小额区块带
来的其实不仅是内存碎片而已，配置时的额外负担（overhead）也是一大问题。所谓的额外
负担如下：
这个分配器采用了内存池的思想，有效地避免了内碎片的问题（顺便一句话介绍一下内
碎片和外碎片：内碎片是已被分配出去但是用不到的内存空间，外碎片是由于大小太小而无
法分配出去的空闲块）。
如果申请的内存块大于 128bytes，就将申请的操作移交__malloc_alloc_template 分配器
去处理；如果申请的区块大小小于 128bytes 时，就从本分配器维护的内存池中分配内存。
分配器用空闲链表的方式维护内存池中的空闲空间，为了方便管理，SGI 第二级配置器
会主动将任何小额区块的内存需求量上调至 8 的倍数（例如客端要求 30 bytes，就自动调整
为 32bytes），并维护 16 个 free-lists，各自管理大小分别为 8, 16, 24, 32, 40, 48, 56, 64, 72, 80,
88, 96, 104, 112, 120, 128 bytes 的小额区块。free-lists 的节点结构如下：
union obj {
union obj * free_list_link;
char
client_data[1];
/* The client sees this. */
};
我们可能会想，为了维护链表，每个节点需要额外的指针（指向下一节点），但是这里
用的是 union，从第一个字段看，obj 可被视为指针，指向相同形式的另一个 obj，从第二个
字段看，指向实际的区块。一物二用，不会为了维护串行所必须的指针而造成内存浪费。
第二级分配器的部分实现：
enum {__ALIGN = 8};//小型区块的上调边界
enum {__MAX_BYTES = 128};//小型区块的上限
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};//free-lists 个数
//以下是第二级配置器。
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
