成员函数的适配器

mem_fn

算法库里面的for_each与成员函数并不适配，所以要使用mem_fn来跟for_each第三个参数适配一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Number{
public:
    void print(){
        ...
    }
    //判断是不是一个偶数
    bool isEven(){
        ...
    }
};

void test(){
    vector<Number> vec;
    for(size_t i = 0; i < 30; ++i){
        vec.push_back(Number(i));
    }
    for_each(vec.begin(),vec.end(),mem_fn(&Number::print));//不这么写会报错
    
    
    //删除所有的偶数
    remove_if(vec.begin(),vec.end(),mem_fn(&Number::isEven));//第三个参数要求一个一元断言
    //返回一个迭代器（符合条件的迭代器）,回忆一下
    //要删除要配合erase
    vec,erase((remove_if(vec.begin(),vec.end(),mem_fn(&Number::isEven))),vec.end());
}

除了用mem_fn来适配，用bind是否也可以适配呢

1
2
3
4
5
6
7
void test(){
    vector<Number> vec;
    for(size_t i = 0; i < 30; ++i){
        vec.push_back(Number(i));
    }
    for_each(vec.begin(),vec.end(),bind(&Number::print,_1));//bind绑定的参数不能使用固定的对象，不然按我的理解，每次都是调用的该对象的 print,那不能用固定的对象，那this指针这个参数应该填什么？ 还有占位符，这样就可以每次都传递的是vec里面的对象了
}

for_each第三个参数绑定的是一元断言，但是使用bind绑定后改变函数形态变成无参函数，其实是相当于给参数提供了一个默认值

函数对象

所有可以与()进行结合，体现函数定义的都称为函数对象。

1，重载了函数调用运算符(operator())的类创建的对象

2，函数名

3，函数指针

空间配置器（==重要==）

为什么要把空间的申请和对象的构建分开呢？

因为在STL中，需要的对象是批量的，如果把申请空间和构建对象两个操作黏在一起，那么每次有一个新对象就要申请一次空间，而且，每次申请的空间可能都不是连续的，这样会造成内存碎片的问题或者效率不高，所以就将空间的申请和对象的构架分开，先申请的大量的空间，需要对象就在这篇空间里构建一个对象，避免了频繁的申请空间，也没有内存碎片。

函数接口

1
2
3
4
5
6
7
8
9
10
11
12
//申请空间
T * allocate(std::size_t n);


//释放空间
void deallocate(T *p, std::size_t n);

//构建对象
void construct( pointer p, const_reference val );

//销毁对象
void destroy( pointer p );

为什么要先销毁对象再回收空间，为什么不直接回收空间呢？

因为，空间内存的对象很有可能也指向某一片堆空间，那么这些对象的析构函数就不会执行，会造成内存泄漏，先销毁对象就会调用这些对象的析构函数。

原理

空间配置器分为两级

  • 一级空间配置器
  • 二级空间配置器
    • 大于128字节调用一级空间配置器
    • 小于128字节使用16维自由链表+内存池

16维自由链表就是一个数组，然后每个索引下面挂一个链表（类似于哈希表的拉链法），索引为0，下面挂的就是8字节的自由链表（每个节点都是8字节），索引为1，下面挂的就是16字节的自由链表，以此类推，下标为15挂的就是128字节的自由链表。

[pkgVrb4.png

如果要申请n个字节的空间，且n<128个字节，那么就会对n向上取整，例如想要申请30个字节，那么就会映射找到下标为3的位置，如果该索引下面足够分配此32个字节，那么就分配，如果不够，就直接申请20个32字节，然后留下分配给此次申请的空间，然后将剩下的全挂在该索引下面的位置上。

默认情况下调用的是二级空间配置器。

为什么要使用16维的自由链表+内存池？

我们认为128一下就是小片空间，如果频繁申请小片空间可能会出现一下问题：

  1. 频繁申请小片空间的时候，会有内存碎片的问题
  2. 频繁的在内核态和用户态之间进行切换，会导致效率不高

源码剖析

空间配置器——allocator

1
2
3
4
5
6
7
8
9
10
11
12
13
class allocator {
  typedef alloc _Alloc;
public:
  _Tp* allocate(size_type __n, const void* = 0) {
    return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) 
                    : 0;
  }
  void deallocate(pointer __p, size_type __n)
    { _Alloc::deallocate(__p, __n * sizeof(_Tp)); }

  void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
  void destroy(pointer __p) { __p->~_Tp(); }
};

