【VC++开源代码栏目提醒】:以下是网学会员为您推荐的VC++开源代码-STL源码剖析笔记 - 大学课件,希望本篇文章对您学习有所帮助。
第1章 STL 概论1.2 STL 六大组件STL 提供六大组件,彼此可以组合套用:1.容器(container):各种数据结构,如 vectorlistdequesetmap 等2.算法(algorithm) :各种
常用算法如 sortsearchcopyerase......3.迭代器(iterator):扮演容器与算法之间的胶着剂。
所以 STL 容器都附带有自己专属的迭代器。
指针也是一种迭代器。
4.仿函式(functors) :行为类似函数,可作为算法的某种策略,从实现的角度讲,仿函式是一种重载了 operator的 class 或 class template。
仿函式是否就是 cprimer 中的函数对象?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_typeallocator::pointerallocator::const_pointerallocator::referenceallocator::const_referenceallocator::size_typeallocator::difference_type第二组:构造与析构函数Allocator::rebind一个嵌套的 (nested)class template。
class rebindltUgt拥有唯一成员 other, 那是一个 typedef,代表 allocatorltUgt。
allocator::allocator---默认构造函数allocator::allocatorconst allocatoramp---拷贝构造函数template ltclass Ugtallocator::allocatorconst allocatorltUgtamp --- 泛化的拷贝构造函数allocator::allocator---默认的析构函数第三组:取地址函数pointer allocator::addressreference x const ---传回某个对象的地址,算式 a.addressx等同于ampx。
const_pointer allocator::addressconst_reference x const --- 传回某个 const 对象的地址,算式a.addressx等同于ampx。
第四组:空间分配与释放pointer allocator::allocatesize_type n cosnt void 0 --- 配置空间,足以储存 n 个 T 对象。
第二自变量是个提示。
实作上可能会利用它来增进区域性(locality) ,或完全忽略之。
void allocator::deallocatepointer p size_type n ---归还先前分配的空间。
size_type allocator::max_size const --- 传回可成功分配的最大量。
第五组:construct 和 destroy 函数void allocator::constructpointer p const Tamp x --- 等同于 newconst void p Tx。
void allocator::destroypointer p --- 等同于 p-gtT。
2.1.1 设计一个空间配置器 JJ::allocator 在书中,侯捷先生写了一个分配器 JJ: :allocator。
代码见书。
2.2 具备 sub-alloction 的 SGI allocator SGI STL 配置器与标准规范不同,其名称是 alloc 而非 allocator,而且不接受任何自变量。
如果要在
程序中使用 SGI STL 配置器,则不能采用标准写法: Vectorltint std::allocatorltintgtgt iv//在
vc 或 c builder 中这么写 Vectorltint std::allocgt 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负责对象析构。
配置器定义于ltmemorygt中,其中包括如下两个头文件: include ltstl_alloc.hgt //负责内存分配与释放 include ltstl_construct.hgt //负责对象构造和析构2.2.3 构造和析构函数:construct 和 destroy 下面
代码是ltstl_construct.hgt中的部分内容: includeltnew.hgt //construct接受一个指针 p 和一个初值 value Templateltclass T1 class T2gt Inline void constructT1 p const T2amp value Newp T1value//placement new 用法调用构造函数 T1::T1value。
这里用到了 placement new,它能实现在指定的内存地址上用指定类型的构造函数构造一个对象 //destroy的第一个版本,接受一个指针 Templateltclass Tgt Inline void destroyT pointer Pointer-gtT //调用析构函数 T 在调用 destroy函数同时释放 n 个对象(假设类型为 T)时,SGI 提供了方法可以判定对象是否有 non-trivial destructortrival:琐碎的,无价值的,不重要的,如果没有则不必要循环为每个对象调用 T::T,以提高效率
代码如下: //以下是 destroy的第二版本,接受两个迭代器,准备将first last范围内的所有物件析 //构掉,因为不知道这个范围有多大,万一很大,但是每个物件的析构函数都是无关痛 //痒的(triaval destructor),那么一次次呼叫这些无关痛痒的析构函数,对效率是一种损 //害,所以此函数设法找出元素的数值类型,进而利用__type_traitsltgt选 // 择 适 当 措 //施 template ltclass ForwardIteratorgt // __false_type 表明是具有 non trivial destructor,所以要循环调用 destroy inline void __destroy_auxForwardIterator first ForwardIterator last __false_type for first lt last first destroyampfirst template ltclass ForwardIteratorgt //__true_type 表明是具有 trivial destructor 不需要调用 destroy inline void __destroy_auxForwardIterator ForwardIterator __true_type //空函数体 //判断元素的型别,是否有 trival destructor template ltclass ForwardIterator class Tgt inline void __destroyForwardIterator first ForwardIterator last T typedef typename __type_traitsltTgt::has_trivial_destructor trivial_destructor __destroy_auxfirst last trivial_destructor template ltclass ForwardIteratorgt inline void destroyForwardIterator first ForwardIterator last __destroyfirst last value_typefirst //以下是 destroy第二版本针对迭代器为 char和 wchar的特化版 Inline void destroychar char Inline void destroywchar_t wcht_t 但是 c本身并不直接支持对“指针所指之物”的型别判断,也不支持“对象析构函数是否是 trival”的判断,这需要借助于 Traits 编程技法来完成的: typedef typename __type_traitsltTgt::has_trivial_destructor trivial_destructor 首先使用 value_type获取迭代器指向的物体类型,然后使用__type_traitsltTgt查看 T 是否有 non-trivial destructor。
2.2.4 空间的配置与释放 std::alloc 对象构造前的空间分配和对象析构之后的空间释放,由ltstl_alloc.hgt负责,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_templatelt0gt malloc_alloc typedef malloc_alloc alloc //令 alloc 为第一级配置器 else ... //令 alloc 为第二级配置器 typedef __default_alloc_templatelt__NODE_ALLOCATOR_THREADS 0gt 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 来分配内存: if 0 includeltnewgt define __THROW_BAD_ALLOC throw bad_alloc elif defined__THROW_BAD_ALLOC include ltiostream.hgt define __THROW_BAD_ALLOC cerrltltquotout of memoryquotltltendlexit1 endif//注意,无「template 型别参数」 。
至于「非型别参数」inst,完全没派上用场。
template ltint instgtclass __malloc_alloc_template private://以下都是函数指针,所代表的函式将用来处理内存不足的情况。
// oom : out of memory.static void oom_mallocsize_tstatic void oom_reallocvoid size_tstatic void __malloc_alloc_oom_handlerpublic:static void allocatesize_t n void result mallocn//第一级配置器直接使用 malloc // 以下,无法满足需求时,改用 oom_malloc if 0 result result oom_mallocn return resultstatic void deallocatevoid p size_t / n / freep //第一级配置器直接使用 freestatic void reallocatevoid p size_t / old_sz / size_t new_sz void result reallocp new_sz//第一级配置器直接使用 realloc // 以下,无法满足需求时,改用 oom_realloc if 0 result result oom_reallocp new_sz return result//以下模拟 C的 set_new_handler. 换句话说,你可以透过它,//指定你自己的 out-of-memory handlerstatic void set_malloc_handlervoid f//蓝色部分作为参数,最后一个和 void //一起组成 void表示返回值是一个函数指针 void old __malloc_alloc_oom_handler __malloc_alloc_oom_handler f returnold // malloc_alloc out-of-memory handling //初值为 0。
有待用户设定。
__malloc_alloc_oom_handler 是一个函数指针 template ltint instgt void __malloc_alloc_templateltinstgt::__malloc_alloc_oom_handler 0 template ltint instgt void __malloc_alloc_templateltinstgt::oom_mallocsize_t n void my_malloc_handler void result for //不断尝试释放、配置、再释放、再配置… my_malloc_handler __malloc_alloc_oom_handler if 0 my_malloc_handler __THROW_BAD_ALLOC my_malloc_handler//呼叫处理例程,企图释放内存。
result mallocn //再次尝试配置内存。
if result returnresult template ltint instgt void __malloc_alloc_templateltinstgt::oom_reallocvoid p size_t n void my_malloc_handler void result for //不断尝试释放、配置、再释放、再配置… my_malloc_handler __malloc_alloc_oom_handler if 0 my_malloc_handler __THROW_BAD_ALLOC my_malloc_handler//呼叫处理例程,企图释放内存。
result reallocp n//再次尝试配置内存。
if result returnresult //注意,以下直接将参数 inst 指定为 0。
typedef __malloc_alloc_templatelt0gt 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 8088 96 104 112 120 128 bytes 的小额区块。
free-lists 的节点结构如下: union obj union obj free_list_link char client_data1 / The client sees this. / 我们可能会想,为了维护链表,每个节点需要额外的指针(指向下一节点) ,但是这里用的是 union,从第一个字段看,obj 可被视为指针,指向相同形式的另一个 obj,从第二个字段看,指向实际的区块。
一物二用,不会为了维护串行所必须的指针而造成内存浪费。
第二级分配器的部分实现: enum __ALIGN 8//小型区块的上调边界 enum __MAX_BYTES 128//小型区块的上限 enum __NFREELISTS __MAX_BYTES/__ALIGN//free-lists 个数 //以下是第二级配置器。
//注意,无「template 型别参数」 ,且第二参数完全没派上用场。
//第一参数用于多线程环境下。
本书不讨论多线程环境。
template ltbool threads int instgtclass __default_alloc_template private: // ROUND_UP 将 bytes 上调至 8 的倍数。
static size_t ROUND_UPsize_t bytes return bytes __ALIGN-1 amp __ALIGN - 1 private: unionobj //free-lists 的节点构造 union obj free_list_link char client_data1 / The client sees this. / private: // 16 个 free-lists static obj volatilefree_list__NFREELISTS // 以下函式根据区块大小,决定使用第 n 号 free-list。
n 从 1 起算。
static size_t FREELIST_INDEXsize_t bytes return bytes __ALIGN-1/__ALIGN - 1 // 传回一个大小为 n 的对象,并可能加入大小为 n 的其它区块到 free list. static void refillsize_t n// 配置一大块空间,可容纳 nobjs 个大小为 quotsizequot 的区块。
// 如果配置 nobjs 个区块有所不便,nobjs 可能会降低。
static char chunk_allocsize_t size int ampnobjs // Chunk allocation state. static char start_free//内存池起始位置。
只在 chunk_alloc中变化 static char end_free//内存池结束位置。
只在 chunk_alloc中变化 static size_t heap_sizepublic: static void allocatesize_t n / 详述于后 / static void deallocatevoid p size_t n / 详述于后 / static void reallocatevoid p size_t old_sz size_t new_sz//以下是 static data member 的定义与初值设定template ltbool threads int instgtchar __default_alloc_templateltthreads instgt::start_free 0 template ltbool threads int instgt char __default_alloc_templateltthreads instgt::end_free 0 template ltbool threads int instgt size_t__default_alloc_templateltthreads instgt::heap_size 0 template ltbool threads int instgt __default_alloc_templateltthreads instgt::obj volatile __default_alloc_templateltthreads instgt::free_list__NFREELISTS 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2.2.7 空间分配函数 allocate 此函数首先判断区块大小,大于 128 bytes 就调用第一级配置器,小于 128 bytes 就检查对应的 free list。
如果 free list 之内有可用的区块,就直接拿来用,如果没有可用区块,就将区块大小上调至 8 倍数边界,然后调用 refill,准备为 free list 重新填充空间。
refill将于稍后介绍。
Allocate的算法描述: 算法:allocate 输入:申请内存的大小 size 输出:若分配成功,则返回一个内存的地址,否则返回 NULL ifsize 大于 128) 启动第一级分配器直接调用 malloc 分配所需的内存并返回内存地址; else 将 size 向上 round up 成 8 的倍数并根据大小从 free_list 中取对应的表头 free_list_head iffree_list_head 不为空) 从该列表中取下第一个空闲块并调整 free_list; 返回 free_list_head else 调用 refill 算法建立空闲块
列表并返回所需的内存地址; Allocate的
代码实现: // n must be gt 0 static void allocatesize_t n obj volatile my_free_list obj result // 大于 128 就呼叫第一级配置器 If n gt size_t __MAX_BYTES returnmalloc_alloc::allocaten // 寻找 16 个 free lists 中适当的一个 my_free_list free_list FREELIST_INDEXn result my_free_list if result 0 // 没找到可用的 free list,准备重新填充 free list void r refillROUND_UPn return r // 调整 free list my_free_list result -gt free_list_link return result 区块子 free_list 中拔出,示意图如下:2.2.8 空间释放函数 deallocate 此函数首先判断区块大小,大于 128 bytes 就呼叫第一级配置器,小于 128 bytes 就找出对应的 free list,将区块回收。
Deallocate算法描述: 算法:deallocate 输入:需要释放的内存块地址 p 和大小 size ifsize 大于 128 字节)直接调用 fre.