C++中的容器空间分配器

在C++中，对象可以粗略的分为两大类，一类是基础对象，它不包含对外部堆上对象的引用，比如普通的编译器内置类型，这类对象的构造函数和析构函数系统可以默认生成且满足要求，拷贝构造函数和拷贝赋值运算符都是默认的对内存的拷贝，这些也大都满足要求。另外一大类是对象包含指针，即包含有指向堆内存对象的引用。所以在涉及到容器的时候，就有必要将对象的内存分配和构造，内存释放和析构分开来，这就是容器的空间分配器的作用，更进一步容器的空间分配器还可以对内存分配进行池化管理从而提升内存使用效率。本文就简单介绍以下为什么容器需要空间分配器，以及一个简单的空间分配器的实现。

一个简单的vector容器类

我们知道在STL中有一个vector类，在这里我们简单实现一个自己的vecor模板类。它在内部使用数组来存储元素，私有成员包括一个指向数组首元素的指针_first，容器中有效元素的后继位置的指针_last，和指向数组空间的后继位置的指针_end，并且支持二倍扩容，代码如下：

template <typename T = int>
class vector
{
public:
    vector(int size = 10) : _first(new T[size])
    {
        _last = _first;
        _end = _first + size;
    }

    ~vector()
    {
        delete[] _first;
        _first = _end = _last = nullptr;
    }

    /// 拷贝构造函数，通过拷贝构造新对象
    vector(const vector<T> &vec)
    {
        int size = vec._end - vec._first;
        _first = new T[size];
        int len = vec._last - vec._first;
        for (size_t i = 0; i != len; ++i)
        {
            _first[i] = vec._first[i];
        }
        _last = _first + len;
        _end = _first + size;
    }

    /// 拷贝赋值运算符，对象已经存在，
    vector<T> &operator=(const vector<T> &vec)
    {
        if (this == &vec)
        {
            return *this;
        }
        delete[] _first;
        int size = vec._end - vec._first;
        _first = new T[size];
        int len = vec._last - vec._first;
        for (size_t i = 0; i != len; ++i)
        {
            _first[i] = vec._first[i];
        }
        _last = _first + len;
        _end = _first + size;
        return *this;
    }

    void push_Back(const T &val)
    {
        if (full())
        {
            resize();
        }
        *_last++ = val;
    }
    void pop_Back()
    {
        if (empty())
            return;
        --_last;
    }

    T back() const
    {
        return *(_last - 1);
    }

    bool full() const
    {
        return _last == _end;
    }

    bool empty() const
    {
        return _first == _last;
    }

    int size() const
    {
        return _last - _first;
    }

private:
    T *_first;
    T *_last; // 指向数组元素中有效元素的后继位置
    T *_end;  // 指向数组空间的后继位置
    void resize()
    {
        int size = _last - _first;
        T *ptemp = new T[size * 2];
        for (size_t i = 0; i != size; ++i)
        {
            ptemp[i] = _first[i];
        }
        delete[] _first;
        _first = ptemp;
        _last = _first + size;
        _end = _first + size * 2;
    }
};

可以看到，在构造函数中，在堆上初始化了一个数组，并将数组的首元素指针放在了_first中，因为有在堆上分配内存，所以需要在析构函数中释放内存，并且需要实现拷贝构造函数和拷贝赋值运算符，这也是big five的内容，只是这里没有实现移动构造函数。

int main()
{
    vector<int> vec;
    for (size_t i = 0; i != 20; ++i)
    {
        vec.push_Back(rand() % 100);
    }
    vec.pop_Back();
    while (!vec.empty())
    {
        std::cout << vec.back() << " ";
        vec.pop_Back();
    }
    std::cout << std::endl;
    return 1;
}

上面这个简化版的vector容器，如果存放的是基本的数据类型，比如int是没有问题的，但如果存放包含有析构函数的对象，特别是那些在堆上分配了内存的对象，则会存在严重的问题。

问题所在

上面的demo，可能不是很能说明问题，下面定义一个简单的名为TestObj的测试对象，在该对象的构造和析构函数中打印一些说明。

class TestObj
{
public:
    TestObj()
    {
        std::cout << "TestObj()" << std::endl;
    }

    TestObj(const TestObj &val)
    {
        std::cout << "TestObj(const TestObj&)" << std::endl;
    }

    ~TestObj()
    {
        std::cout << "~TestObj()" << std::endl;
    }
};

现在将该对象添加到vector容器中：

int main()
{
    TestObj t1, t2, t3;
    std::cout << "--------------------" << std::endl;
    vector<TestObj> vec;
    vec.push_Back(t1);
    vec.push_Back(t2);
    vec.push_Back(t3);
    std::cout << "--------------------" << std::endl;
    vec.pop_Back();
    std::cout << "--------------------" << std::endl;
    return 1;
}

