STL空间适配器

配置器

配置器

空间适配器的标准接口

代码片段1 代码片段2

内存分配释放与构造析构

为了精密分工，STL allocator决定将这两阶段操作区分开来。内存配置操作由alloc::allocate（）负责，内存释放操作由alloc::deallocate（）负责；对象构造操作由::construct（）负责，对象析构操作由::destroy（）负责。

构造和析构的基本工具：construct()和destroy()

首先析构分为有意义的析构函数操作和无意义的析构函数操作，有意义的就是类似释放堆内存操作，delete一个指针；无意义的就是一些栈内存的释放，因为系统会自动帮助我们进行释放，例如在类内声明的一个整型变量int a。

构造析构

destroy()有两个版本：

destroy()有两个版本，第一版本接受一个指针，准备将该指针所指之物析构掉。这很简单，直接调用该对象的析构函数即可。

第二版本接受first和last两个迭代器（所谓迭代器，第3章有详细介绍），准备将[first，last)范围内的所有对象析构掉。我们不知道这个范围有多大，万一很大，而每个对象的析构函数都无关痛痒（所谓trivial destructor)，那么一次次调用这些无关痛痒的析构函数，对效率是一种伤害。因此，这里首先利用value_type（）获得迭代器所指对象的型别，再利用_type_traits<T>判断该型别的析构函数是否无关痛痒。若是（true_type)，则什么也不做就结束；若否（false_type)，这才以循环方式巡访整个范围，并在循环中每经历一个对象就调用第一个版本的destroy(）。

空间配置与释放，std::alloc

对象构造前的空间配置和对象析构后的空间释放，由<stl_alloc.h>负责，SGI对此的设计哲学如下：

• 向system heap 要求空间。
• 考虑多线程（multi-threads)状态。
• 考虑内存不足时的应变措施。
• 考虑过多“小型区块”可能造成的内存碎片（fragment)问题。

C++的内存配置基本操作是：：operator new（），内存释放基本操作是：：operator delete()。这两个全局函数相当于C的malloc（）和free（）函数。是的，正是如此，SGI正是以malloc（）和free（）完成内存的配置与释放。

STL一级适配器和二级适配器

