malloc/free based STL allocator

Question

Is there a malloc/free based allocator in the STL? If not, does anyone know of a simple copy/paste one? I need it for a map that must not call new/delete.

Positively

Why can't it call new/delete? They are part of the language (and typically implemented via malloc/free already). – Huygens

Stephan T. Lavavej wrote up "The Mallocator" as an example of a bare-bones allocator to show exactly what's necessary in a custom allocator: blogs.msdn.com/b/vcblog/archive/2008/08/28/the-mallocator.aspx – Barringer

Worth noting that on some platforms, malloc() and free() call new and delete rather than the other way around. – Matherly

@JonathanGrynspan: The standard doesn't allow that (20.4.6/3&4): The functions calloc(), malloc(), and realloc() do not attempt to allocate storage by calling ::operator new(), and The function free() does not attempt to deallocate storage by calling ::operator delete(). (That's not to argue that it hasn't been done, only that doing so violates the requirements of the standard). – Landowner

@JerryCoffin: You're right of course. :) That said, I've worked on systems where the implementation was non-conformant. Tip of the iceberg... – Matherly

Answer 1

First, I'd note that changing the allocator for the map itself won't change the allocation used by the objects stored in the map. For example, if you do something like:

std::map<std::string, int, my_allocator<std::pair<const std::string, int> > m;

The map itself will allocate memory using the specified allocator, but when the std::strings in the map allocate memory, they'll still use the default allocator (which will use new and delete. So, if you need to avoid new and delete in general, you have to ensure that not only the map itself uses the right allocator, but that any objects it stores do the same (I know that's probably stating the obvious, but I've overlooked it, so maybe it's worth mentioning).

With that proviso, on with the code:

#ifndef ALLOCATOR_H_INC_
#define ALLOCATOR_H_INC_

#include <stdlib.h>
#include <new>
#include <limits>

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

    template <class U> struct rebind { typedef allocator<U> other; };
    allocator() throw() {}
    allocator(const allocator&) throw() {}

    template <class U> allocator(const allocator<U>&) throw(){}

    ~allocator() throw() {}

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

    pointer allocate(size_type s, void const * = 0) {
        if (0 == s)
            return NULL;
        pointer temp = (pointer)malloc(s * sizeof(T)); 
        if (temp == NULL)
            throw std::bad_alloc();
        return temp;
    }

    void deallocate(pointer p, size_type) {
        free(p);
    }

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

    void construct(pointer p, const T& val) {
        new((void *)p) T(val);
    }

    void destroy(pointer p) {
        p->~T();
    }
};
}

#endif

And, a little test code:

#include <map>
#include <vector>
#include <iostream>
#include <string>
#include <iterator>
#include "allocator.h"

// Technically this isn't allowed, but it's only demo code, so we'll live with it.
namespace std { 
std::ostream &operator<<(std::ostream &os, std::pair<std::string, int> const &c) { 
    return os << c.first << ": " << c.second;
}
}

int main() { 
    std::map<std::string, int, std::less<std::string>, 
             JVC::allocator<std::pair<const std::string, int> > > stuff;

    stuff["string 1"] = 1;
    stuff["string 2"] = 2;
    stuff["string 3"] = 3;

    std::copy(stuff.begin(), stuff.end(), 
        std::ostream_iterator<std::pair<std::string, int> >(std::cout, "\n"));

    return 0;
}

Landowner

I believe that your answers may contain more uses of ostream_iterator than all the production C++ code written to date. ;-) – Antilogy

numberic_limits is in the <limits> header – Irretentive

@JerryCoffin How do you ensure the std::string's are also allocated using the same mechanism? – Gagliano

@thegreendroid: You can't. The allocator used by a standard container (including string) is defined as part of its type. std::string is a typedef for std::basic_string<chat, std::Allocator<char> >. You can define your own std::basic_string<char, my_allocator>, and that will use the allocator you specify--but it'll also be largely incompatible with most existing string implementations. – Landowner

@JerryCoffin, thanks for the quick reply! That's a bummer that you can't force it to use the same allocator though. Can we not use scoped allocators from C++11 to achieve this? – Gagliano

@thegreendroid: Maybe--I haven't really worked with them, so I'm not sure. – Landowner

Answer 2

Indeed, as @MichaelBurr suggests, Stephen J, Lavavej's 'mallocator' is what you're looking for. I just got updated and prettied-up code for it in this answer by @Arnaud today, do have a look.

Okwu