Constant container (map) - eliminate heap allocation

Question

If I create a static const std::map, it will allocate memory on heap. Following code throws bad_alloc:

#include <iostream>
#include <map>

class A {
public:
    static const std::map<int, int> a;
};

const std::map<int, int> A::a = { { 1, 3} , { 2, 5} };

void* operator new  ( std::size_t count )
{
    throw std::bad_alloc();
}

int
main (void)
{
    for(auto &ai: A::a) {
        std::cout << ai.first << " " << ai.second << "\n";
    }
    return 0;
}

Is it possible to create this constant map somehow without having memory allocation?

Answer 1

As Igor Tandetnik suggested, a custom allocator would do the trick. The following is a quick'n'dirty example of a simple linear allocator, which returns memory slots from a static buffer:

#include <iostream>
#include <map>
#include <cassert>

template <typename T>
class LinearAllocator {
    static constexpr size_t _maxAlloc = 1<<20;
    using Buffer = std::array<T, _maxAlloc>;
    using FreeList = std::array<bool, _maxAlloc>;

    static Buffer _buffer;
    static FreeList _allocated;
public:
    typedef T* pointer;
    typedef T value_type;

    template<typename U>
    struct rebind { typedef LinearAllocator<U> other; };

    pointer allocate(size_t /*n*/, const void *hint=0) {
        for(size_t i = 0; i < _maxAlloc; ++i) {
            if(!_allocated[i]) {
                _allocated[i] = true;
                return &_buffer[i];
            }
        }
        throw std::bad_alloc();
    }

    void deallocate(pointer p, size_t /*n*/) {
        assert(p >= &_buffer[0] && p < &_buffer[_maxAlloc]);
        _allocated[p-&_buffer[0]] = false;
    }

    LinearAllocator() throw() { }
    LinearAllocator(const LinearAllocator &a) throw() { }
    template <class U>                    
    LinearAllocator(const LinearAllocator<U> &a) throw() { }
    ~LinearAllocator() throw() { }
};

template <typename T>
typename LinearAllocator<T>::Buffer LinearAllocator<T>::_buffer;

template <typename T>
typename LinearAllocator<T>::FreeList LinearAllocator<T>::_allocated;

using MyMap = std::map<int, int, std::less<int>,
                       LinearAllocator<std::pair<int,int> > >;

// make sure we notice if new gets called
void* operator new(size_t size) {
    std::cout << "new called" << std::endl; 
}

int main() {
    MyMap m;
    m[0] = 1; m[1] = 3; m[2] = 8;

    for(auto & p : m)
        std::cout << p.first << ": " << p.second << std::endl;

    return 0;
}

Output:

0: 1
1: 3
2: 8

Note that this allocator will only handle requests for single slots at a time. I'm sure you will figure out how to extend it according to your requirements.