考虑到小型区块所可能造成的内存破碎问题，SGI 设计了双层级配置器，第一级适配器用 malloc(）和 free()，第二级配置器则视情况采用不同的策略：当配置区块超过 128 bytes 时，视之为 “足够大”，便调用第一级配置器；当配置区块小于 128 bytes 时，视之为 “过小”，为了降低额外负担，便采用复杂的内存池(memory pool)整理方式，而不再求助于第一级配置器。

一级适配器和二级适配器

包装接口和运用方式

包装和接口

一级适配器

第一级配置器以 malloc(), free(), realloc(）等 C 函数执行实际的内存配置、释放、重配置操作，并实现出类似 C++ new-handler7 的机制。

malloc(）和 realloc(）不成功后,改调用 oom_malloc() 和 oom_realloc()。
后两者都有内循环，不断调用 “内存不足处理例程”，期望在某次调用之后，获得足够的内存而圆满完成任务。但如果 “内存不足处理例程”并未被客端设定,oom_malloc(）和 oom_realloc() 便老实不客气地调用 __THROW_BAD_ALLOC,丢出 bad_alloc 异常信息，或利用 exit（1）硬生生中止程序。

相关代码：

一级适配器代码 一级适配器代码2

C++ new-handler的机制

所谓C++new handler机制是，你可以要求系统在内存配置需求无法被满足时，调用一个你所指定的函数。换句话说，一旦：：operator new无法完成任务，在丢出stdl：bad_aloc异常状态之前，会先调用由客端指定的处理例程。

相关信息：

注意，SGI以malloc而非：：operator new来配置内存（我所能够想象的一个原因是历史因素，另一个原因是C++并未提供相应于realloc（）的内存配置操作），因此，SGI不能直接使用C++的set_new_handler(），必须仿真一个类似的 set_malloc_handler(）。
请注意，SGI第一级配置器的allocate（）和realloc（）都是在调用ma11oc（）和rea1loc（）不成功后，改调用oom_malloc（）和oom_realloc(）。
后两者都有内循环，不断调用“内存不足处理例程”，期望在某次调用之后，获得足够的内存而圆满完成任务。但如果“内存不足处理例程”并未被客端设定，oom_malloc（）和oom_realloc（）便老实不客气地调用THROW_BAD_ALLOC，丢出bad alloc异常信息，或利用exit（1）硬生生中止程序。
记住，设计“内存不足处理例程”是客端的责任，设定“内存不足处理例程”
也是客端的责任。再一次提醒你，“内存不足处理例程”解决问题的做法有着特定的模式

内存不足处理例程是客端的责任！

适配器

二级适配器

请求内存的布局：(索求任何一块内存，都得有一些“税”要缴给系统)

请求布局

SGI 第二级配置器的做法是，如果区块够大，超过 128 bytes 时，就移交第一级配置器处理。当区块小于 128 bytes 时，则以内存池（memory pool）管理，此法又称为次层配置（sub-allocation）：每次配置一大块内存，并维护对应之自由链表（free-list）。下次若再有相同大小的内存需求，就直接从 free-lists 中拨出。如果客端释还小额区块，就由配置器回收到 free-lists 中——是的，别忘了，配置器除了负责配置，也负责回收。为了方便管理，SGI 第二级配置器会主动将任何小额区块的内存需求量上调至 8 的倍数（例如客端要求 30 bytes，就自动调整为 32 bytes），并维护 16 个 free-lists，各自管理大小分别为 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88,96,104,112,120,128 bytes 的小额区块。

但是，我们通常会想到，为了维护这个链表，每个节点都必须含有一个额外的指针，指向下一个节点，这显然会造成负担。所以我们使用union这个数据结构解决这个问题。free-lists 的节点结构如下：

union obj { 
    union obj * free_list_link;
    char client_data[1];
};

该结构中，从第一个字段来看，obj可以视为一个指针，指向相同形式的另一个obj；从第二个字段看，obj可以视为一个指针，指向实际区块。一物二用的结果是，不会为了维护链表所必须的指针而造成内存的另一种浪费。

下面是自由链表实现：

自由链表

空间配置函数allocate()

身为一个配置器，__default_alloc_template 拥有配置器的标准接口函数allocate()。此函数首先判断区块大小，大于128 bytes 就调用第一级配置器，小于 128 bytes 就检查对应的 free list。如果 free list 之内有可用的区块，就直接拿来用，如果没有可用区块，就将区块大小上调至 8 倍数边界，然后调用 refill（）,准备为free list重新填充空间。

填充空间的意思时从内存池中拿出一部分空间填充到空闲链表中去。

相关代码

如下图图示：

假如当前空闲链表没有指向空闲空间的时候，值为0，此时需要从内存池中分配内存去填充这个空闲链表；当空闲链表还有指向空闲空间的指针的时候，可以直接拿头节点的指针指向的空间来用就可以，最后记得更新空闲链表。

分配空闲空间

也就是说，当可以从空闲链表中找到可以分配的空间，就从空闲链表调出一个空间，如下图：

调出链表空闲节点

调出去之后后面的空闲节点向前移动：

更新链表

对应的空闲链表没有空闲分区的时候，就是下面这种情况

无空闲分区

空间释放函数 deallocate(）

身为一个配置器，_default_alloc_template拥有配置器标准接口函数deallocate()。该函数首先判断区块大小，大于128bytes就调用第一级配置器，小于128bytes就找出对应的free list，将区块回收。

相关代码如下：

空间释放代码片段

回收区块的时候直接将这个区块的指针插入到对应节点的第一个空闲指针即可：

回收分区

也即：

回收分区

重新填充free lists

当申请空间的时候发现对应的链表没有空闲分区的时候，也就是下面这种情况

无空闲分区

我们就需要调用 refill（)，准备为 free list 重新填充空间。新的空间将取自内存池（经由chunk_alloc() 完成）。

<font color = 'pink'>缺省取得20 个新节点（新区块），但万一内存池空间不足，获得的节点数（区块数）可能小于20。</font>

总的来说：

1. 向内存池申请空间的起始地址
2. 如果只申请到一个对象的大小, 就直接返回一个内存的大小, 如果有更多的内存, 就继续执行
3. 从第二个块内存开始, 把从内存池里面分配的内存用链表给串起来, 并返回一个块内存的地址给用户

refill相关代码 如下(假设 n 已经适当上调至 8 的倍数):

// 内存填充
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n)
{
    int nobjs = 20;
    char * chunk = chunk_alloc(n, nobjs);             // 向内存池申请空间的起始地址
    obj * __VOLATILE * my_free_list;
    obj * result;
    obj * current_obj, * next_obj;
    int i;

    // 如果只申请到一个对象的大小, 就直接返回一个内存的大小
    if (1 == nobjs) return(chunk);
    my_free_list = free_list + FREELIST_INDEX(n);

    // 申请的大小不只一个对象的大小的时候
    result = (obj *)chunk;
    // my_free_list指向内存池返回的地址的下一个对齐后的地址
    *my_free_list = next_obj = (obj *)(chunk + n);
    // 这里从第二个开始的原因主要是第一块地址返回给了用户, 现在需要把从内存池里面分配的内存用链表给串起来
    for (i = 1; ; i++) 
    {
        current_obj = next_obj;
        next_obj = (obj *)((char *)next_obj + n);
        if (nobjs - 1 == i) 
        {
            current_obj -> free_list_link = 0;
            break;
        } 
        else 
        {
            current_obj -> free_list_link = next_obj;
        }
        }
    return(result);
}

内存池（memory pool）

从内存池中取空间给 freelist 使用，是 chunk_alloc(）的工作，其主要做了下面的工作：

1. 内存池的大小大于需要的空间, 直接返回起始地址(nobjs默认设置为20, 所以每次调用都会给链表额外的19个内存块)
2. 内存池的内存不足以马上分配那么多内存, 但是还能满足分配一个即以上的大小, 那就全部分配出去
3. 如果一个对象的大小都已经提供不了了, 先将零碎的内存块给一个小内存的链表来保存, 然后就准备调用malloc申请40块+额外大小的内存块(额外内存块就由heap_size决定), 如果申请失败跳转到步骤4, 成功跳转到步骤6
4. 充分利用更大内存的链表, 通过递归来调用他们的内存块
5. 如果还是没有内存块, 直接调用一级配置器来申请内存, 还是失败就抛出异常, 成功申请就继续执行
6. 重新修改内存起始地址和结束地址为当前申请的地址块, 重新调用chunk_alloc分配内存

内存池的代码如下：

<font color = 'pink'>注意，下面代码函数参数nobjs传的是引用</font>

// 内存池
template <bool threads, int inst>
char* __default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs)
{
    char * result;
    size_t total_bytes = size * nobjs;            // 链表需要申请的内存大小
    size_t bytes_left = end_free - start_free;    // 内存池里面总共还有多少内存空间

      // 内存池的大小大于需要的空间, 直接返回起始地址
    if (bytes_left >= total_bytes) 
    {
        result = start_free;
        start_free += total_bytes;  // 内存池的首地址往后移
        return(result);
    }
    // 内存池的内存不足以马上分配那么多内存, 但是还能满足分配一个即以上的大小, 那就按对齐方式全部分配出去
    else if (bytes_left >= size) 
    {
        nobjs = bytes_left/size;
        total_bytes = size * nobjs;
        result = start_free;
        start_free += total_bytes;  // 内存池的首地址往后移
        return(result);
    } 
    else 
    { 
        // 如果一个对象的大小都已经提供不了了, 那就准备调用malloc申请两倍+额外大小的内存
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        // Try to make use of the left-over piece.
        // 内存池还剩下的零头内存分给给其他能利用的链表, 也就是绝不浪费一点.
        if (bytes_left > 0) 
        {
            // 链表指向申请内存的地址
            obj * __VOLATILE * my_free_list = free_list + FREELIST_INDEX(bytes_left);
            ((obj *)start_free) -> free_list_link = *my_free_list;
            *my_free_list = (obj *)start_free;
        }
        start_free = (char *)malloc(bytes_to_get);
        // 内存不足了
        if (0 == start_free) 
        {
            int i;
            obj * __VOLATILE * my_free_list, *p;
            // 充分利用剩余链表的内存, 通过递归来申请
            for (i = size; i <= __MAX_BYTES; i += __ALIGN) 
            {   
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if (0 != p) 
                {
                    *my_free_list = p -> free_list_link;
                    start_free = (char *)p;
                    end_free = start_free + i;
                    return(chunk_alloc(size, nobjs));
                }
            }
            // 如果一点内存都没有了的话, 就只有调用一级配置器来申请内存了, 并且用户没有设置处理例程就抛出异常
            end_free = 0;   // In case of exception.
            start_free = (char *)malloc_alloc::allocate(bytes_to_get);
        }
            // 申请内存成功后重新修改内存起始地址和结束地址, 重新调用chunk_alloc分配内存，此时内存池已有空间分配
            heap_size += bytes_to_get;
            end_free = start_free + bytes_to_get;
            return(chunk_alloc(size, nobjs));
    }   
}

上述的 chunk_alloc(）函数以 end_free - start_free 来判断内存池的水量。如果水量充足，就直接调出 20 个区块返回给 free list。如果水量不足以提供 20个区块，但还足够供应一个以上的区块，就拨出这不足 20 个区块的空间出去。这时候其 pass by reference 的 nobjs 参数将被修改为实际能够供应的区块数。如果内存池连一个区块空间都无法供应,对客端显然无法交待,此时便需利用 malloc(）从 heap 中配置内存，为内存池注人活水源头以应付需求。新水量的大小为需求量的两倍，再加上一个随着配置次数增加而愈来愈大的附加量。

内存池实际操练结果：

内存池操作

内存基本处理工具

前两个函数是用于构造的construct（）和用于析构的destroy（），另三个函数是 uninitialized_copy(),uninitialized_fi11(),uninitialized_fil1_n()10, 分别对应于高层次函数copy（）、fi11（）、fi11_n(）——这些都是STL算法。

uninitialized_copy函数

功能 : 从first到last范围内的元素复制到从 result地址开始的内存.

template <class InputIterator, class ForwardIterator>
inline ForwardIterator uninitialized_copy(InputIterator first, InputIterator last,
                     ForwardIterator result) {
  return __uninitialized_copy(first, last, result, value_type(result));
}

uninitialized_copy()使我们能够将内存的配置与对象的构造行为分离开来。如果作为输出目的地的[result，result+(last-first))范围内的每一个迭代器都指向未初始化区域，则uninitializead_copy（）会使用copy constructor，给身为输入来源之[first，last)范围内的每一个对象产生一份复制品，放进输出范围中。换句话说，针对输入范围内的每一个迭代器i，该函数会调用construct(&*(result+(i-first)),*i),产生*i的复制品，放置于输出范围的相对位置上。

如果你需要实现一个容器，uninitialized_copy（）这样的函数会为你带来很大的帮助，因为容器的全区间构造函数（range constructor)通常以两个步骤完成：

• 配置内存区块，足以包含范围内的所有元素。
• 使用uninitialized_copy（)，在该内存区块上构造元素。

C++标准规格书要求uninitialized_copy（）具有“commit or rollback”语意，意思是要么“构造出所有必要元素”，要么（当有任何一个copy constructor失败时)“不构造任何东西”。

其中__uninitialized_copy函数代码如下：

template <class InputIterator, class ForwardIterator, class T>
inline ForwardIterator __uninitialized_copy(InputIterator first, InputIterator last,
                     ForwardIterator result, T*) {
  typedef typename __type_traits<T>::is_POD_type is_POD;
  return __uninitialized_copy_aux(first, last, result, is_POD());
}

__uninitialized_copy使用了typename进行萃取, 并且萃取的类型是POD.

优化处理

POD意指Plain Old Data，也就是标量型别（scalar types)或传统的Cstruct型别。POD型别必然拥有trivial ctor/dtor/copy/assignment函数，因此，我们可以对POD型别采用最有效率的复制手法，而对non-POD型别采取最保险安全的做法：

1. __uninitialized_copy_aux优化处理

   // 如果是POD类型
   template <class InputIterator, class ForwardIterator> 
   inline ForwardIterator __uninitialized_copy_aux(InputIterator first, InputIterator last,
                            ForwardIterator result,
                            __true_type) {
     return copy(first, last, result);
   }
   
   // 如果不是POD类型
   template <class InputIterator, class ForwardIterator>
   ForwardIterator __uninitialized_copy_aux(InputIterator first, InputIterator last,
                            ForwardIterator result,
                            __false_type) {
     ForwardIterator cur = result;
     __STL_TRY {
       for ( ; first != last; ++first, ++cur)
         construct(&*cur, *first);
       return cur;
     }
     __STL_UNWIND(destroy(result, cur));
   }
   

   __uninitialized_copy针对普通类型(int, double)做了特殊的优化, 以执行更高效的处理, 对类和用户定义类型做了构造处理, 当然用户自定义的不一定是类, 但是编译器为了安全性依然会执行最慢处理.

2. uninitialized_copy_n函数

   uninitialized_copy_n也做了跟uninitialized_copy类似的处理, 只是它是采用tratis编程里iterator_category迭代器的类型来选择最优的处理函数.

   template <class InputIterator, class Size, class ForwardIterator>
   inline pair<InputIterator, ForwardIterator>
   uninitialized_copy_n(InputIterator first, Size count,
                        ForwardIterator result) {
     return __uninitialized_copy_n(first, count, result, iterator_category(first)); // 根据iterator_category选择最优函数
   }
   
   template <class InputIterator, class Size, class ForwardIterator>
   pair<InputIterator, ForwardIterator>
   __uninitialized_copy_n(InputIterator first, Size count, ForwardIterator result,
                          input_iterator_tag) // input_iterator_tag类型的迭代器
   {
     ForwardIterator cur = result;
     __STL_TRY {
       for ( ; count > 0 ; --count, ++first, ++cur) 
         construct(&*cur, *first);
       return pair<InputIterator, ForwardIterator>(first, cur);
     }
     __STL_UNWIND(destroy(result, cur));
   }
   
   template <class RandomAccessIterator, class Size, class ForwardIterator>
   inline pair<RandomAccessIterator, ForwardIterator>
   __uninitialized_copy_n(RandomAccessIterator first, Size count, ForwardIterator result,
                          random_access_iterator_tag) // random_access_iterator_tag类型的迭代器
   {
     RandomAccessIterator last = first + count;
     return make_pair(last, uninitialized_copy(first, last, result));
   }
   

uninitialized_copy类似于第一篇分析空间配置器的destory针对const char*和const wchar*单独做了特例化.

inline char* uninitialized_copy(const char* first, const char* last,
                                char* result) {
  memmove(result, first, last - first);
  return result + (last - first);
}

inline wchar_t* uninitialized_copy(const wchar_t* first, const wchar_t* last,
                                   wchar_t* result) {
  memmove(result, first, sizeof(wchar_t) * (last - first));
  return result + (last - first);
}

直接调用c++的memmove操作, 毕竟这样的效率更加的高效.

uninitialized_fill函数

功能 : 从first到last范围内的都填充为 x 的值.

uninitialized_fill采用了与uninitialized_copy一样的处理方法选择最优处理函数,

函数声明：

template <class ForwardIterator, class T>
void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x);

uninitialized_fill()也能够使我们将内存配置与对象的构造行为分离开来。如果[first，last）范围内的每个迭代器都指向未初始化的内存，那么uninitialized_fill()会在该范围内产生x（上式第三参数）的复制品。换句话说，uninitialized_fill（）会针对操作范围内的每个迭代器i，调用construct(&*i，x），在i所指之处产生x的复制品。

与uninitialized_copy（）一样，uninitialized_fill（）必须具备“commitor rollback”语意，换句话说，它要么产生出所有必要元素，要么不产生任何元素。
如果有任何一个copy constructor 丢出异常(exception)，uninitialized_fill（），必须能够将已产生的所有元素析构掉。

相关代码如下：

// 函数封装
template <class ForwardIterator, class T>
inline void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x) 
{
  __uninitialized_fill(first, last, x, value_type(first));
}

// 类型萃取并且调用重载函数
template <class ForwardIterator, class T, class T1>
inline void __uninitialized_fill(ForwardIterator first, ForwardIterator last,  const T& x, T1*)
{
  typedef typename __type_traits<T1>::is_POD_type is_POD;
  __uninitialized_fill_aux(first, last, x, is_POD());
                   
}

// 是POD类型
template <class ForwardIterator, class T>
inline void
__uninitialized_fill_aux(ForwardIterator first, ForwardIterator last,  const T& x, __true_type)
{
   fill(first, last, x);    // 调用STL算法fill()
}

// 不是POD类型
template <class ForwardIterator, class T>
void
__uninitialized_fill_aux(ForwardIterator first, ForwardIterator last, const T& x, __false_type)
{
  ForwardIterator cur = first;
  __STL_TRY {
    for ( ; cur != last; ++cur)
      construct(&*cur, x);  // 必须一个一个元素地构造，无法批量进行
  }
  __STL_UNWIND(destroy(first, cur));
}

uninitialized_fill_n函数

功能 : 从first开始n 个元素填充成 x 值.

相关代码：

// 函数封装
template <class ForwardIterator, class Size, class T>
inline ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n, const T& x) 
{
  return __uninitialized_fill_n(first, n, x, value_type(first));
}

// 萃取并且调用重载函数
template <class ForwardIterator, class Size, class T, class T1>
inline ForwardIterator __uninitialized_fill_n(ForwardIterator first, Size n, const T& x, T1*) 
{
  typedef typename __type_traits<T1>::is_POD_type is_POD;
  return __uninitialized_fill_n_aux(first, n, x, is_POD());                                
}

// 假如是POD类型
template <class ForwardIterator, class Size, class T>
inline ForwardIterator __uninitialized_fill_n_aux(ForwardIterator first, Size n, const T& x, __true_type) 
{
  return fill_n(first, n, x);   // 交由高阶函数执行
}

// 不是POD类型
template <class ForwardIterator, class Size, class T>
ForwardIterator __uninitialized_fill_n_aux(ForwardIterator first, Size n, const T& x, __false_type) 
{
    ForwardIterator cur = first;
    __STL_TRY 
    {
        for ( ; n > 0; --n, ++cur)
            construct(&*cur, x);    // 必须一个一个调用拷贝构造函数
        return cur;
    }
    __STL_UNWIND(destroy(first, cur));
}

三个函数效率的特殊考虑可以总结为下图：

函数效率优化

---

参考地址：

1. STL源码分析目录
2. 《STL源码分析》- 侯捷