有四个函数allocate,deallocate,construct,destory很重要

这四个函数就是上述提到了四个函数接口

接下来一个一个分析

allocate

1
2
3
4
_Tp* allocate(size_type __n, const void* = 0) {
    return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) 
                    : 0;
  }

发现这个函数内部调用了_Alloc::allocate,接下来看看这个是个什么东西

首先_Alloc的定义为

1
typedef alloc _Alloc;

说明调用了alloc这个类的成员函数allocate分配内存，去找到alloc这个类的定义

在这里就涉及到两级空间配置器了

一级空间配置器
1
2
3
# ifdef __USE_MALLOC

typedef malloc_alloc alloc;

定义了宏的话分配内存就会走一级空间配置器，接下来就要去看看一级空间配置器到底是什么原理，去找到malloc_alloc的定义

1
typedef __malloc_alloc_template<0> malloc_alloc;

发现有一个别名，接着找

1
2
3
4
5
6
7
8
9
10
class __malloc_alloc_template {
public:

  static void* allocate(size_t __n)
  {
    void* __result = malloc(__n);
    if (0 == __result) __result = _S_oom_malloc(__n);
    return __result;
  }
};

只需要去看allocate的定义，发现底层就是调用了一个malloc来分配内存

二级空间配置器

二级空间配置器就是默认的分配内存的空间配置器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class __default_alloc_template {

private:
#if ! (defined(__SUNPRO_CC) || defined(__GNUC__))
    enum {_ALIGN = 8};
    enum {_MAX_BYTES = 128};
    enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN
# endif
  static size_t
  _S_round_up(size_t __bytes) 
    { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }

__PRIVATE:
  union _Obj {
        union _Obj* _M_free_list_link;
        char _M_client_data[1];    /* The client sees this.        */
  };
private:
    static _Obj* __STL_VOLATILE _S_free_list[]; 
# else
    static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS]; 
# endif
  static  size_t _S_freelist_index(size_t __bytes) {
        return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
  }

  // Returns an object of size __n, and optionally adds to size __n free list.
  static void* _S_refill(size_t __n);
  // Allocates a chunk for nobjs of size size.  nobjs may be reduced
  // if it is inconvenient to allocate the requested number.
  static char* _S_chunk_alloc(size_t __size, int& __nobjs);

  // Chunk allocation state.
  static char* _S_start_free;
  static char* _S_end_free;
  static size_t _S_heap_size;
}；

这里有几个比较重要的东西

1
2
3
4
_S_round_up(size_t __bytes);
_S_freelist_index(size_t __bytes);
_S_refill(size_t __n);
_S_chunk_alloc(size_t __size, int& __nobjs);

四个函数以及自由链表和三个指针

1
2
3
4
static _Obj* _S_free_list[_NFREELISTS]; 
  static char* _S_start_free;
  static char* _S_end_free;
  static size_t _S_heap_size

接下来就会涉及到这几个东西的应用

首先是四个函数各自的作用

](https://imgse.com/i/pkgVrb4)
pkgVyVJ.png

_S_freelist_index
1
2
3
static  size_t _S_freelist_index(size_t __bytes) {
      return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
}

这里_ALIGN在上述代码有定义

1
2
3
enum {_ALIGN = 8};
enum {_MAX_BYTES = 128};
enum {_NFREELISTS = 16};

举例说明取下标的用法：

例如要分配32字节的空间，那么这里传入参数32，执行分子运算

((__bytes) + (size_t)_ALIGN-1–>(32 + 8 - 1) = 39
分母运算
(size_t)_ALIGN - 1)–>8 = 8
得结果为:return 39/8-1;最终返回4-1=3，刚好对应16维数组下标为三的位置

_S_round_up
1
2
_S_round_up(size_t __bytes) 
  { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }

举例说明向上取整，得到8的整数倍的用法：

例如要分配32字节的空间，这里传入参数32，

执行前半部分的运算:((__bytes) + (size_t) _ALIGN-1—>(32+8-1) = 39

执行后半部分运算：(size_t) _ALIGN - 1)—>(8-1)=7

然后后半部分取反，前后按位与运算，首先后半部分按位取反 ~7 = ~0000 0111 = 1111 1000

前后按位与运算 39 = 32 + 4 + 2 + 1

​ 0001 0111
& 1111 1000
/——————–
​ 0001 0000 ——> 32

例子二:传入31，同上述运算，然后得

​ 0001 0110

& 1111 1000
/———————
0001 0000 ——->32

所以得出结论，通过该函数就可以向上取整得到8的整数倍

_S_refill
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void* __default_alloc_::_S_refill(size_t __n)
{
    int __nobjs = 20;
    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 = __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 -> _M_free_list_link = 0;
            break;
        } else {
            __current_obj -> _M_free_list_link = __next_obj;
        }
      }
    return(__result);
}

