从vector扩容看STL空间分配器的本质

熟悉STL的同学始终都绕不过的一个地方，尤其是面试时也会被问及容器的知识点：vector。

1 vector

vector是一个序列型的容器数据元素是连续存储，支持随机访问。向vector插入一个新元素时，如果vector当前的空间已经满了，没有额外的空间存储新元素vector会申请一块更大的空间，然后把vector元素拷贝到新的空间，在插入新的元素。可想而知，如果是实际生产中频繁这样操作性能损耗会很大。导致的后果将是拖累程序处理效率，业务处理卡死。

vector空间分配在linux和windows操作系统中分配策略是不一样的，下面的代码将对这两种操作系统上的分配策略进行验证：

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> vInt(2); 
  cout << "size = " << vInt.size() << ",capacity = " << vInt.capacity() << endl;
  for (int a = 1; a <= 12; a++)
  {
    vInt.push_back(a);
    cout << "size = " << vInt.size() << ",capacity = " << vInt.capacity() << endl;
  }
    return 0;
}

代码的逻辑是开始得到时候定义一个vector后面通过向容器中插入元素观察内存空间分配情况。

代码在windows和linux结果如下：

图1 windows和linux对比图

如上，左图是windows上运行结果，右图为linux运行结果，vector每次进行空间扩展时，windows是按照临界值的1.5倍左右进行，linux是按照2的倍数进行扩展。具体是按照什么规则进行扩展，并不是统一的，需要根据空间扩展策略或者版本等进行确定。

2 空间分配器

容器进行内存扩展时，需要使用空间分配器。STL空间分配器是是怎么工作的呢？

在C++中，内存空间的分配和释放可以通过malloc、free、new和delete进行操作，STL在设计空间分配器的时候也是使用了这些但是设计的时候又兼顾了线程安全、内存碎片等，STL空间分配器的设计哲学如下：

• 从system的heap申请空间
• 兼容多线程
• 内存不足时处理措施
• 小内存片过多处理措施

实际上在我们使用容器时容器动态扩展时这些问题都会遇到。STL为了解决这些问题采取了双层级配置器就是处理，第一级主要针对内存块大于128个字节的情况，如果满足就直接采用第一级配置器，第二级主要针对内存块小于128个字节的情况。这两种情况STL采取了两种不同的方式进行处理。

2.1 第一级配置器

第一级配置器主要是使用C函数的形式对空间进行创建、释放以及重新配置。使用的方法主要是malloc()、free()、realloc()。并没有像大家理解的那样使用C++的机制实现。原因主要有两点：

• 当new无法申请足够的空间抛出异常前需要先调用异常处理函数，这种处理的机制也叫做new-handle机制，但内存不足的异常处理通常被认为是客户端需要处理的。
• C++没有提供相应的realloc()方法，因此SGI不能直接只用C++的set_new_handler()。

第一级配置器相关实现代码如下：

// 一级配置器
template <int inst>
class __malloc_alloc_template 
{
  // 这里private里面的函数都是在内存不足的时候进行调用的
  private:   
    static void *oom_malloc(size_t);        // 分配不足
    static void *oom_realloc(void *, size_t);   // 重新分配不足
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
    static void (* __malloc_alloc_oom_handler)();   // 内存不足设置的处理例程, 默认设置的是0, 表示没有设置处理例程, 这个处理例程是由用户手动设置的
#endif
  public:
    static void * allocate(size_t n){
    // 第一级配置器直接使用 malloc()
      void *result = malloc(n); 
      // 以下，无法满足需求时，改用 oom_malloc()
      if (0 == result) result = oom_malloc(n);
      return result;
    }
    static void deallocate(void *p, size_t /* n */){
     // 第一级配置器直接使用 free()
    free(p);
    }
    static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz){
      // 第一级配置器直接使用 realloc()
      void * result = realloc(p, new_sz); 
      // 以下，无法满足需求时，改用 oom_realloc()
      if (0 == result) result = oom_realloc(p, new_sz);
      return result;
    }
};

从源码可以看出，除了实现时使用了C语言的函数外，在空间分配不足时还是用了下面两个函数：

static void *oom_malloc(size_t);        // 分配不足
static void *oom_realloc(void *, size_t);   // 重新分配不足

这两个函数在内存不足时会持续进行申请，直到某一次申请成功可以进行正确出处理，但是如果客户端没有正常的处理这种异常，它们也会抛出bad_alloc异常或者使用exit使进程退出。

2.2 第二级配置器

在实际处理时需要开辟额外的空间对小内存块进行管理，因此在满足功能的同时浪费一些额外的空间也在所难免，必将如果不对小内存块进行管理，损失的将会更大。

SGI二级配置器主要的功能是：如果空间大于128个字节就移交给一级配置器进行处理，如果空间小于128个字节则使用内存池(memory pool)的方式进行管理。这种处理方法也叫做次层配置。

次层配置的处理方法为：在内部维护一个链表（free-list），如果有配置器对释放或者分配空间时由链表进行维护空间的状态，当有需要分配空间且大小和链表中维护的块相等时则直接从链表中进行返回。如果块大小不合适时，SGI也会自动将块大小扩展为2的次方继续分配。如：申请一个56字节的空间，如果没有SGI会为其匹配64字节的。设计时，链表的节点结构如下：

union obj{
  union obj* free_list_link;
  char client data[1];
}

free-list的链表结构如下图所示：

图2 图片来源于网络

从面的图中可以看出，SGI维护了一个16个节点的freelist，每个节点又指向了一个小空间块，在使用二级配置器进行分配空间时就根据链表进行获取。还有一点要注意的是在链表节点内部都维护了一个节点指针，这个指针只有在链表中才会有具体的使用和指向，一旦脱离链表指针就不会再使用，也不会造成空间的浪费。

- EOF -