STL空间配置器

为了精密分工， STL将new和delete分别的两阶段动作分开 ： 内存配置 操作由成员函数**allocate() 负责 内存释放 操作由成员函数 deallcate() 负责 对象构造 操作由成员函数 construct() 负责 对象析构 操作由成员函数 destroy()**负责 内存分配过程中需要考虑的问题： 小块内存带来的内存碎片问题 小块内存频繁申请释放带来的性能问题 内存碎片问题是指;单从分配的角度来看。由于 频繁分配、释放小块内存容易在堆中造成外部碎片 (极端情况下就是堆中空闲的内存总量满足一个请求，但是这些空闲的块都不连续，导致任何一个单独的空闲的块都无法满足这个请求)。 为了解决该类问题，STL设计了==双层级配置器==，也就是第一级配置器和第二级配置器

• 第一级配置器 直接使用 malloc和free ；
• 第二级配置器则视情况采 用不同的策略：
• ①当配置区块 大于128bytes ，将其视作足够大，便 调用第一级配置器，使用malloc和free ；
• ②==当配置区块 小于128bytes ，将其视作过小，为降低额外负担，便采用 内存池 的管理方式==

解释 ：内存池的思想：一次向heap申请一块很大的内存( 内存池 )，如果申请小块内存的话就直接到内存池中去要。这样的话，就能够有效的解决上面所提到的问题。 注意 ：==如果用户申请的内存大小不是8的倍数，二级配置器会将申请的字节数上调至距离用户申请大小的最近的8的倍数处==。（这里带来了内部碎片问题，和之前谈到的外部碎片问题相比，这个问题我们无法避免） 问题： 内存块为什么必须要以8位单位呢，把1作为单位不就可以避免这个问题了吗？ ——我们的内存块是像链表一样连接起来的，这样就必然需要指针来维护， 32位平台下指针4字节，64位平台下指针8字节，所以内存块最小也要能存放一个指针吧，这样就清楚了为什么是8字节。 二级配置器是以内存池管理的，每次从系统中配置一大块内存，并维护与之对应的自由链表 free-list

• 如果用户申请内存，有相同大小的需要就直接从 free-lis t中分配。
• 如果用户归还内存时，将根据归还内存快的大小，将需要归还的内存插入到对应 free-list 的最顶端。

二级配置器的内存分配 1.free_list列表中有空余内存。如果申请3个字节的内存，则所需空间大小提升为8的倍数，然后去 free_list中查找相应的链表，如果 free_list[i] 不为空，则返回第一个元素，然后把头指针往后移。 ​ 2.free_list列表中没有空余，但内存池不为空。首先检验内存池中的大小是不是比申请的内存大，比如申请20 8的内存，如果足够，则分配相应内存，将* 其中一个分配给用户使用，其它的挂在相应的free_list 中 。如果内存池不够大，只够几个内存分配，则就分配这几个，把相应的数据返回。如果连一个都不够则执行第三中情况。

1. free_list列表中没有空余，内存池也不够。 调用malloc重新分配内存，分配时会多分配一倍的内存 ，把相应的内存挂到free_list下，剩余的放到内存池中。
2. free_list列表中没有空余，内存池也不够，malloc也失败 。则调用一级空间配置器，里面会有循环处理，或者抛出异常。