{"id":4853,"date":"2008-08-28T17:51:00","date_gmt":"2008-08-28T17:51:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/vcblog\/2008\/08\/28\/the-mallocator\/"},"modified":"2019-02-18T18:54:01","modified_gmt":"2019-02-18T18:54:01","slug":"the-mallocator","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/cppblog\/the-mallocator\/","title":{"rendered":"The Mallocator"},"content":{"rendered":"

A common question from programmers who have an intermediate amount of experience with using the STL is, “How do I write an STL allocator?”.  Writing an STL allocator is not especially difficult – only two member functions are interesting, allocate() and deallocate().  However, STL allocators must satisfy a number of other requirements (given by section 20.1.5 of the International Standard for C++, ISO\/IEC 14882:2003), and the code to do so takes roughly 80 editor lines.  Figuring out the code from the requirements can be overwhelming, but once you see the code, it’s easy.<\/font><\/p>\n

\n

 <\/font><\/p>\n<\/p>\n

One thing some programmers try is to derive from std::allocator.  I recommend against this; it’s more trouble than it’s worth.  Looking at std::allocator’s implementation is also painful.<\/font><\/p>\n

\n

 <\/font><\/p>\n<\/p>\n

Therefore, I’ve written an example STL allocator, whose purpose in life is to wrap malloc() and free(), which I’ve imaginatively called Mallocator.  I’ve carefully implemented all of the integer overflow checks and so forth that would be required in real production code.  And I’ve exhaustively commented which parts of Mallocator are boilerplate (common to all, virtually all, or all stateless allocators), and which parts you would have to customize.  Hopefully, this should demystify the implementation of STL allocators:<\/font><\/p>\n

\n

 <\/font><\/p>\n<\/p>\n

\n

 <\/font><\/p>\n<\/p>\n

C:Temp>type mallocator.cpp<\/p>\n

<\/font><\/span><\/p>\n

\/\/ The following headers are required for all allocators.<\/p>\n

<\/font><\/span><\/p>\n

#include <stddef.h>  \/\/ Required for size_t and ptrdiff_t and NULL<\/p>\n

<\/font><\/span><\/p>\n

#include <new>       \/\/ Required for placement new and std::bad_alloc<\/p>\n

<\/font><\/span><\/p>\n

#include <stdexcept> \/\/ Required for std::length_error<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

\/\/ The following headers contain stuff that Mallocator uses.<\/p>\n

<\/font><\/span><\/p>\n

#include <stdlib.h>  \/\/ For malloc() and free()<\/p>\n

<\/font><\/span><\/p>\n

#include <iostream>  \/\/ For std::cout<\/p>\n

<\/font><\/span><\/p>\n

#include <ostream>   \/\/ For std::endl<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

\/\/ The following headers contain stuff that main() uses.<\/p>\n

<\/font><\/span><\/p>\n

#include <list>      \/\/ For std::list<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

template <typename T> class Mallocator {<\/p>\n

<\/font><\/span><\/p>\n

public:<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    \/\/ The following will be the same for virtually all allocators.<\/p>\n

<\/font><\/span><\/p>\n

    typedef T * pointer;<\/p>\n

<\/font><\/span><\/p>\n

    typedef const T * const_pointer;<\/p>\n

<\/font><\/span><\/p>\n

    typedef T& reference;<\/p>\n

<\/font><\/span><\/p>\n

    typedef const T& const_reference;<\/p>\n

<\/font><\/span><\/p>\n

    typedef T value_type;<\/p>\n

<\/font><\/span><\/p>\n

    typedef size_t size_type;<\/p>\n

<\/font><\/span><\/p>\n

    typedef ptrdiff_t difference_type;<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    T * address(T& r) const {<\/p>\n

<\/font><\/span><\/p>\n

        return &r;<\/p>\n

<\/font><\/span><\/p>\n

    }<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    const T * address(const T& s) const {<\/p>\n

<\/font><\/span><\/p>\n

        return &s;<\/p>\n

<\/font><\/span><\/p>\n

    }<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    size_t max_size() const {<\/p>\n

<\/font><\/span><\/p>\n

        \/\/ The following has been carefully written to be independent of<\/p>\n

<\/font><\/s><\/p>\n

        \/\/ the definition of size_t and to avoid signed\/unsigned warnings.<\/p>\n

<\/font><\/span><\/p>\n

        return (static_cast<size_t>(0) – static_cast<size_t>(1)) \/ sizeof(T);<\/p>\n

<\/font><\/span><\/p>\n

    }<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    \/\/ The following must be the same for all allocators.<\/p>\n

<\/font><\/span><\/p>\n

    template <typename U> struct rebind {<\/p>\n

<\/font><\/span><\/p>\n

        typedef Mallocator<U> other;<\/p>\n

<\/font><\/span><\/p>\n

    };<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    bool operator!=(const Mallocator& other) const {<\/p>\n

<\/font><\/span><\/p>\n

        return !(*this == other);<\/p>\n

<\/font><\/span><\/p>\n

    }<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    void construct(T * const p, const T& t) const {<\/p>\n

<\/font><\/span><\/p>\n

        void * const pv = static_cast<void *>(p);<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

        new (pv) T(t);<\/p>\n

<\/font><\/span><\/p>\n

    }<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    void destroy(T * const p) const; \/\/ Defined below.<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    \/\/ Returns true if and only if storage allocated from *this<\/p>\n

<\/font><\/span><\/p>\n

    \/\/ can be deallocated from other, and vice versa.<\/p>\n

<\/font><\/span><\/p>\n

    \/\/ Always returns true for stateless allocators.<\/p>\n

<\/font><\/span><\/p>\n

    bool operator==(const Mallocator& other) const {<\/p>\n

<\/font><\/span><\/p>\n

        return true;<\/p>\n

<\/font><\/span><\/p>\n

    }<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    \/\/ Default constructor, copy constructor, rebinding constructor, and destructor.<\/p>\n

<\/font><\/span><\/p>\n

    \/\/ Empty for stateless allocators.<\/p>\n

<\/font><\/span><\/p>\n

    Mallocator() { }<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    Mallocator(const Mallocator&) { }<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    template <typename U> Mallocator(const Mallocator<U>&) { }<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    ~Mallocator() { }<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    \/\/ The following will be different for each allocator.<\/p>\n

<\/font><\/span><\/p>\n

    T * allocate(const size_t n) const {<\/p>\n

<\/font><\/span><\/p>\n

        \/\/ Mallocator prints a diagnostic message to demonstrate<\/p>\n

<\/font><\/span><\/p>\n

        \/\/ what it’s doing. Real allocators won’t do this.<\/p>\n

<\/font><\/span><\/p>\n

        std::cout << “Allocating ” << n << (n == 1 ? ” object” : “objects”)<\/p>\n

<\/font><\/span><\/p>\n

            << ” of size ” << sizeof(T) << “.” << std::endl;<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

        \/\/ The return value of allocate(0) is unspecified.<\/p>\n

<\/font><\/span><\/p>\n

        \/\/ Mallocator returns NULL in order to avoid depending<\/p>\n

<\/font><\/span><\/p>\n

        \/\/ on malloc(0)’s implementation-defined behavior<\/p>\n

<\/font><\/span><\/p>\n

        \/\/ (the implementation can define malloc(0) to return NULL,<\/p>\n

<\/font><\/span><\/p>\n

        \/\/ in which case the bad_alloc check below would fire).<\/p>\n

<\/font><\/span><\/p>\n

        \/\/ All allocators can return NULL in this case.<\/p>\n

<\/font><\/span><\/p>\n

        if (n == 0) {<\/p>\n

<\/font><\/span><\/p>\n

            return NULL;<\/p>\n

<\/font><\/span><\/p>\n

        }<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

        \/\/ All allocators should contain an integer overflow check.<\/p>\n

<\/font><\/span><\/p>\n

        \/\/ The Standardization Committee recommends that std::length_error<\/p>\n

<\/font><\/span><\/p>\n

        \/\/ be thrown in the case of integer overflow.<\/p>\n

<\/font><\/span><\/p>\n

        if (n > max_size()) {<\/p>\n

<\/font><\/span><\/p>\n

            throw std::length_error(“Mallocator<T>::allocate() – Integer overflow.”);<\/p>\n

<\/font><\/span><\/p>\n

        }<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

        \/\/ Mallocator wraps malloc().<\/p>\n

<\/font><\/span><\/p>\n

        void * const pv = malloc(n * sizeof(T));<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

        \/\/ Allocators should throw std::bad_alloc in the case of memory allocation failure.<\/p>\n

<\/font><\/span><\/p>\n

        if (pv == NULL) {<\/p>\n

<\/font><\/span><\/p>\n

            throw std::bad_alloc();<\/p>\n

<\/font><\/span><\/p>\n

        }<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

        return static_cast<T *>(pv);<\/p>\n

<\/font><\/span><\/p>\n

    }<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    void deallocate(T * const p, const size_t n) const {<\/p>\n

<\/font><\/span><\/p>\n

        \/\/ Mallocator prints a diagnostic message to demonstrate<\/p>\n

<\/font><\/span><\/p>\n

        \/\/ what it’s doing. Real allocators won’t do this.<\/p>\n

<\/font><\/span><\/p>\n

        std::cout << “Deallocating ” << n << (n == 1 ? ” object” : “objects”)<\/p>\n

<\/font><\/span><\/p>\n

            << ” of size ” << sizeof(T) << “.” << std::endl;<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

        \/\/ Mallocator wraps free().<\/p>\n

<\/font><\/span><\/p>\n

        free(p);<\/p>\n

<\/font><\/span><\/p>\n

    }<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    \/\/ The following will be the same for all allocators that ignore hints.<\/p>\n

<\/font><\/span><\/p>\n

    template <typename U> T * allocate(const size_t n, const U * \/* const\nhint *\/) const {<\/p>\n

<\/font><\/span><\/p>\n

        return allocate(n);<\/p>\n

<\/font><\/span><\/p>\n

    }<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    \/\/ Allocators are not required to be assignable, so<\/p>\n

<\/font><\/span><\/p>\n

    \/\/ all allocators should have a private unimplemented<\/p>\n

<\/font><\/span><\/p>\n

    \/\/ assignment operator. Note that this will trigger the<\/p>\n

<\/font><\/span><\/p>\n

    \/\/ off-by-default (enabled under \/Wall) warning C4626<\/p>\n

<\/font><\/span><\/p>\n

    \/\/ “assignment operator could not be generated because a<\/p>\n

<\/font><\/span><\/p>\n

    \/\/ base class assignment operator is inaccessible” within<\/p>\n

<\/font><\/span><\/p>\n

    \/\/ the STL headers, but that warning is useless.<\/p>\n

<\/font><\/span><\/p>\n

private:<\/p>\n

<\/font><\/span><\/p>\n

    Mallocator& operator=(const Mallocator&);<\/p>\n

<\/font><\/span><\/p>\n

};<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

\/\/ A compiler bug causes it to believe that p->~T() doesn’t reference p.<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

#ifdef _MSC_VER<\/p>\n

<\/font><\/span><\/p>\n

    #pragma warning(push)<\/p>\n

<\/font><\/span><\/p>\n

    #pragma warning(disable: 4100) \/\/ unreferenced formal parameter<\/p>\n

<\/font><\/span><\/p>\n

#endif<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

\/\/ The definition of destroy() must be the same for all allocators.<\/p>\n

<\/font><\/span><\/p>\n

template <typename T> void Mallocator<T>::destroy(T * const p) const {<\/p>\n

<\/font><\/span><\/p>\n

    p->~T();<\/p>\n

<\/font><\/span><\/p>\n

}<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

#ifdef _MSC_VER<\/p>\n

<\/font><\/span><\/p>\n

    #pragma warning(pop)<\/p>\n

<\/font><\/span><\/p>\n

#endif<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

int main() {<\/p>\n

<\/font><\/span><\/p>\n

    using namespace std;<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    cout << “Constructing l:” << endl;<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    list<int, Mallocator<int> > l;<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    cout << endl << “l.push_back(1729):” << endl;<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    l.push_back(1729);<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    cout << endl << “l.push_back(2161):” << endl;<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

    l.push_ba<\/font><\/span><\/p><\/p>\n","protected":false},"excerpt":{"rendered":"

A common question from programmers who have an intermediate amount of experience with using the STL is, “How do I write an STL allocator?”.  Writing an STL allocator is not especially difficult – only two member functions are interesting, allocate() and deallocate().  However, STL allocators must satisfy a number of other requirements (given by section […]<\/p>\n","protected":false},"author":289,"featured_media":35994,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[3],"class_list":["post-4853","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-cplusplus","tag-dev"],"acf":[],"blog_post_summary":"

A common question from programmers who have an intermediate amount of experience with using the STL is, “How do I write an STL allocator?”.  Writing an STL allocator is not especially difficult – only two member functions are interesting, allocate() and deallocate().  However, STL allocators must satisfy a number of other requirements (given by section […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts\/4853","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/users\/289"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/comments?post=4853"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts\/4853\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/media\/35994"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/media?parent=4853"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/categories?post=4853"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/tags?post=4853"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}