这里就跟上述原理联系起来了，即上述提到的：如果不够，就直接申请20个32字节，看这里定义了一个

1
int __nobjs = 20;

然后该函数一进来就调用了_S_chunk_alloc这个函数，这个函数的分析可以看下面

通过_S_chunk_alloc分配好了内存，然后在这里进行了这样一个操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
__my_free_list = _S_free_list + _S_freelist_index(__n);

     __result = (_Obj*)__chunk;
     *__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 -> _M_free_list_link = 0;
           break;
       } else {
           __current_obj -> _M_free_list_link = __next_obj;
       }
     }

这里的操作实际上是把申请的一大片连续的空间切分为与索引对应的小块然后用自由链表索引起来。

从开头

1
__my_free_list = _S_free_list + _S_freelist_index(__n);

获得对应的索引下标，得到自由链表的头指针，这里自由链表的类型是

1
_Obj** __my_free_list;

是一个二级指针，这里_Obj的定义为

1
2
3
4
union _Obj {
      union _Obj* _M_free_list_link;
      char _M_client_data[1];
};

其中 union _Obj* _M_free_list_link;就相当于链表的next

然后这里的_S_free_list的定义为

1
_S_free_list[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };

其实就是栈里面的数组，用来挂自由链表的（类似于拉链法里面的哈希表）,然后通过_S_free_list + _S_freelist_index(__n);就找到相应的索引下标的位置了

然后在这里将申请的那一大片空间挂在对应的下标的位置

1
*__my_free_list = __next_obj = (_Obj*)(__chunk + __n);

注意这里在最后加了一个__n，这是因为第一块要分出去作为此次内存分配的结果，然后将剩下的挂在S_free_list下面留着备用（如果下次还要申请该大小的空间，就直接在这里取一个节点即可，不需要重新分配了）

开始切分

1
2
3
4
5
6
7
8
9
10
for (__i = 1; ; __i++) {
        __current_obj = __next_obj;
        __next_obj = (_Obj*)((char*)__next_obj + __n);
        if (__nobjs - 1 == __i) {
            __current_obj -> _M_free_list_link = 0;
            break;
        } else {
            __current_obj -> _M_free_list_link = __next_obj;
        }
      }

每次通过这个操作

1
__next_obj = (_Obj*)((char*)__next_obj + __n);

切一块，然后配合__current_obj来将申请的一大片内存来切分为对应大小的内存块作为自由链表的节点挂在S_free_list下面

然后还有一句没有分析

1
if (1 == __nobjs) return(__chunk);

如果只有一块的话也不需要切分了，直接分配就行了

_S_chunk_alloc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
template <bool __threads, int __inst>
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;

    if (__bytes_left >= __total_bytes) {
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    } else if (__bytes_left >= __size) {
        __nobjs = (int)(__bytes_left/__size);
        __total_bytes = __size * __nobjs;
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    } else {
        size_t __bytes_to_get = 
	  2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
        if (__bytes_left > 0) {
            _Obj* __STL_VOLATILE* __my_free_list =
                        _S_free_list + _S_freelist_index(__bytes_left);

            ((_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;
            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) {
                    *__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));
                }
            }
	    _S_end_free = 0;	
            _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
        }
        _S_heap_size += __bytes_to_get;
        _S_end_free = _S_start_free + __bytes_to_get;
        return(_S_chunk_alloc(__size, __nobjs));
    }
}

