为什么要使用空间适配器

要知道为什么要使用空间适配器，我们先看一下下面这段代码

#include 
   
    using namespace std;template
    
     class Vector{
   public:	// 按指定size进行构造，size个空间，没有元素	Vector(int size = 0):mSize(size),mCur(0)	{
   		if(size != 0)		{
   			mpVec = new T[size];		}	}	~Vector()	{
   		delete []mpVec;	}	// 按指定size进行构造,添加size个元素，元素值是val	Vector(int size, const T &val = T()):mSize(size),mCur(size)	{
   		mpVec = new T[size];		for(int i = 0; i < size; i++)		{
   			mpVec[i] = val;		}	}	// 按[first, last)区间的元素来构造Vector	Vector(T *first, T *last)	{
   		mCur = 0;		mpVec = new T[last-first];		mSize = last-first;		T *p = first;		for(; p != last; p++)		{
   			mpVec[mCur++] = *p;		}	}	// 从末尾添加元素	void push_back(const T &val)	{
   		if(full())		{
   			resize();		}		mpVec[mCur++] = val;	}	// 从末尾删除元素	void pop_back()	{
   		if(empty())		{
   			return ;		}		--mCur;	}	bool full()const	{
   		return mCur == mSize;	}	bool empty()const	{
   		return mCur == 0;	}	// 返回容器元素的个数	int size()const	{
   		return mCur;	}	// Vector的迭代器	class iterator	{
   	public:		iterator(T *p):_iter(p){
   }		bool operator != (const iterator &val)		{
   			return _iter != val._iter;		}		T& operator *()		{
   			return *_iter;		}		void operator++ ()		{
   			++_iter;		}	private:		T *_iter;	};	iterator begin()	{
   		return iterator(mpVec);	}	iterator end()	{
   		return iterator(mpVec+mCur);	}	private:	T *mpVec;	int mCur;	int mSize;	// 容器内存2倍扩容	void resize()	{
   		if(mSize != 0)		{
   			T *newdata = new T[mSize*2];			for(int i = 0; i < mCur; i++)			{
   				newdata[i] = mpVec[i];			}			delete []mpVec;			mpVec = newdata;			mSize *= 2;		}		else		{
   			mpVec = new T[1];			mSize = 1;		}	}};

这里我们实现了一个简单的vector 类，假如我们需要一个长度为1000的A类型的数组，用该容器申请一块sizeof(A)*1000的内存块，并且调用1000次A的构造函数，有时候我们开辟一块内存并不希望调用对象的构造函数。这时候我们可以把内存的开辟与对象的构造分开，对象的析构与内存的释放分开，使得在一定程度上使容器更加高效。

所以可以将空间适配器实现为这样

template
   
    class Allocator{
   public:	T* allocate(size_t size) // 开辟内存	{
   		return (T*)malloc(size);	}	void deallocate(void *ptr) // 释放内存	{
   		free(ptr);	}	void construct(T *ptr, const T &val) // 构造对象	{
   		new (ptr) T(val);	}	void destroy(T *ptr) // 析构对象	{
   		ptr->~T();	}};

这样内存的开辟与对象的构造分开，内存的释放与析构函数分开，一级的空间适配器只是简单地将malloc 与free 封装了一下，

二级空间适配器

二级空间适配器用来管理stl容器对内存的申请与释放

如果用户申请的内存大于128字节，直接调用一级适配器给用户分配内存，如果小于128字节，先遍历free-list 链表，二级空间适配器维护着一个free-list 的结构，该结构如下图所示，适配器按8字节对齐，将内存块的大小按8字节为单位分成一些固定大小的块，8字节大小的在第一个链表中，16字节在第二个链表中… 一次类推，知道128字节为止。

在这里插入图片描述

如果用户申请的内存字节数不是8的倍数，则按能够满足用户需求的最小的内存块进行分配，例如，用户要10字节的内存，直接分配给用户16字节

以 24 字节为例

