STL内存管理详细分析

        STL中内存管理非常精妙，本文以SGI STL为例，分析其内存管理的设计思路，也是对侯捷老师的《STL源码剖析》中相关内容的总结。

        首先，从总体上看，STL空间配置器分为两级，针对大内存的申请，调用第一级空间配置器，对于小内存的申请，则调用第二级配置器。

        第一级空间配置器对外提供了allocate()，deallocate(),reallocate()三个函数供用户使用，同时，其内部定义了oom_allocate()和oom_reallocate()函数，用于处理内存不足的情况。

        deallocate()函数直接调用free函数释放内存，无须关心其他问题，重点在于内存不足情况下allocate()函数和reallocate()函数是如何应对的。

        allocate()函数首先调用malloc函数获取内存，在内存不足的情况下，该函数会返回空指针NULL，当malloc函数返回NULL时，则会调用oom_allocate()函数尝试释放一些内存并再次进行申请。

        这就是第一级空间配置器所提供的一种缓冲机制，第一级配置器中定义了一个函数指针，这个指针所指向的函数由用户所定义，因为只有用户知道哪些内存可以被释放来腾出空间，如果没有为该函数指针赋予相应的函数，则此时直接会抛出bad_alloc异常，若该函数指针被指定，则会不停调用该函数，直到申请到足够的内存，这里把它叫做内存不足处理函数，它的运行过程如图所示

        reallocate函数的内部运行过程和allocate函数的过程是相似的，只不过把malloc换成了realloc，oom_allocate换成了oom_reallocate，过程都是一样的。

        第二级内存配置器负责小内存的管理

        当申请大量的小内存时，一方面会把完整的内存区间划分的很破碎，当再次申请较大的内存时，可能会出现没有足够长的区间的情况，另一方面，大量的小区间也会使 *** 作系统用来记录内存状态的数据结构很臃肿。

        第二级内存配置器所采取的策略是，在第一次申请小内存时，先申请一大块内存留作备用，以后再申请小内存时，直接从上次申请的那一大块内存中划去要求的部分，不再向系统申请。

        同样的，第二级空间配置器提供了标准接口allocate()、deallocate()、reallocate()三个接口，在介绍这三个接口之前，先介绍一下接下来会遇到的一些名词。

        1 内存区块，有时也简称区块

        内存区块是指一块小内存，它的大小均为8的倍数，最大为128Bytes，即有8、16、24、32、40、48、56、64、72、80、88、96、114、122、128这几种，内存区块有自己的首地址，可以存储数据。在每个区块的前8个字节，存储下一个可用区块的地址，通过这种方式，可以形成一条区块链表

        2 freelist数组

        freelist数组是一个数组，内含16个元素，每一个元素是一个区块链表的首指针

        3 内存池

        内存池是是一大块内存，它有三个参数：起始地址，终止地址以及大小，内存池的大小=终止地址 - 起始地址

        在初始状态下，内存池是空的，内存区块也是不存在的，freelist数组中保存的都是空指针。

        我们从这种状态下开始分析，该机制是如何运作的。

        当申请的内存大于128bytes时，直接转交第一级配置器进行内存申请。

        当申请的内存不大于128bytes时，假设申请n字节

        1 计算（n + 7）/7，得到一个整数值i，这个i即为freelist的元素索引

        2 访问freelist位于i的元素，此时该元素为NULL，不指向任何可用区块，这时将n向上调整为8的倍数，并调用refill函数

        3 refill函数的作用是给freelist重新填充内存区块，这些区块从内存池中获得，一次默认取20个，通过函数chunk_alloc获得

        chunk_alloc函数返回的是一块长度为nobjsn的内存块，refill函数需要将这一整块连续内存分割为一个个内存区块，并构建链表的链接关系

        在内存充足的情况下，第一个内存块会被返回给用户使用，从第二块内存块开始构建链接关系，如图所示

        在内存不足的情况下，假如只分配到了一个区块，则该区块直接交给用户使用，freelist不进行更新

        如果不足20个，则仍将获得的内存构建链接关系。

        如果一个区块都没有获得，因为chunk_alloc函数内部调用了第一级配置器填充内存池，因此会按照第一级内存配置器的方式处理内存不足的情况。

        这里我们要关注几个参数

        1 申请的内存总大小——sizenobjs，这里用total_bytes来表示

        2 内存池剩余空间——用bytes_left表示

        如果total_bytes小于bytes_left，则直接划走total_bytes这么多内存，同时更新内存池的状态

        如果内存池的剩余空间不够申请的那么多区块，即size < bytes_left < total_bytes，即能够供应一部分区块，则计算最多能划多少块，并划走

        如果连一个区块都无法供应，这时候就要给内存池“加水”了

        在“加水”之前，首先要把内存池中剩下的水收集起来，别浪费了，加到freelist上去，具体的步骤是，根据剩下的内存的大小确定freelist的index，因为每个内存块都是8的倍数，划走时也按照8的倍数划分的，因此生下来的内存一定可以构成一个内存区块，找到合适的freelist位置后，将这个区块加到freelist上，这时，就可以开始“加水”了

        首先要确定“加多少水”，即为内存池填充的内存总量

        1 加完“水”后，要满足这次的内存申请的量，即大于total_bytes

        2 加完“水”后，内存池的大小应该比上一次的要大

        SGI STL选择的量是

        2 × total_bytes + heap_size >> 4

        heap_size是以往内存池的容量的累加和，这里把它作为一个附加变量来看待，要满足，随着“加水”次数变多，每次加水的量应该越来越大这个条件

        确定加多少水后，通过malloc函数获取内存

        如果获取成功，则更新内存池的状态，并递归调用chunk_malloc，因为内存池已经充足，下一次能够直接获取指定的内存

        如果没能获取那么多内存

        首先，遍历freelist，如果freelist里面有大小大于一个size的空闲区块，则将这个区块加入到内存池，并递归

        注意，这里的遍历并不是那种从freelist第一个开始逐个检查，而是以size为起点，确定freelist中相应的index，如果该index不含有空闲区块，则将size增加8字节，也就是检查下个freelist，直到后面的freelist都检查完，中途找到任何一个空闲区块，都会立即返回，不再遍历

