《STL源码剖析》笔记——allocator

一个最简单的allocator就可以理解为对new，delete的简单封装,以及对构造函数和析构函数的直接调用。

书中实现

#ifndef _MYALLOC_
#define _MYALLOC_

#include 
#include 
#include 
#include 
#include 

namespace my_alloc
{
    // allocate的实际实现，简单封装new，当无法获得内存时，报错并退出
    template <class T>
    inline T* _allocate(ptrdiff_t size, T*) {
        set_new_handler(0);
        T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));
        if (tmp == 0) {
            cerr << "out of memory" << endl;
            exit(1);
        }
        return tmp;
    }

    // deallocate的实际实现，简单封装delete
    template <class T>
    inline void _deallocate(T* buffer) { ::operator delete(buffer); }

    // construct的实际实现，直接调用对象的构造函数
    template <class T1, class T2>
    inline void _construct(T1* p, const T2& value) { new(p) T1(value); }

    // destroy的实际实现，直接调用对象的析构函数
    template <class T>
    inline void _destroy(T* ptr) { ptr->~T(); }

    template <class T>
    class allocator {
    public:
        typedef T           value_type;
        typedef T*          pointer;
        typedef const T*    const_pointer;
        typedef T&          reference;
        typedef const T&    const_reference;
        typedef size_t      size_type;
        typedef ptrdiff_t   difference_type;

        // 构造函数
        allocator(){ return; }
        template <class U>
        allocator(const allocator<U>& c){}

        // rebind allocator of type U
        template <class U>
        struct rebind { typedef allocator<U> other; };

        // allocate，deallocate，construct和destroy函数均调用上面的实际实现
        // hint used for locality. ref.[Austern],p189
        pointer allocate(size_type n, const void* hint = 0) {
            return _allocate((difference_type)n, (pointer)0);
        }
        void deallocate(pointer p, size_type n) { _deallocate(p); }
        void construct(pointer p, const T& value) { _construct(p, value); }
        void destroy(pointer p) { _destroy(p); }

        pointer address(reference x) { return (pointer)&x; }
        const_pointer const_address(const_reference x) { return (const_pointer)&x; }

        size_type max_size() const { return size_type(UINT_MAX / sizeof(T)); }   
    };
} // end of namespace myalloc
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

自己编写的allocator为vector分配空间

#include 
int main()
{
    std::vector<int, my_alloc::allocator<int> > v;
    // Do something;
    return 0;
}
1
2
3
4
5
6
7

该实现符合STL标准，但是通过不了GCC编译器，原因是SGI STL的allocator并不完全符合STL规范。在gcc9.2.0（mingw-w64 on msys2）里，上面这个“最简单的allocator实现”微小改动（给set_new_handler、cerr、endl三处加上std::）以后是可以编译通过。

SGI STL 默认配置器：std::alloc 详解

上面实现的满足STL标准的allocator只是简单的实现内存配置/释放，即对new和delete的浅包装,SGI中拥有其独特的操作来优化alloc的性能

alloc总体架构

1.构造和析构基本工具construct（）destory
2.空间的配置与释放工具 一级配置器、二级配置器
3.调用系统内存函数

new操作

class Foo{....}
Foo *pf =new Foo;
delete pf
1
2
3

上述代码new操作主要分为两个阶段的操作
1.调用::operator new 配置内存
2.调用构造函数 Foo（）构造对象内容
delete也包含两个操作：
1.调用Foo：~Foo（）将对象析构
2.调用::operator delete 释放内存

STL 中 内存配置操作由 alloc:allocate 负责
内存释放由alloc::deallocate负责，对象构造由::construct 负责，对象析构由
::destroy负责

destroy

直接使用模板编程调用析构函数

template<class T>
inline void destroy(T *pointer)
{
 pointer->~T();
}
1
2
3
4
5

construct

template<class T1,class T2>
inline void construct (T1*p,const T2& value)
{
 new(p) T1(value);
}
1
2
3
4
5

在SGI源码中加入了第二版destroy，主要根据trivial来特化实例

allocate

在SGI中，alloc优化了申请内存和释放的性能。拿vector来举例，申请一个vector时，我们调用alloc为其申请内存空间。

在SGI中将alloc分为一级适配器和二级适配器，以应用于内存大小不同的场景。大于128bytes直接调用一级alloc，小于则使用二级alloc。二级适配器采用维护16个自由链表来分配内存，这主要是为了解决小型区块可能造成的内存碎片问题。

空间释放函数deallocate

该函数首先会判断区块大小，大于128bytes调用一级配置器，小于128bytes就找到对应的自由链表，将区块回收

另外的内存处理工具

STL 定义了5个全局函数，作用容器配置空间。
1.构造函数 construct
2.析构函数 destroy
3.uninitialized_copy ->copy()
4.uninitialized_fill->fill()
5.uninitialized_fill_n->filln()

总结

本文简单介绍了STL组件之一空间配置器，先从标准接口来简要的理解allocator的功能紧接着用templet编程写了一个简单的allocator，然后记录了SGI 中利用traits编程技法来特化提高函数效率，包括一二级适配器优化内存管理的过程，最后介绍了另外几个内存全局函数。本篇文章并未具体细节代码进行讲解是对《STL源码剖析》框架上的总结，若读者对具体代码有兴趣，可以直接读原书。