首先实例化了三个对象，然后实例化一个容器类，然后将着三个对象添加到容器中，最后移除一个元素，运行后代码的打印结果如下：

TestObj()
TestObj()
TestObj()
--------------------
TestObj()
TestObj()
TestObj()
TestObj()
TestObj()
TestObj()
TestObj()
TestObj()
TestObj()
TestObj()
--------------------
--------------------
~TestObj()
~TestObj()
~TestObj()
~TestObj()
~TestObj()
~TestObj()
~TestObj()
~TestObj()
~TestObj()
~TestObj()
~TestObj()
~TestObj()
~TestObj()

可以看到，首先，打印的三个构造函数是我们首先实例化的三个对象t1，t2，t3。下面问题来了，当实例化容器类的时候，因为容器默认的长度大小为10，所以在容器实例化时，直接使用new初始化了10个对象，这10个“空”对象，_first和_last指向的是第一个对象，这显然不是我们想要的。

当往容器里面添加元素时，直接将_last指针指向了新添加对象的指针，所以没有调用对象的构造函数，而之前_last所指的先前创建的”空“对象则丢失了。如果这个TestObj对象在堆上创建的对象，则这个对象就会产生内存泄漏。

当从容器里面移除元素时，也没有调用对象的析构函数，只是简单的将_last指针往前移动了一个位置，先前_last所指的对象也被丢弃了。

最后函数调用了三个对象的析构函数和10个容器里的空对象的析构函数。

所以上述容器类vector的最大问题是，在构造函数中，使用了new从而将内存的开辟和对象的构造耦合在一起了；在析构函数中，使用了delete[] 将内存的释放和对象的析构耦合在一起了。而对于容器来说，在初始化的时候，应该做的仅仅是分配内存块，而不用构造对象，只用在往里面添加元素的时候，才在对应的位置_last所指的位置顶点使用用户传进来的对象拷贝构造一个新的对象。在删除元素时，也应该先调用_last对象所指的对象的析构函数，然后再将指针往前移。

综上，所以需要一个空间分配器，来负责内存的开辟和释放，对象的构造和解析。

空间分配器

一个简单的空间分配器实现起来也很简单：

/// 定义容器的空间配置器，
/// 负责内存开辟/内存释放，对象构造/对象解析
template <typename T>
class Allocator
{
public:
    T *allocate(size_t size) // 负责内存开辟
    {
        return (T *)malloc(sizeof(T) * size);
    }
    void deallocate(void *p) // 负责内存释放
    {
        free(p);
    }
    void construct(T *p, const T &val) // 负责对象构造
    {
        new (p) T(val); // 定位New，调用T对象的拷贝构造
    }

    void destroy(T *p) // 负责对象析构
    {
        p->~T(); // 调用p指向的对象的析构函数
    }
};

内存的开辟和释放，使用malloc和free来实现，对象的构造调用对象的构造函数，这里的对象构造需要使用结合容器里面创建的内存地址，所以需要使用到定位new，即在指定的内存位置创建对象。对象释放的时候显示调用对象的析构函数。

上述只是一个简单的空间分配器，在STL中容器的空间分配器是一个比这个更复杂的，带有对象池化功能。有了以上的空间分配器，结合vector模板类，就能实现一个正确的容器类。

改进的vector

要在vector模板类中添加容器分配器，需要添加一个类型位空间分配器的模板参数，这个空间分配器用户可以自己添加实现了那四个方法的分配器（更好的做法时做成抽象类，只要实现了该抽象类的空间分配器都能使用），如果用户不添加自己的实现，则默认使用上述自己实现的空间分配器，代码如下：

/*
容器底层内存开辟，内存释放，对象构造和析构，都通过allocator对象空间配置器实现
*/
template <typename T = int, typename Alloc = Allocator<T>>
class vector
{
public:
    vector(int size = 10, const Alloc &alloc = Allocator<T>()) : _allocator(alloc)
    {
        // 需要把内存开辟和对象构造分开
        //_first = new T[size];
        _first = _allocator.allocate(size);
        _last = _first;
        _end = _first + size;
    }

    ~vector()
    {
        // delete[] _first;
        for (T *p = _first; p != _last; ++p)
        {
            _allocator.destroy(p); // 把_first指针指向的数组的有效元素进行析构操作
        }
        _allocator.deallocate(_first); // 释放堆上数组内存， 当前容器内存释放
        _first = _end = _last = nullptr;
    }

