文章目录
背景
STL是一个C++程序员经常使用的库，目前有很多缪论说大厂不使用STL, 其实并不是，谷歌很多代码都是使用STL, 只有极个别需要定制的逻辑或者定制化提升性能时才会抛弃STL，因此在我们日常工作还是要大胆使用STL, 引用荀子劝学的一句话就是『登高而招，臂非加长也，而见者远；顺风而呼，声非加疾也，而闻者彰。』，所以我们要合理使用STL来提升开发效率。
作为一个优秀的库，我们不仅要知其然，也要知其所以然，不然某天美帝禁止我们使用STL不就gg了？下面就开始踏上学习STL的旅程，不过在学习STL之前一定要学好元编程，STL几乎是一个模板库的经典案例，所以基础不牢，地动山摇。
理解
空间配置器，英文名字是allocator, 作用就是分配空间，我们知道当在使用vector, list等容器的时候，从来没有过malloc, new等操作，其实这都是空间配置器帮我们处理了，那么本节就是讲如何设计一个空间配置器。
alloctor必须要有哪些属性？
- allocate()
- deallocate()
上面两个内存分配函数很好理解，就是分配内存和释放内存。
alloctor如何使用？
//我们日产使用的方式
vector<int> vec;
//其实
template<typename T>
class MyAlloc;
vector<int, MyAlloc<int>> vec;
//如果使用SGI STL的话直接如下,这个是因为SGI STL没有按照STL的标准来，这个后续会有讲解。
vector<int, std::alloc> vec;
研究一下SGI STL中的std::alloc?
alloc主要是将new和delete实现一下，用自己实现的construct和allcocate组合来代替new, 这个可以更加细致处理。
全局函数construct() 和destroy()
template<typename T, typename Value>
inline void construct(T* p, const Value& value)
{
new (p) T(value);//在一个指定内存指针上构建对象。
}
template<typename T>
inline void destroy(T* ptr)
{
ptr->~T();
}
//重载函数
template<typename ForwardIterator, class T>
inline void destroy(ForwardIterator first, ForwardIterator last)
{
__destory(first,last, value_type(first));
}
//看一下value_type的逻辑
template<typename Itera>
Itera::pointer value_type(Itera it)
{
Itera::pointer res= nullptr;
return res ;
}
//偏特化
template<typename T>
T* value_type<T*>(T it)
{
T* res= nullptr;
return res ;
}
template<typename ForwardIterator, typename T>
void __destory(ForwardIterator first, ForwardIterator last, T*)
{
typedef typename __type_traits<T>::has_trivial_destructor trivival_des;//trivial_des是一个类型
__destroy_aux(firstm last, trivial_des());
}
template<typename ForwardIterator>
void __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type)
{
for(;first < last; ++first)
{
destory(&*first);
}
}
//函数重载，最后一个参数类型不一样
void __destroy_aux(ForwardIterator first, ForwardIterator last, __true_type){}//无关紧要的类型，析构函数不需要调用
//相关模板如下
struct __true_type {};
struct __false_type {};
//默认
template<typenam T>
struct __type_traits
{
typename __false_type has_trivial_destructor;
}
//全特化
template<>
struct __type_traits<int>
{
typename __true_type has_trivial_destructor;
}
template<>
struct __type_traits<float>
{
typename __true_type has_trivial_destructor;
}
如果上面的代码看不懂还是建议先去学习元模板编程。上面的代码意思是，如果析构的是一个对象则直接处理，如果是一个区间，则看一下这个对象是不是需要有必要析构(这点可能有些人不明白，其实在free或者operator delete的时候会直接清空相应的内存块，而之所以要析构目的是害怕有的对象在析构函数中搞事情，比如打印个bye啥的，对于基础数据pod是不需要的，可以参考逻辑链接), 如果析构有必要则慢慢析构，没必要的话直接跳过不处理
内存的分配和释放如何实现？
SGI STL实现了两个alloc类型，这里记住，是alloc类型不是模板，虽然模板有两个数值参数但是为了多线程设置了，这里不再考虑范围内，所以我们就可以当是两个alloc类型，那么要使用模板怎么用，这里SGI STL又包装了一下：
template <typename T, typename Alloc>
class simple_alloc
{
public:
static T* allocate(size_t n)
{
Alloc::allocate(n * sizeof(T))//SGI用的是malloc函数
}
static T* deallocate(T* ptr, size_t n)
{
Alloc::deallocate(p, n * sizeof(T))//free函数
}
}
这里我们主要研究二级配置器__default_alloc_template.
__default_alloc_template 如何实现？
当需要内存需求大于128字节时，直接调用malloc, 否则从内存池中获取。至于为什么这么处理可以参考内存碎片 和内存布局。下面主要讲一下这个内存池的原理。
内存池每次可以给出的内存是8的整数倍，只能有下面16个尺寸：8，16，。。。120，128字节。在此之前先介绍一下union类型。
什么是uninon?
union Test{
char cval;
int ival;
double dval;
}
Test t
/*|cc cc cc cc | cc cc cc cc|*/ //8字节
t.cval = 'a';
/*|61 cc cc cc | cc cc cc cc|*/
t.ival = 1;
/*|01 00 00 00 | cc cc cc cc|*/
t.dval = 2.5;
/*|00 00 00 00 | 01 00 04 40|*/
obJ
根据上面的知识，我们先来定一个结构：
union obj {
union obj* free_list_link;
char client_data[1];
}
/*|00 00 00 00/
这一块比较骚，free_list_link可以一理解，单链表的下一个指针，client_data是啥意思？为啥client_data[1]?我们知道如果定义为char client_data,当调用obj_test.char_data返回的是第一个字节的数值，当定义为数组时，obj_test.char_data的时候，返回的是char_data数组的首地址，而这个首地址和obj_test是完全一样的，不过后面完全没有使用，据说是什么柔性数组的目的，不知道博主都在瞎扯些什么，后面根本没有用到，看了老半天，看不懂的可以不用管。
示意图
分配内存和释放内存比较简单，就不在展示代码，简单说就是先找到某个类型尺寸，比如是128字节，然后取出一块A, 然后A指向的B的地址填到#16的位置，释放的时候就是把A的下一个节点链接到#16的地址，然后把自己的地址赋值给#16。
如果free_list的某一个尺寸没有内存了怎么办？
简单，一开始就留了一手，下图中的橘黄色部分就是没有挂载到任何序列类型中的，所以到时候会根据情况调配。
内存处理基本工具
主要是三个全局函数：uninitialized_copy(), uninitialized_fill(),uninitialized_fill_n(),后面会使用，核心的目的就是POD数据处理方式和一般自定义的类型不相同，这个跟上面destroy()的原理一模一样，主要是元编程的相关知识，很简单，这里不再详细阐述。