STL简介
STL（Standard Template Library，标准模板库），从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其他一些组件的集合。
谈及组件，那么我们就首先来简单谈下STL六大组件，其相关的设计模式使用，以及各组件之间的协作关系。
设计模式一览
六大组件简单介绍
1. 空间配置器：内存池实现小块内存分配,对应到设计模式--单例模式（工具类，提供服务，一个程序只需要一个空间配置器即可），享元模式（小块内存统一由内存池进行管理）
2.迭代器：迭代器模式，模板方法
3.容器：STL的核心之一，其他组件围绕容器进行工作：迭代器提供访问方式，空间配置器提供容器内存分配，算法对容器中数据进行处理，仿函数伪算法提供具体的策略，类型萃取 实现对自定义类型内部类型提取。保证算法覆盖性。其中涉及到的设计模式：组合模式（树形结构），门面模式（外部接口提供），适配器模式（stack，queue通过deque适配得 到），建造者模式（不同类型树的建立过程）。
4.类型萃取：基于范型编程的内部类型解析，通过typename获取。可以获取迭代器内部类型value_type,Poter,Reference等。
5.仿函数：一种类似于函数指针的可回调机制，用于算法中的决策处理。涉及：策略模式，模板方法。
6适配器：STL中的stack，queue通过双端队列deque适配实现，map，set通过RB-Tree适配实现。涉及适配器模式。
关于六大组件之间的具体关系如图简单描述
ps（图技术比较水，见谅，如有bug，请指正）
貌似扯的多了，来谈谈主题《空间配置器》问题吧。
STL空间配置器产生的缘由：
在软件开发，程序设计中，我们不免因为程序需求，使用很多的小块内存（基本类型以及小内存的自定义类型）。在程序中动态申请，释放。
这个过程过程并不是一定能够控制好的，于是乎，
问题1：就出现了内存碎片问题。（ps外碎片问题）
问题2：一直在因为小块内存而进行内存申请，调用malloc，系统调用产生性能问题。
注：内碎片：因为内存对齐/访问效率（CPU取址次数）而产生 如 用户需要3字节，实际得到4或者8字节的问题，其中的碎片是浪费掉的。
外碎片：系统中内存总量足够，但是不连续，所以无法分配给用户使用而产生的浪费。下边简单图解
这两个问题解释清楚之后，就来谈STL空间配置器的实现细节了
实现策略
用户申请空间大于128？
yes：调用一级空间配置器
no：调用二级空间配置器
大致实现为：
二级空间配置由内存池以及伙伴系统：*链表组成
一级空间配置器直接封装malloc，free进行处理，增加了C++中的set_handler机制（这里其实也就是个略显牵强的装饰/适配模式了），增加内存分配时客户端可选处理机制。
可配置性：
客户端可以通过宏__USE_MALLOC进行自定义选择是否使用二级空间配置器。
一级空间配置器就主要封装malloc，添加handler机制了，这里就不罗嗦了，相信各位都是可以通过源码了解到的
关于二级空间配置器：
最后再罗嗦一点，说说Trace问题，然后就给出代码了。
Trace使用
对于内存池的内部实现过程共还是比较复杂的，虽然代码量，函数比较简单。但是调用过程可能比较复杂。这时，如果我们选择debug调试，过程会相当的繁琐，需要仔细记录调用堆栈过程以及数据流向，逻辑变更等。对于楼主这种水货来说，估计完事就要苦了。
所以，就使用Trace进行跟踪，打印数据流向，逻辑走向，文件，函数，方法，行位置。那么我们就能根据这个记录进行程序的排错以及调优了。
具体Trace简单如下
#pragma once #define ___TRACE(...) fprintf(fout, "file[%s]line[%u]func[%s]::",__FILE__,__LINE__,__func__);\
fprintf(fout,__VA_ARGS__)
没错，就是这么简单，利用宏打印文件，行，函数位置，然后利用可变参数列表方式接收代码中具体位置的记录跟踪。
如下是代码摘取的Alloc中的跟中。
static void *Allocate(size_t n)
{
___TRACE("__MallocAllocTemplate to get n = %u\n",n);
void *result = malloc(n);
if ( == result)
{
result = OomMalloc(n);
}
return result;
}
我的天：组织不好，手速太差，终于前奏完成。那么就给出空间配置器的代码了。
具体也可以在个人的github中获取源码
https://github.com/langya0/llhProjectFile/tree/master/STL
文件：Alloc.h
#pragma once #include "Config.h"
__STLBEGIN
#include <memory.h>
#include <stdlib.h> #define __THROW_BAD_ALLOC throw std::bad_alloc() class __MallocAllocTemplate
{
private:
static void *OomMalloc(size_t);
static void *OomRealloc(void *, size_t);
static void(*__malloc_alloc_oom_handler)();
public:
static void *Allocate(size_t n)
{
___TRACE("__MallocAllocTemplate to get n = %u\n",n);
void *result = malloc(n);
if ( == result)
{
result = OomMalloc(n);
}
return result;
}
static void *Reallocate(void *p, size_t old_sz, size_t new_sz)
{
void* result = realloc(p, new_sz);
if ( == result)
{
result = OomRealloc(p, new_sz);
return result;
}
} static void Deallocate(void *p,size_t n)
{
___TRACE("一级空间配置器释放 p= %p n = %u\n",p,n);
free(p);
} //
static void(*set_malloc_handler(void(*f)()))()
{
___TRACE("一级空间配置器,set Handler f = %p\n",f);
void(*old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return (old);
} }; void *__MallocAllocTemplate::OomMalloc(size_t n)
{
___TRACE("一级空间配置器,不足进入Oo中n = %u\n",n);
void(*my_malloc_handler)();
void* result;
for (;;)
{
my_malloc_handler = __malloc_alloc_oom_handler;
if ( == my_malloc_handler)
{
__THROW_BAD_ALLOC;
}
(*__malloc_alloc_oom_handler)();
result = malloc(n);
if (result)
return result;
}
} void* __MallocAllocTemplate::OomRealloc(void* p, size_t n)
{
void(*my_malloc_handler)();
void* result; for (;;)
{
my_malloc_handler = __malloc_alloc_oom_handler;
if ( == my_malloc_handler)
{
__THROW_BAD_ALLOC;
}
(*my_malloc_handler)();
result = realloc(p, n);
if (result)
return result;
}
}
void(*__MallocAllocTemplate::__malloc_alloc_oom_handler)() = ; typedef __MallocAllocTemplate MallocAlloc; //////这里放在#ifdef前边是因为二级空间配置器中还需要调用一级空间配置器
/////////////////////////////////////////根据是否配置__USE_ALLOC选择使用一级还是二级空间配置器
#ifdef __USE_ALLOC
typedef MallocAlloc Alloc;
#else //not define __USE_ALLOC template <bool threads, int inst>
class __DefaultAllocTemplate
{
protected:
enum {_ALIGN = };
enum {_MAX_BYTES = };
enum {_NFREELISTS = }; // _MAX_BYTES/_ALIGN static size_t RoundUp(size_t bytes)
{
return (((bytes) + (size_t) _ALIGN-) & ~((size_t) _ALIGN - ));
} protected:
union _Obj {
// 节点链接指针
union _Obj* _freeListLink;
//客户端数据
char _ClientData[];
}; //桶结构,保存链表
static _Obj* _freeList[_NFREELISTS]; //获取具体大小元素在表中的下标
static size_t _FreeListIndex(size_t __bytes)
{
return (((__bytes) + (size_t)_ALIGN-)/(size_t)_ALIGN - );
} static char* _start_free;
static char* _end_free;
static size_t _heap_size;
public:
static void* Allocate(size_t n)
{
void * ret = ;
___TRACE("二级空间配置器申请n = %u\n",n);
if(n>_MAX_BYTES)
ret = MallocAlloc::Allocate(n); _Obj* volatile * __my_free_list = _freeList + _FreeListIndex(n); _Obj* __result = *__my_free_list;
if (__result == )
ret = _Refill(RoundUp(n));
else
{
*__my_free_list = __result -> _freeListLink;
ret = __result;
}
return ret;
} static void Deallocate(void* p, size_t n)
{
___TRACE("二级空间配置器删除p = %p,n = %d\n",p,n);
if (n > (size_t) _MAX_BYTES)
MallocAlloc::Deallocate(p, n);
else
{
_Obj* volatile* __my_free_list = _freeList + _FreeListIndex(n);
_Obj* q = (_Obj*)p;
q -> _freeListLink = *__my_free_list;
*__my_free_list = q;
}
} static void *Reallocate(void* p,size_t __old_sz,size_t __new_sz)
{
___TRACE("二级空间配置器重新申请p = %p,new_sz = %d\n",p,__new_sz);
void* __result;
size_t __copy_sz; if (__old_sz > (size_t)_MAX_BYTES && __new_sz > (size_t)_MAX_BYTES)
{
return(realloc(p, __new_sz));
} if (RoundUp(__old_sz) == RoundUp(__new_sz))
return(p); __result = Allocate(__new_sz); __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
memcpy(__result, p, __copy_sz);
Deallocate(p, __old_sz);
return(__result);
}
protected:
static void *_Refill(size_t n)
{
___TRACE("二级空间配置器*链表填充n = %u\n",n); size_t nobjs = ;
void * ret;
char * chunks = _ChunkAlloc(n,nobjs); if(nobjs == )
{
return chunks;
}
_Obj* volatile * __my_free_list = _freeList+_FreeListIndex(n);
ret = chunks; for(size_t i = ;i<nobjs;i++)
{
((_Obj*)(chunks+n*i))->_freeListLink = *__my_free_list;
*__my_free_list = (_Obj*)(chunks+n*i);
}
return ret;
} /////////////这里的nobjs使用&，，内部需要复用逻辑，可能改变之
static char * _ChunkAlloc(size_t n,size_t &nobjs)
{
size_t totalBytes = n*nobjs;
size_t bytesLeft = _end_free - _start_free; if(bytesLeft>=totalBytes)
{
___TRACE("二级空间配置器内存池填充n = %u,nobjs = %d\n",n,nobjs);
_start_free += n*nobjs;
return _start_free;
}
else if(bytesLeft>=n)
{
nobjs = (_end_free- _start_free)/n;
___TRACE("二级空间配置器内存池填充n = %u,nobjs = %d\n",n,nobjs);
_start_free +=n*nobjs;
return _start_free;
} //bytesLeft [0,1)
_Obj* volatile * __my_free_list = _freeList + _FreeListIndex(bytesLeft);
if(_start_free)
{
___TRACE("二级空间配置器剩余bytesLeft = %u\n",bytesLeft);
((_Obj*)_start_free)->_freeListLink=*__my_free_list;
*__my_free_list = (_Obj*)_start_free;
} size_t bytesToGet = nobjs*n*+(_heap_size>>); //malloc
_start_free = (char*)malloc(bytesToGet); if(!_start_free)
{
___TRACE("二级空间配置器malloc失败，在后续链表查找n = %d\n",n);
for(size_t i = n + _ALIGN;i < _MAX_BYTES;i+=_ALIGN)
{
_Obj* volatile * cur = _freeList+_FreeListIndex(i);
if(*cur)
{
*cur = (*cur)->_freeListLink;
_start_free = (char*)*cur;
_end_free = _start_free + i; return _ChunkAlloc(n,nobjs);
}
} ___TRACE("二级空间配置器：后续链表查找失败，转接一级配置，借用handler机制终止程序或者得到空间n = %d\n",n);
_start_free = (char*)MallocAlloc::Allocate(n);
return _ChunkAlloc(n,nobjs);
}
else
{
_end_free = _start_free + bytesToGet;
_heap_size += bytesToGet;
return _ChunkAlloc(n,nobjs);
} }
}; template <bool __threads, int __inst>
char* __DefaultAllocTemplate<__threads, __inst>::_start_free= ; template <bool __threads, int __inst>
char* __DefaultAllocTemplate<__threads, __inst>::_end_free = ; template <bool __threads, int __inst>
size_t __DefaultAllocTemplate<__threads, __inst>::_heap_size = ; // static _Obj* _freeList[_NFREELISTS];
template <bool threads, int inst>
typename __DefaultAllocTemplate<threads,inst>::_Obj*
__DefaultAllocTemplate<threads,inst>::_freeList[__DefaultAllocTemplate<threads,inst>::_NFREELISTS]
= {, , , , , , , , , , , , , , , }; typedef __DefaultAllocTemplate<,> Alloc;
#endif __STLEND void handler()
{
cout << "here in handler!\n"<<endl;
}
void test()
{
// stl::Alloc::set_malloc_handler(handler);
void *arr[] = {};
___TRACE("Clint to Get size = %u\n",); // for(size_t i =0;i < 21;++i)
// arr[i] = stl::Alloc::Allocate(5);
// for(size_t i =0;i < 21;++i)
// stl::Alloc::Deallocate(arr[i],5);
arr[] = stl::Alloc::Allocate();
arr[] = stl::Alloc::Allocate(); arr[] = stl::Alloc::Allocate();
}
文件：Trace.h
#pragma once #define ___TRACE(...) fprintf(fout, "file[%s]line[%u]func[%s]::",__FILE__,__LINE__,__func__);\
fprintf(fout,__VA_ARGS__)
文件Config.h
#pragma once /////模拟std实现宏方式开始，结束命名空间
namespace __STLNAMESPACE {} #define __STLBEGIN namespace __STLNAMESPACE { #define __STLEND } namespace stl = __STLNAMESPACE; //for malloc
// #define __USE_MALLOC ///for trace
#define __DEBUG
#ifdef __DEBUG
#include <stdio.h>
#define fout stdout ///方便配置，修改Trace记录位置
#endif
终于大功告成，源码finished，那么，再给出测试结果截图了
最后，完成了主题工作之后。
再来说一些空间配置器的遗留问题吧：
1.仔细探究源码之后，你一定会发现一个问题，
貌似二级空间配置器中的空间重头到尾都没看到他归还给系统。那么问题就是，内存池空间何时释放？
对于这个问题，在回头浏览一下源码及结构图，你就会发现
大于128的内存，客户程序Deallocate之后会调free释放掉，归还给了系统。
但是呢...............
内存池中获取的空间，最终，假定用户都调用Dealloc释放调了，那么他们又在哪里呢？
没有还给系统，没有在内存池，在*链表中。
Got it：程序中不曾释放，只是在*链表中，且配置器的所有方法，成员都是静态的，那么他们就是存放在静态区。释放时机就是程序结束。
2.如果需要释放，那么应该怎么处理呢？
因为真正可以在程序运行中就归还系统的只有*链表中的未使用值，但是他们并不一定是连续的（用户申请空间，释放空间顺序的不可控制性），所以想要在合适时间（eg一级配置器的handler中释放，或者设置各阀值，分配空间量到达时处理），就必须保证释放的空间要是连续的。保证连续的方案就是：跟踪分配释放过程，记录节点信心。释放时，仅释放连续的大块。
3.关于STL空间配置器的效率考究
既然已经存在，而又被广泛使用，那么，整体的效率，以及和STL内部容器之间的使用配合还是没问题的。
我们考虑几种情况：
a. 用户只需要无限的char类型空间，然而配置器中却对齐到8，于是乎，整个程序中就会有7/8的空间浪费。
b.对于假定用户申请N次8空间，将系统资源耗到一定程度，然后全部释放了，*链表中的空间都是连续的。却没有释放。
但是：用户需要申请大于8的空间时，却依旧没有空间可用。
总之：这个问题就是，空间可能全部积攒在小块*链表中，却没有用户可用的。这就尴尬了。
最后，关于配置器的其它问题，如果各位有什么新的思考，欢迎交流。邮箱：15829391774@163.com