这个比较复杂，举例说明：

如果要申请32个字节的空间，首先走函数_S_refill，这里给

__nobjs赋值为20，传入该函数，并且需要注意的是，这里传入的是一个引用类型，说明函数内部可能会改变这个的取值

接下来按顺序执行代码

1
2
3
char* __result;
size_t __total_bytes = __size * __nobjs;
size_t __bytes_left = _S_end_free - _S_start_free;

这里的__total_bytes –> 32*20 = 640

这里 的__bytes_left —>0

这里出现两个较为陌生的东西，这两个东西其实在二级空间配置器的类定义中出现过，如下

1
2
3
static char* _S_start_free;
static char* _S_end_free;
static size_t _S_heap_size;

初始化为

1
2
3
4
5
char* __default_alloc_template::_S_start_free = 0;

char* __default_alloc_template::_S_end_free = 0;

size_t __default_alloc_template::_S_heap_size = 0;

所以可以得出上述的结果，然后继续往下走代码

1
2
3
4
5
if (__bytes_left >= __total_bytes) {
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
}

这里0 >= 640吗，不符合 所以不走这个if语句

1
2
3
4
5
6
7
else if (__bytes_left >= __size) {
        __nobjs = (int)(__bytes_left/__size);
        __total_bytes = __size * __nobjs;
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    }

再看这个else if语句，0 >= 32吗，也不符合 所以走最后的else语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
else {
        size_t __bytes_to_get = 
	  2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
        if (__bytes_left > 0) {
            _Obj* __STL_VOLATILE* __my_free_list =
                        _S_free_list + _S_freelist_index(__bytes_left);

            ((_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;
            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) {
                    *__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));
                }
            }
	    _S_end_free = 0;	//
            _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
        }
        _S_heap_size += __bytes_to_get;
        _S_end_free = _S_start_free + __bytes_to_get;
        return(_S_chunk_alloc(__size, __nobjs));
    }

慢慢往下分析

首先搞了一个这个

1
2
size_t __bytes_to_get = 
	  2 * __total_bytes + _S_round_up(_S_heap_size >> 4);

__bytes_to_get = 2 * 640 + 向上取整的8的整数倍(0 >> 4) 的其结果为1280字节

然后看下面的if判断语句

1
2
3
4
5
6
7
if (__bytes_left > 0) {
            _Obj* __STL_VOLATILE* __my_free_list =
                        _S_free_list + _S_freelist_index(__bytes_left);

            ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
            *__my_free_list = (_Obj*)_S_start_free;
        }

这里__bytes_left是

1
size_t __bytes_left = _S_end_free - _S_start_free;

这个东西，结果是0，那么这里 0> 0吗。显然不符合，所以这个if语句跳过，看下面的语句

1
_S_start_free = (char*)malloc(__bytes_to_get);

这里直接分配了1280字节的内存
然后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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.
            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) {
                    *__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.
                }
            }
	    _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.
        }

malloc分配内存成功，这个if判断语句是不会进去的，先讨论分配内存成功的情况，不成功的待会讨论

不走if接下来走下面的语句

1
2
3
_S_heap_size += __bytes_to_get;
        _S_end_free = _S_start_free + __bytes_to_get;
        return(_S_chunk_alloc(__size, __nobjs));

_S_heap_size –> 0 + 1280 = 1280

_S_end_free —> 0 + 1280 = 1280

相当于用一个_S_heap_size记录了申请的堆空间的大小，用一个_S_start_free和_S_end_free将这片空间的首位地址记录了（相当于框起来了）

然后执行递归，传入的参数依然是（32，20）

再次执行

1
2
3
char* __result;
size_t __total_bytes = __size * __nobjs;
size_t __bytes_left = _S_end_free - _S_start_free;

这里__total_bytes仍然是640，但是要注意的是__bytes_left的值这里改变了

__bytes_left —> 1280 - 0 = 1280

然后继续往下执行

1
2
3
if (__bytes_left >= __total_bytes) {
    ...
}

判断语句 1280 >= 640吗，这次就符合条件了，会执行if里面的语句

1
2
3
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);

__result —> 0 作为分配内存的首地址返回

