c++ - 编写自定义分配器

Question

我正在尝试编写一个自定义分配器，它为固定数量的元素预分配空间。但是，我在理解要求方面遇到了一些问题。

分配器.h

#pragma once
#ifndef _ALLOCATOR_H
#define _ALLOCATOR_H

template<typename T>
class Allocator
{
public:
    //    typedefs
    typedef T value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;

public:
    //    convert an allocator<T> to allocator<U>
    template<typename U>
    struct rebind
    {
        typedef Allocator<U> other;
    };

public:
    explicit Allocator(void)
    {
        mCurElement = 0;
        mMaxElements = 650000000;
        mBase = reinterpret_cast<pointer>(::operator new(mMaxElements * sizeof(T)));
    }

    virtual ~Allocator(void)
    {
        ::operator delete(mBase);
    }

    explicit Allocator(Allocator const &oOther)
    {
        mCurElement = oOther.mCurElement;
        mMaxElements = oOther.mMaxElements;
        mBase = oOther.mBase;
    }

    template<typename U>
    explicit Allocator(Allocator<U> const &oOther)
    {
        mCurElement = 0;
        mMaxElements = 650000000;
        mBase = oOther.mBase;
    }

    //    address
    pointer address(reference r) { return &r; }
    const_pointer address(const_reference r) { return &r; }

    //    memory allocation
    pointer allocate(size_type nElements, typename std::allocator<void>::const_pointer = 0)
    {
        if (mCurElement > mMaxElements)
            return NULL;

        //pointer p = reinterpret_cast<pointer>(::operator new(cnt * sizeof(T)));
        pointer p = &mBase[mCurElement];
        mCurElement += nElements;
        return p;
    }
    void deallocate(pointer pAddress, size_type)
    {
        //::operator delete(pAddress);
        mCurElement--;
    }

    //    size
    size_type max_size() const
    {
        return std::numeric_limits<size_type>::max() / sizeof(T);
    }

    //    construction/destruction
    void construct(pointer pAddress, const T& oObject)
    {
        new(pAddress) T(oObject);
    }
    void destroy(pointer pAddress)
    {
        pAddress->~T();
    }

    bool operator==(Allocator const&) { return true; }
    bool operator!=(Allocator const& oAllocator) { return !operator==(oAllocator); }

public:
    T *getBase(void) const { return mBase; }

private:
    static usize_t mId;
    T *mBase;
    usize_t mMaxElements;
    usize_t mCurElement;
};


#endif // _ALLOCATOR_H

分配器.cpp

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <sstream>
#include <set>
#include <ctime>

#include "allocator.h"

typedef unsigned int uint_t;
typedef unsigned long long usize_t;
usize_t Allocator<usize_t>::mId;

void testStdAllocator(usize_t nIterations, usize_t nMaxValue)
{
    std::set<usize_t, std::less<usize_t>, Allocator<usize_t>> st;
    std::string id = "Standard Set";

    clock_t start = clock();
    for (usize_t i = 0; i < nIterations; i++)
    {
        usize_t val = (usize_t)(rand() % nMaxValue) + 1;
        if (i % 1000000 == 0)
            std::cout << id << " testing ... " << i << "/" << nIterations << "\r";

        st.insert(val);
    }

    std::cout << id << " Elapsed: " << clock() - start << std::endl;
}

int main(int argc, char *argv[])
{
    usize_t iterations =    650000000;
    usize_t val =           6500000;

    std::cout << "Allocator" << std::endl;

    testStdAllocator(iterations, val);

    return 0;
}

我遇到的问题是:

为什么我需要 template <typename U> ... ？ (我找到了一个例子并对其进行了修改)

当我让它可编译并测试它时 std::set显然创建了分配器的拷贝，所以我必须绕过指针。我可以使用 std::shared_ptr为此，但我真的不明白为什么首先需要这样做。

显然有一些关于代理容器的东西，其中 template <typename U>是必需的，但这又会产生额外的问题，即为(显然)不同的分配器类型传递指针。

所以我希望能在我出错的地方提供一些指示。

Answer 1

当您将分配器传递给 std::set<T, C A> 时它应该有一个 allocate() T的功能allcoating空间对象。然而，std::set<T, C, A> 不会分配任何T目的。相反，它将分配 _Node<T> _Node 所在的对象是一些能够容纳 T 的树节点表示对象，但也包含指向其他节点的合适指针。

分配_Node<T>的对象基于 A 的分配器是需要的。此分配器的类型是从 A::rebind<_Node<T>>::other 获得的并通过将原始分配器对象(或从中创建的对象)作为构造函数参数进行适当初始化。

当然，使用有状态分配器确实假定您使用 C++11 分配器模型。在 C++11 之前，分配器没有适本地构造其他分配器，它们本质上是无状态的。如果您需要使用 C++11 之前的代码但想要处理分配器，您可能需要使用来自 BSL 的容器。 : 这些是分配器感知的，并且可以使用 C++03 编译器进行编译。