从零开始，打造自己的STL(三、alloc)

发表于 | 更新于 | 分类于

简述

在stl中，所有的内存分配与释放都是交由allocator来实现的。在大部分情况下，我们都接触不到这里面的内容，因为它一直是隐藏在幕后悄悄的工作。

当然如果对于内存分配有特殊的要求的话，STL也提供了接口供我们使用自己的分配器

比如在vector的定义上

1
2
3
4
template <typename _Tp, typename _Alloc = alloc >
class vector : protected _Vector_base<_Tp, _Alloc>
{
}

可以看到，模板参数_Alloc是可以由我们自己指定的。在使用的时候我们可以通过如下方式指定自己的分配器

1
vector<int, myalloc> vec;

这样，内存的分配就交由我们来完成了。但是在我们自己的方法中，必须要提供 allocate 和 deallocate 这两个接口。否则是无法使用的

内存分配策略

在SGI的STL中，内存的分配策略有两种

  1. 一级空间配置器。凡是大于128bytes内存的空间，都会交由一级空间配置器来完成。它的底层直接通过 malloc 和 free 实现。

  2. 二级空间配置器。二级空间配置器是通过内存池来管理里面的内存分配与释放。凡是小于128bytes的内存需求都会通过它来配置，通过它可以有效的避免内存碎片，提高内存的利用率

在我们自己实现的STL中，只实现了一级空间配置器，因为它的实现相对简单
在讨论分配器之前，和大家分享一下标准化的一些东西

首先是一些统一的接口

1
2
3
4
5
6
7
8
9
10
11
typedef size_t              size_type;
typedef _Tp                 value_type;
typedef value_type*         iterator;
typedef value_type*         pointer;
typedef const value_type*   const_pointer;
typedef const value_type*   const_iterator;
typedef value_type&         reference;
typedef const value_type&   const_reference;
typedef ptrdiff_t           difference_type;
typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;

这些接口是每一个容器都必须提供的，详细的原因在迭代器中解释

其次就是命名规范，所有非标准的东西全部以 “_” 开头

在不考虑内存池和内存分配失败的各种处理策略上，以一个简单的分配器举例

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
template <int _Tp>
class _malloc_alloc
{
public:
    static void *allocate(size_t _n)
    {
        void *_result = malloc(_n);
        return _result;
    }
    static void deallocate(void *_p)
    {
        free(_p);
    }
};

template<typename _TP, typename _Alloc>
class simple_alloc
{
public:
    static _TP* allocate(size_t _n)
    {
        return 0 == _n ? nullptr : (_TP*)_Alloc::allocate(_n * sizeof(_TP));
    }

    static void deallocate(_TP *_p)
    {
        if (nullptr != _p)
            _Alloc::deallocate(_p);
    }
};

typedef _malloc_alloc<0> malloc_alloc;

typedef malloc_alloc alloc;

malloc_alloc提供内存分配和释放，simple_alloc作为对外统一管理调度的接口。

成员的构造与析构

从上面大家可以看到，进行内存分配的时候我们调用的底层函数是malloc。众所周知，在c++中，malloc分配的空间是不会调用成员的构造函数的，在STL中是如何解决这一问题的呢。

前面我们提到过，STL中内存分配与成员的构造是分离的，这也是STL提高效率的策略之一。因为对于内置类型来说，并不需要进行构造与析构的，这样，我们将这些类型抽离出来，通过函数重载，使其什么也不做，这样效率就上来了

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
// 对原生类型进行重载, 这些类型不需要析构
inline void _Destroy(char*, char*) {}
inline void _Destroy(int*, int*) {}
inline void _Destroy(long*, long*) {}
inline void _Destroy(float*, float*) {}
inline void _Destroy(double*, double*) {}
inline void _Destroy(wchar_t*, wchar_t*) {}

// 对于范围析构的情况，根据不同的类型采取不同的策略
template<typename _ForwardIter>
void _destroy_aux(_ForwardIter _first, _ForwardIter _last, _false_type)
{
    for (; _first != _last; ++_first)
        destroy(&*_first); // op*()
}
template<typename _ForwardIter>
void _destroy_aux(_ForwardIter _first, _ForwardIter _last, _true_type){}

template <class _Tp>
void destroy(_Tp* _pointer)
{
    _pointer->~_Tp();
}

template<typename _T1, typename _T2>
void construct(_T1 *_p, const _T2 &_val)
{
    new ((void*)_p) _T1(_val);
}

析构我们有了一定的了解，谈到构造，就要详细的了解一下之前所说的uninitialized系列的函数了，通过这一系列的函数，能够非常方便的对成员进行构造

uninitialized_fill

uninitialized_copy

uninitialized_fill_n

这三大函数完成了STL中所有空间的构造

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
// uninitialized_copy
template<typename _InputIter, typename _ForwardIter>
_ForwardIter _uninitialized_copy_aux(_InputIter _first, _InputIter _last, _ForwardIter _result, _false_type)
{
    _ForwardIter _cur = _result;
    for (; _first != _last; ++_first, ++_cur)
        construct(&*_cur, *_first);

    return _cur;
}

template<typename _InputIter, typename _ForwardIter>
_ForwardIter _uninitialized_copy_aux(_InputIter _first, _InputIter _last, _ForwardIter _result, _true_type)
{
    return copy(_first, _last, _result);
}

// uninitialized_fill
template<typename _ForwardIter, typename _Tp>
void _uninitialized_fill_aux(_ForwardIter _first, _ForwardIter _last, const _Tp &_val, _true_type)
{
    fill(_first, _last, _val);
}

template<typename _ForwardIter, typename _Tp>
void _uninitialized_fill_aux(_ForwardIter _first, _ForwardIter _last, const _Tp &_val, _false_type)
{
    _ForwardIter _cur = _first;

    for (; _cur != _last; ++_cur)
        construct(&*_first, _val);
}

// uninitialized_fill_n
template <typename _ForwardIter, typename _Size, typename _Tp>
inline _ForwardIter
_uninitialized_fill_n_aux(_ForwardIter _first, _Size _n, const _Tp& _x, _true_type)
{
    return fill_n(_first, _n, _x);
}

template <typename _ForwardIter, typename _Size, typename _Tp>
inline _ForwardIter
_uninitialized_fill_n_aux(_ForwardIter _first, _Size _n, const _Tp& _val, _false_type)
{
    _ForwardIter _cur = _first;

    for (; _n > 0; --_n, ++_cur)
        construct(&*_cur, _val);

    return _cur;
}

这三个函数的实现都非常简单，具体的功能一眼就能看出

uninitialized_copy是将[first,last)的值拷贝到result中

uninitialized_fill_n是从first开始，填充n个val的值

uninitialized_fill 在区域[first,last)中填充val

上面三个函数都分别有两个版本，会根据该种数据类型生成相应的type(false_type或true_type)，根据不同的type调用不同的函数