Как написать свой аллокатор?

Часто пишут что с не-стандартным аллокатором код может работать быстрее, а как вообще написать свой аллокатор?
    

Ответы

Ответ 1

Требования к аллокаторам, и их значения по-умолчанию приведены в главе "Allocato
requirements [allocator.requirements]". В этой же главе приводится пример минимального аллокатора:

template 
struct SimpleAllocator {
    typedef Tp value_type;
    SimpleAllocator(аргументы конструктора);

    template  SimpleAllocator(const SimpleAllocator& other);

    Tp* allocate(std::size_t n);
    void deallocate(Tp* p, std::size_t n);
};

template 
bool operator==(const SimpleAllocator&, const SimpleAllocator&);
template 
bool operator!=(const SimpleAllocator&, const SimpleAllocator&);


Предполагается, что контейнеры обязаны обращаться к аллокатору не напрямую, а чере
шаблон std::allocator_traits, который предоставляет значения по-умолчанию, такие как typedef T* pointer;, и т.п.

Однако существующие реализации стандартных библиотек не везде используют allocator_traits.
По этому если мы попробуем например скомпилировать код
std::basic_string, SimpleAllocator> s;
то мы получим такие ошибки:

/usr/local/bin/../lib/gcc/x86_64-unknown-linux-gnu/4.9.2/../../../../include/c++/4.9.2/bits/basic_string.h:114:41: error: 'rebind' following the 'template' keyword does not refer to a template
  typedef typename _Alloc::template rebind<_CharT>::other _CharT_alloc_type;


или

1>S:\MSVS2013\VC\include\xstring(664): error C2903: 'rebind' : symbol is neithe
a class template nor a function template


В обоих случаях в реализации стандартной библиотеки написано _Alloc::rebind вместо allocator_traits<_Alloc>::rebind.

Таким образом, при написании своего аллокатора, надо смотреть на ошибки компиляции, и при необходимости дописывать нужные члены класса.

Ниже приведен пример Arena аллокатора, который компилируется (VC++2013, g++-4.9.2)

#include 
#include 
#include 
#include 

class Arena {
public:
    Arena() {}
    ~Arena() {
        assert(m_allocations == 0);
    }

    void* allocate(std::size_t n) {
        if (n > m_available) {
            m_chunks.emplace_back(100500);
            m_available = m_chunks.back().size();
            m_memory = &m_chunks.back().front();
        }

        auto mem = m_memory;
        m_available -= n;
        m_memory += n;
        ++m_allocations;
        return mem;
    }
    void deallocate(void* p, std::size_t n) {
        --m_allocations;
        auto mem = (unsigned char*)p;
        if (mem + n == m_memory) {
            m_memory = mem;
            m_available += n;
        }
    }

private:
    std::deque> m_chunks;
    std::size_t m_available = 0;
    unsigned char* m_memory;
    int m_allocations = 0;
};

template 
struct ArenaAllocator {
    using value_type = T;

    using Traits = std::allocator_traits>;

#if !defined _MSC_VER    
    // libstdc++ использует конструктор по умолчанию:
    // __a == _Alloc()
    ArenaAllocator() : m_arena(nullptr) {}

    // libstdc++ требует следующие определения
    using size_type = typename std::allocator::size_type;
    using difference_type = typename std::allocator::difference_type;
    using pointer = typename std::allocator::pointer;
    using const_pointer = typename std::allocator::const_pointer;
    // "reference" не входит Allocator Requirements,
    // но libstdc++ думает что она всегда работает с std::allocator.
    using reference = typename std::allocator::reference;
    using const_reference = typename std::allocator::const_reference;
#endif

    explicit ArenaAllocator(Arena& arena) : m_arena(&arena) {}
    template ArenaAllocator(const ArenaAllocator& other) : m_arena(other.m_arena) {}

    T* allocate(std::size_t n) { return (T*)m_arena->allocate(n * sizeof(T)); }
    void deallocate(T* p, std::size_t n) { m_arena->deallocate(p, n * sizeof(T)); }

    // требуется в VC++ и libstdc++
    template void construct(U* p, Args&&... args) { std::allocator().construct(p, std::forward(args)...); }
    template void destroy(U* p) { std::allocator().destroy(p); }
    template struct rebind { using other = ArenaAllocator; };

    Arena* m_arena;
};

template bool operator==(const ArenaAllocator& lhs, const ArenaAllocator& rhs) { return lhs.m_arena == rhs.m_arena; }
template bool operator!=(const ArenaAllocator& lhs, const ArenaAllocator& rhs) { return !(lhs == rhs); }

#include 
#include 
#include 
#include