bitmap_allocator 是 GNU 中另一种常用的 allocator。它不像 pool_allocator 支持复数个的元素申请，只能一个一个申请，由于是应用在容器中，所以也无所谓。

如上图，一次只能分配回收一个object。

bitmap allocator 结构

• bitmap_allocator 内部自己实现了一个 vector 作用的结构 __mini_vector ，和 普通的 vector 一样 会 两倍成长。这其中 _M_start 和 _M_finish 、_M_end_of_storage 都是和 vector 保持一致。
• __mini_vector 用于存放 _block_pair ，即上图的 Entries，它内部有两个指针，记录一个 Super Blocks 的头和最后一个元素。
• 一个 Super Blocks 包含一个 int 记录该 int 之后的区块长度（即该 Super Blocks 的大小），一个 int 用于记录当前已经分配出去的块数量，然后是一个 bitmap 数组 （uint），长度根据 blocks 的数量决定（64 个 Blocks 需要 64 位也就是两个 uint 记录），最后是个 blocks 的区块内容。一开始第一个 Super Blocks 的 Blocks 数量是64个，然后成倍增长。
• bitmap_allocator 内还有一个 _S_free_list ，实际也是一个 vector，用于记录需要全回收的 Super Blocks。最大长度是 64。

分配

bitmap 记录的方向如下所示

Super Blocks Size     记录已使用的块数    位图数组 记录某块是否被使用        64个Blocks 被 mini vector 所管理
[ Super Blocks Size  |  Use Counts  |  bitmap[1]  |  bitmap[0]  |  [1][][][][][][]...[][][][][][][][][]  |]
                                                           1110 
                                               <-bitmap 记录的方向     Super Blocks 使用的方向->

bitmap 中的位，1 表示空闲，0表示分配出去，记录的方向与 Blocks 的使用方向相反。

假设第一个都分配出去了，__mini_vector 为 1，这时候 __mini_vector 就会两倍增长，新创建的 Super Blocks 就会包含 64 * 2 = 128 个 Blocks，其记录 size 为 4 + 4 * 4 + 128 * 8 = 1044。

后续如果一直都是新创建，则一直会两倍增长，只有当发生第一个全回收（无需立马归还 OS）的时候，下次分配的规模才会减半。

如果 前面一个 Super Block 本来没有区块可以分配， 现在回收到了区块， 此时又请求了新的区块的话， 会从后面一个 Super Block 去分配，而非当前 Super Block。 但是如果 后面一个 Super Block 不存在的话， 则从 前面一个 Super Block 取。

当 __mini_vector 中没有任何一个 Super Blocks 时，会从 _S_free_list 中取一个，重新放回 __mini_vector ，再次执行分配流程。