如果遍历freelist也找不到足够的空闲区块，那么只能指望第一级配置器中由用户设置的内存不足处理函数能否解决，这里转交给第一级空间配置器，这时，要么第一级空间配置器顺利获得内存，这时会更新内存池，并递归，没能顺利获得内存，则会抛出异常。

        释放内存的过程相对简单，由第二级内存配置器分配的内存，在释放时并不交由free函数进行释放，也不放到内存池中，而是把内存加入到freelist链表中，以备下次使用，这个过程主要是简单的链表 *** 作，不作详解。

        freelist中，每一个元素都是obj，obj的结构如图所示

        这里为什么要采用这种结构？

        首先考虑它的功能，它是内存区块的链表结点，它需要记录当前区块的地址，以及下个区块的地址，每个地址都是8个字节的指针，用一个struct来表示，需要16字节，而使用union结构，只需要8个字节

        在每个内存区块的前8个字节处，是个obj对象，它存储着下一个内存区块的地址，当用free_list_link来解引用这个指针时，有效区间为这8个字节，client_data是一个长度为1的数组，只有一个元素，它就是内存区块的第一个字节，为这个字节定义一个变量，并对它取址，得到的就是当前区块的地址，这里采用数组的形式而不是直接定义一个char，目的是直接将client_data作为数组首地址返回，而不需要调用取址运算符，将该内存区块返回时，返回client_data，无须进行类型转换，直接在union中切换就行，状态的改变不会改变前8个字节的内容，但内存区块交出去后，前八个字节的内容丢失也不重要了，在将内存区块加入到freelist中时，会重新设置前8个字节的值，保证数据的有效性。

经典书籍比较多，其中最经典的就是《C++标准程序库：自修教程与参考手册》。

1、《C++标准程序库：自修教程与参考手册》

这本书作为学习STL的第一本书是绝对适合的，一开始就会有C++语言的必备知识，以免你一头扎进STL中直接淹死。

《The C++ Standard Library》（中文版《C++ 标准程序库》）不仅对每一个程序库组件提供范围广泛的说明，也对繁杂的感念提供清楚明亮的解释，并描述高效运用这些组件时需要的实际编程细节，提出一个又一个的范例程序。 