_S_start_free–> 0 + 640 = 640，这里把后半部分剩下的640字节放到内存池里面了，用_S_start_free和_S_end_free两个指针维护，自此，32字节的空间分配就结束了

结果就是返回了一个640字节的空间让refill函数切分，然后剩下的640字节的空间放在内存池里用作备用

分配64字节的空间，此时内存充足

依然是按上述执行，只不过传入的参数变为了(64,20)

1
2
3
char* __result;
size_t __total_bytes = __size * __nobjs;
size_t __bytes_left = _S_end_free - _S_start_free;

__total_bytes —> 64 * 20 = 1280

__bytes_left —> 1280 - 640 = 640

然后看下面的if语句

1
2
3
4
5
if (__bytes_left >= __total_bytes) {
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    }

640 >= 1280吗，显然不符合，该if语句不执行

然后看下面的else if语句

1
2
3
4
5
6
7
else if (__bytes_left >= __size) {
        __nobjs = (int)(__bytes_left/__size);
        __total_bytes = __size * __nobjs;
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    }

640 >= 64吗，显然符合，所以这次的空间分配会走到这个if里面，下面看看干了什么操作

首先改变了__nobjs的值，从20变成了640/64 = 10，然后将__total_bytes赋值为64 * 10 = 640，然后让__result指向内存池中的那640个字节，然后这里说明内存池的640的空间已经分配出去了，需要更改_S_start_free,这时_S_start_free和__total_bytes相等了，说明内存池没有空闲内存了，然后将分配出那640的空间返回

这里修改__nobjs会影响到refill函数切分的内存块的大小，这里就只会切分10快，然后分配出去一块，然后挂9快了

自此，本次分配结束

申请96字节的内存

这次分配其实跟分配32内存是一摸一样的，只是数值有所改变，所以这里不再赘述，只是将最终的更改的结果进行计算

__total_bytes —> 20 * 96 = 1920

这里有所改变

1
2
size_t __bytes_to_get = 
	  2 * __total_bytes + _S_round_up(_S_heap_size >> 4);

因为_S_heap_size在分配32字节空间的时候被改变了

__bytes_to_get —> 2 * 1920 + 向上取整得到8的倍数(1280 >> 4) = 3840 + 80 = 3920

然后会分配3920的内存在这里

1
_S_start_free = (char*)malloc(__bytes_to_get);

然后最后

1
2
_S_heap_size += __bytes_to_get;
_S_end_free = _S_start_free + __bytes_to_get;

_S_heap_size–> 1280 + 3920 = 5200

_S_end_free —> 1280 + 3920 = 5200

进入递归后就会跟分配32字节一样，进入第一个if语句

1
2
3
4
5
if (__bytes_left >= __total_bytes) {
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    }

然后分配出1920的空间，留出2000字节的空间在内存池中，因为

_S_start_free—> 1280 + 1920 = 3200