    /// @brief 拷贝构造函数，通过拷贝构造新对象
    /// @param vec
    vector(const vector<T> &vec)
    {
        int size = vec._end - vec._first;
        //_first = new T[size];
        _first = _allocator.allocate(size);
        int len = vec._last - vec._first;
        for (size_t i = 0; i != len; ++i)
        {
            _allocator.construct(_first[i], vec._first[i]);
            // _allocator.construct(_first + i, vec._first[i]);
        }
        _last = _first + len;
        _end = _first + size;
    }

    /// 拷贝赋值运算符，对象已经存在，
    vector<T> &operator=(const vector<T> &vec)
    {
        if (this == &vec)
        {
            return *this;
        }
        // delete[] _first;
        for (T *p = _first; p != _last; ++p)
        {
            _allocator.destroy(p);
        }
        _allocator.deallocate(_first); // 当前容器内存释放

        int size = vec._end - vec._first;
        //_first = new T[size];
        _first = _allocator.allocate(size);
        int len = vec._last - vec._first;
        for (size_t i = 0; i != len; ++i)
        {
            //_first[i] = vec._first[i];
            _allocator.construct(_first[i], vec._first[i]);
        }
        _last = _first + len;
        _end = _first + size;
        return *this;
    }

    void push_Back(const T &val)
    {
        if (full())
        {
            resize();
        }
        // *_last++ = val; //_last指针指向的内存构造一个值为value的对象
        _allocator.construct(_last, val);
        _last++;
    }
    void pop_Back()
    {
        if (empty())
            return;
        // --_last;//不仅需要把last--,还需要析构last指针所指对象的
        --_last;
        _allocator.destroy(_last);
    }

    T back() const
    {
        return *(_last - 1);
    }

    bool full() const
    {
        return _last == _end;
    }

    bool empty() const
    {
        return _first == _last;
    }

    int size() const
    {
        return _last - _first;
    }

private:
    T *_first;
    T *_last;         // 指向数组元素中有效元素的后继位置
    T *_end;          // 指向数组空间的后继位置
    Alloc _allocator; // 定义人容器的空间配置器对象
    void resize()
    {
        int size = _last - _first;
        // T *ptemp = new T[size * 2];
        T *ptemp = _allocator.allocate(size * 2);
        for (size_t i = 0; i != size; ++i)
        {
            // ptemp[i] = _first[i];
            _allocator.construct(ptemp + i, _first[i]);
        }
        // delete[] _first;
        for (T *p = _first; p != _last; ++p)
        {
            _allocator.destroy(p);
        }
        _allocator.deallocate(_first);
        _first = ptemp;
        _last = _first + size;
        _end = _first + size * 2;
    }
};

可以看到:

在构造函数中，不再简单使用new来创建空间和实例化不必要的对象，而只是使用allocator来分配内存空间块，这个空间的大小就是元素类型的大小。_first和_last分别指向数组第一个元素的位置。
在析构函数中，不再是简单的删除数组，而是首先遍历数组的有效元素个数（_first~_last）, 调用allocator的destroy 分别释放这些元素占用的空间，最后释放数组本身的空间。
当添加对象时，不再是简单的将_last指针指向新对象，而是在_last所指的位置，使用传进来的对象，拷贝构造一个新对象，最后将_last后移。
当删除对象时，不再是简单的将_last指针前移，而是将_last前移之后，将_last所指的对象释放。
在拷贝构造函数中，也是首先开辟空间，然后在开辟的空间上构造对象。
在拷贝赋值运算符中，首先判断自赋值，然后首先将当前容器中的有效元素对象逐个进行释放，最后释放数组占用的空间，然后与构造函数一样，从新开辟空间，然后在开辟的空间上构造对象。
扩容函数中，与拷贝复制运算符类似。

经过以上改造，调整代码再次运行：

int main()
{
    TestObj t1, t2, t3;
    std::cout << "--------------------" << std::endl;
    vector<TestObj> vec;
    vec.push_Back(t1);
    vec.push_Back(t2);
    vec.push_Back(t3);
    std::cout << "--------------------" << std::endl;
    vec.pop_Back();
    std::cout << "--------------------" << std::endl;
    return 1;
}

运行结果如下：

TestObj()
TestObj()
TestObj()
--------------------
TestObj(const TestObj&)
TestObj(const TestObj&)
TestObj(const TestObj&)
--------------------
~TestObj()
--------------------
~TestObj()
~TestObj()
~TestObj()
~TestObj()
~TestObj()

可以看到运行结果与我们所料：

前面三个对象是实例化的t1,t2,t3
实例化vector容器时，只是分配了内存块，没有创建任何对象
在往容器添加元素时，调用了对象的拷贝构造函数。
移除元素时，调用了被移除对象的析构函数。
最后离开函数作用域的时候，容器的析构函数被调用，容器内部的有效元素的析构函数被依次调用。

码农兼一个普普通通小青年

一个简单的vector容器类

问题所在

空间分配器

改进的vector