这本包含最新资料的完整书籍，反映出被 ANSI/ISO C++ 语言标准规格书纳入的 C++ 标准程序库的结构。更明确地说，本书将焦点放在标准模板库（Standard Template Library）身上，检验其中的容器（containers）、迭代器（iterators）、仿函数（functors）和算法（algorithms）。

你还可以找到特殊容器、字符串（strings）、数值类别、国际化议题、IOStream。每一个组件都有深刻的呈现，包括其介绍、设计、运用实例、细部解说、陷阱、意想不到的危险，以及相关类别和函数的确切标记（signature）和定义。

一份见解深刻的基础概念介绍和一个程序库综合鸟瞰，会对新手带来快速的提升。

2、《Effective STL 中文版: 50条有效使用STL的经验》

说到Scott Meyers的大名，C++程序员应该是无人不知无人不晓，他开创性的写了两本C++巨著《Effective C++》和《More Effective C++》都是每一个C++程序员必备书籍。

这本书自然也不例外，其中讲解了50条容易将C++程序员引入歧途的错误案例和正确修正使用方法。每一个使用STL的程序员都必备该书。

3、《STL源码剖析》

侯捷先生出品的书籍，一般品质都有所保证。这也是侯捷先生自己原创的一本书，这本书主要是深入到SGI版本的STL实现中，将STL的代码抽丝剥茧，将最鲜血淋漓的那部分取出来给大家指导清除。阅读这本书。

学习STL是次要的，学习数据结构是次要的，主要是要学习侯捷先生治学的精神和分析源代码的方式方法，这才是最重要的。这本书一再印刷，销量已经证明了一切。各大图书商城有售。

4、《STL扩展技术手册（卷1）：集合和迭代器》

相信一大群读者没有听说过这本书，但是这本书也是非常值得推荐的一本STL书籍，这本书既不是教你STL怎么用，也不是教你STL的实现是怎么样的，而是教你如何扩展你自己的STL组件。基本上是国内C++图书界中唯一一本讲解STL扩展的专著。

作者之前写过一本《Imperfact C++》的书，这本书不知道为什么在国内的销量也不好，但是该作者的C++技术造诣非常深厚，他的著作也是每一个想要深入学习C++的读者所必读的书籍。作者本来打算将STL 扩展技术手册分为1，2两卷出版，可惜第一卷出版后，第二卷再也出不来了。

5、介绍

STL（StandardTemplate Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库（C++Standard Library）中，是ANSI/ISOC++标准中最新的也是极具革命性的一部分。

该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。

从逻辑层次来看，在STL中体现了泛型化程序设计的思想（genericprogramming），引入了诸多新的名词，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。

与OOP（object-orientedprogramming）中的多态（polymorphism）一样，泛型也是一种软件的复用技术；

从实现层次看，整个STL是以一种类型参数化（typeparameterized）的方式实现的，这种方式基于一个在早先C++标准中没有出现的语言特性--模板（template）。

如果查阅任何一个版本的STL源代码，你就会发现，模板作为构成整个STL的基石是一件千真万确的事情。除此之外，还有许多C++的新特性为STL的实现提供了方便；

6、STL的六大组件

·        容器（Container），是一种数据结构，如list，vector，和deques ，以模板类的方法提供。为了访问容器中的数据，可以使用由容器类输出的迭代器；

·        迭代器（Iterator），提供了访问容器中对象的方法。例如，可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上，C++的指针也是一种迭代器。但是，迭代器也可以是那些定义了operator()以及其他类似于指针的 *** 作符地方法的类对象；

·        算法（Algorithm），是用来 *** 作容器中的数据的模板函数。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象，函数本身与他们 *** 作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用；

·        仿函数（Function object，仿函数(functor)又称之为函数对象（functionobject），其实就是重载了() *** 作符的struct，没有什么特别的地方

·        迭代适配器（Adaptor）

·        空间配制器（allocator）其中主要工作包括两部分：对象的创建与销毁和内存的获取与释放

以上就是关于STL内存管理详细分析全部的内容，包括:STL内存管理详细分析、C++ STL有哪些经典书籍、等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！