如果用户索要一块24字节的内存，free-list中24字节的内存块分配完了，这时候，free-list 会向内存池中申请大小为24字节的内存块，如果内存池中有内存能够满足，则除了给用户分配一个24字节的内存块之外，还会给free-list中链接一部分24字节的内存块以供用户的使用。

如果内存池中的内存大小不能满足用户的申请，则内存池将自身剩余的内存挂入free-list的相应位置，然后向系统申请一块内存。申请成功，则分配给用户和free-list ,若失败，则遍历free-list 大于24字节的部分，找到一块分配给用户，并将剩余内存挂入相应free-list 的位置。

如果没找到则调用一级适配器。

源码分析

allocate

从源码中我们可以看出

static void* allocate(size_t __n)  {
       void* __ret = 0;	/* 如果申请的内存大小大于 _MAX_BYTES 直接调用一级适配器*/    if (__n > (size_t) _MAX_BYTES) {
         __ret = malloc_alloc::allocate(__n);    }    else {
   		/* 计算__n大小的内存块所在的free-list 的位置 */      _Obj* __STL_VOLATILE* __my_free_list          = _S_free_list + _S_freelist_index(__n);      // Acquire the lock here with a constructor call.      // This ensures that it is released in exit or during stack      // unwinding.#     ifndef _NOTHREADS      /*REFERENCED*/      _Lock __lock_instance;#     endif      _Obj* __RESTRICT __result = *__my_free_list;		/* 如果当前free-list中没有相应的内存块 就从内存池申请一块内存，		返回一块大小为__n的内存块     */      if (__result == 0)        __ret = _S_refill(_S_round_up(__n));      else {
   	  	/*否则直接返回一个内存块 */        *__my_free_list = __result -> _M_free_list_link;        __ret = __result;      }    }    return __ret;  };

_S_refill

template 
   
    void*__default_alloc_template<__threads, __inst>::_S_refill(size_t __n){
       int __nobjs = 20;	/* 从内存池请求一大块内存放入free-list中 */    char* __chunk = _S_chunk_alloc(__n, __nobjs);    _Obj* __STL_VOLATILE* __my_free_list;    _Obj* __result;    _Obj* __current_obj;    _Obj* __next_obj;    int __i;	/* 如果只返回了一个内存块 直接返回*/    if (1 == __nobjs) return(__chunk);	    __my_free_list = _S_free_list + _S_freelist_index(__n);    /* Build free list in chunk */      __result = (_Obj*)__chunk;	/* __my_free_list 指向 __chunk 位置开始向后的 __n个字节处  */      *__my_free_list = __next_obj = (_Obj*)(__chunk + __n); 	/* 如果__nobjs 的值大于 1 的情况*/      for (__i = 1; ; __i++) {
           __current_obj = __next_obj;		/* __next_obj 指向下一个内存块 */        __next_obj = (_Obj*)((char*)__next_obj + __n);        if (__nobjs - 1 == __i) {
   			/* 如果当前内存块时最后一个内存块，就将链接地址置为 0 */            __current_obj -> _M_free_list_link = 0;            break;        } else {
   			/* 将当前内存块与后继的内存块建立链接 */            __current_obj -> _M_free_list_link = __next_obj;        }      }    return(__result);}

_S_chunk_alloc