``_S_end_fre` —> 5200 ,所以内存池所剩的空间大小为5200-3200 = 2000

自此本次分配结束

分配72字节，假定此刻内存池耗尽，堆空间没有大于72字节的连续空间

这里传入参数(72,20)

然后按照正常流程

1
2
3
size_t __total_bytes = __size * __nobjs;
size_t __bytes_left = _S_end_free - _S_start_free;

得到__total_bytes = 72*20 = 1440

因为内存池耗尽了，所以__bytes_left = 0

所以就会进入else语句当中，又因为堆空间内已经没有大于72字节的连续空间了，所以，直接看到这句

1
_S_start_free = (char*)malloc(__bytes_to_get);

这句分配内存就会失败，所以就会进入下面这个if语句当中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
if (0 == _S_start_free) {
            size_t __i;
            _Obj* __STL_VOLATILE* __my_free_list;
	    _Obj* __p;
            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) {
                    *__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));
.
                }
            }
	    _S_end_free = 0;	
            _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);

}

这里用到了自由链表

1
_Obj** __my_free_list;

然后就进入了一个for循环

1
for (__i = __size;__i <= (size_t) _MAX_BYTES;__i += (size_t) _ALIGN)

这里的_MAX_BYTES在上述也有写过

定义是这样的

1
2
3
enum {_ALIGN = 8};
enum {_MAX_BYTES = 128};
enum {_NFREELISTS = 16};

所以翻译出来的代码其实就是

1
for (__i = 72;__i <= 128;__i += 8 _ALIGN)

然后看for循环的第一句

1
__my_free_list = _S_free_list + _S_freelist_index(__i);

可以发现似曾相识，因为在refill函数里也用过这句话，含义就是从16维数组的72这个下标的位置开始，一个一个的遍历他们下面挂着的自由链表(如果有的话)

如果他们下面挂着自由链表的话，就会进入这个if语句

1
2
3
4
5
6
if (0 != __p) {
                    *__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));.
                }

相当于是从这个索引下面的自由链表里摘了一个节点，

1
2
_S_start_free = (char*)__p;
                    _S_end_free = _S_start_free + __i;

这两句话就相当于从摘下来的那个节点分配出72+i字节的空间（就是就是这个节点的全部空间），然后递归执行这句话

1
size_t __bytes_left = _S_end_free - _S_start_free;

得到的结果就不是0了，而是72，所以就会满足这个条件判断语句

1
2
3
4
5
6
7
else if (__bytes_left >= __size) {
        __nobjs = (int)(__bytes_left/__size);
        __total_bytes = __size * __nobjs;
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    }

然后这里__nobjs–->72/72 = 1

​ __total_bytes –>72*1 = 72

​ _S_start_free向后偏移72个字节，然后就可以和_S_end_free维护之前那个节点剩下的空间了

然后返回refill函数就会执行

1
if (1 == __nobjs) return(__chunk)

自此内存分配结束

deallocate

1
2
void deallocate(pointer __p, size_type __n)
   { _Alloc::deallocate(__p, __n * sizeof(_Tp)); }

这里也是调用了_Alloc类的deallocate函数，找一下该函数的定义

一级空间配置器
1
typedef malloc_alloc alloc;

然后再找malloc_alloc

1
typedef __malloc_alloc_template<0> malloc_alloc;

然后再找__malloc_alloc_template<0>

1
2
3
4
5
6
7
class __malloc_alloc_template {
  static void deallocate(void* __p, size_t /* __n */)
  {
    free(__p);
  }

};

只是进行了free

二级空间配置器
1
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;

然后找到定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static void deallocate(void* __p, size_t __n)
  {
    if (__n > (size_t) _MAX_BYTES)
      malloc_alloc::deallocate(__p, __n);
    else {
      _Obj* __STL_VOLATILE*  __my_free_list
          = _S_free_list + _S_freelist_index(__n);
      _Obj* __q = (_Obj*)__p;
      _Lock __lock_instance;

      __q -> _M_free_list_link = *__my_free_list;
      *__my_free_list = __q;

    }
  }

发现这里首先进行了一个条件判断

1
2
if (__n > (size_t) _MAX_BYTES)
      malloc_alloc::deallocate(__p, __n);

假设这里传入的是__n == 256那么，256 > 128吗？显然符合，所以会走

1
malloc_alloc::deallocate(__p, __n);

这个其实就是一级空间配置器的内存释放函数，就是最后free了一下

如果传入的是32呢，那么就会走else

1
2
3
4
 _Obj**  __my_free_list = _S_free_list + _S_freelist_index(__n);
_Obj* __q = (_Obj*)__p;
__q -> _M_free_list_link = *__my_free_list;
*__my_free_list = __q;

这里有看到了这句话

1
_Obj**  __my_free_list = _S_free_list + _S_freelist_index(__n);

跟上述是一样的，找到对应的自由链表，然后将要释放的__p强转为_Obj*，交给__q保存，然后其实就是进行了一个头插，将要释放的这块空间又挂回自由链表里了，也就是说，如果要释放128kb内的小内存，就把这些小内存重新挂会自由链表，不会真正的释放，而是可以重复利用

construct

这个不分一级配置器或者二级配置器

1
void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }

这里用到了定位new表达式

定位new表达式接受指向未构造内存的指针，并在该空间中初始化一个对象或者数组。不分配内存，它只在特定的，预分配的内存地址构造一个对象。

destroy

这个也不分一级配置器或者二级配置器

1
void destroy(pointer __p) { __p->~_Tp(); }

就是调用了一下要释放内存的那个对象的析构函数，完成对对象的释放，比较简单

​