template 
   
    char*__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size,                                                             int& __nobjs){
       char* __result;	/* 计算所需要的字节数 */    size_t __total_bytes = __size * __nobjs;	/* 计算当前内存池的剩余的字节数 */    size_t __bytes_left = _S_end_free - _S_start_free;	/* 如果剩余字节数大于所需要的字节数 就直接切割处__total_bytes个字节*/    if (__bytes_left >= __total_bytes) {
           __result = _S_start_free;		/* 内存池的首地址指向切割后的位置 */        _S_start_free += __total_bytes;        return(__result);		/* 如果剩余字节数小于所需要的字节数 但是大于一个内存块的大小 ，就尽可能		多的切割处__size 大小的内存块 */    } else if (__bytes_left >= __size) {
       	/* 计算出最多能分配多少个大小为 __size 的内存块*/        __nobjs = (int)(__bytes_left/__size);		/* 计算出实际分配的内存大小 */        __total_bytes = __size * __nobjs;        __result = _S_start_free;        _S_start_free += __total_bytes;        return(__result);		/*如果剩余的内存不够一个大小为 __size 的内存块*/    } else {
       	/* 计算出向系统申请的内存资源的大小 */        size_t __bytes_to_get = 	  2 * __total_bytes + _S_round_up(_S_heap_size >> 4);        // Try to make use of the left-over piece.        /* 如果内存池中有剩余的内存 */        if (__bytes_left > 0) {
   			/* 根据剩余内存的大小计算出该放到free-list的哪个位置 */            _Obj* __STL_VOLATILE* __my_free_list =                        _S_free_list + _S_freelist_index(__bytes_left);			/* 将内存池中剩余的内存放到free-list 的相应的位置*/            ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;            *__my_free_list = (_Obj*)_S_start_free;        }		/* 重新开辟一块内存 */        _S_start_free = (char*)malloc(__bytes_to_get);		/* 如果内存开辟失败 */        if (0 == _S_start_free) {
               size_t __i;            _Obj* __STL_VOLATILE* __my_free_list;	    _Obj* __p;            // Try to make do with what we have.  That can't            // hurt.  We do not try smaller requests, since that tends            // to result in disaster on multi-process machines.            /* 遍历从free-list 中较大的内存块中取出一块进行分配 */            for (__i = __size;                 __i <= (size_t) _MAX_BYTES;                 __i += (size_t) _ALIGN) {
                   __my_free_list = _S_free_list + _S_freelist_index(__i);                __p = *__my_free_list;                if (0 != __p) {
   					/* 找到一块大于 __size 的内存块 __my_free_list 指向找到的这个内存块*/                    *__my_free_list = __p -> _M_free_list_link;					/* 内存池的首地址指向这个内存块 */                    _S_start_free = (char*)__p;					/* 内存池的尾地址指向这个内存块的结束位置 */                    _S_end_free = _S_start_free + __i;					/* 递归调用，重新分配*/                    return(_S_chunk_alloc(__size, __nobjs));                    // Any leftover piece will eventually make it to the                    // right free list.                }            }			/* 如果free-list中找不到比__size 大的内存块 */	    _S_end_free = 0;	// In case of exception.	    	/* 一级空间适配器分配内存 */            _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);            // This should either throw an            // exception or remedy the situation.  Thus we assume it            // succeeded.        }        _S_heap_size += __bytes_to_get;		/* 内存池的尾指针指向新开辟内存的结尾 */        _S_end_free = _S_start_free + __bytes_to_get;        return(_S_chunk_alloc(__size, __nobjs));    }}

deallocate

static void deallocate(void* __p, size_t __n)  {
     	/*如果申请的内存大小大于 _MAX_BYTES 就世界调用一级适配器的释放函数 */    if (__n > (size_t) _MAX_BYTES)      malloc_alloc::deallocate(__p, __n);    else {
   		/* 如果小于 _MAX_BYTES 则回收到free-list 的 计算出在自由链表中的位置 */      _Obj* __STL_VOLATILE*  __my_free_list          = _S_free_list + _S_freelist_index(__n);		/*__q 指向了需要回收的内存块 */      _Obj* __q = (_Obj*)__p;      // acquire lock#       ifndef _NOTHREADS      /*REFERENCED*/      _Lock __lock_instance;#       endif /* _NOTHREADS */		/*类似于链表中的头插法，将需要回收的资源放入链表中*/      __q -> _M_free_list_link = *__my_free_list;      *__my_free_list = __q;      // lock is released here    }  }

转载地址：http://ttnwi.baihongyu.com/

你可能感兴趣的文章

SQLite Tutorial 4 : How to export SQLite file into CSV or Excel file