How to completely manage heap memory allocation of std containers like map?

Question

I'm interested in using multiple std map<int,int> and I want all of them to allocate the elements from a common memory pool. From what I've read so far, I can use custom allocators such as the Boost pool_alloc to achieve this.

My question is, despite using something like Boost pool_alloc to manage the allocation of the elements themselves, will std map still use little bits of heap memory as some form of container overhead that will NOT be managed by boost pool_alloc? I'm thinking something along the lines of pointer to elements with regards to the use std map itself?

Answer 1

The short version

A map type such as:

typedef std::map<
    int,
    int,
    less<int>,
    boost::pool_allocator<pair<const int, int> >
    > 
    AMapType;

Will do all the allocation it needs as it grows using boost::pool_allocators. Some of the initial structure is likely to be created on the stack. How much and what the exact structure will be though is implementation dependent.

Allocator Rebind

The above is possible through the use of allocator::rebind

All std::allocator conformant allocators (such as boost::pool_allocator) provide a rebind template struct in the form:

template<class U> struct rebind{
   typedef AllocatorType<U> other;
};

This can be used to obtain the same kind of allocator for a different type:

typedef AllocatorOfOther AllocatorType::rebind<ADifferentType>::other;

gcc std::map internal structure

The g++ std::map implementation (I inspected 4.7.3 and 4.1.1) is built purely out of a single node type. This includes the key value pair and the pointers and colour bit needed for the rbTree structure. To allocate this it defines a Node allocator using the rebind struct from the user provided allocator. This is used for all the allocations it does as the map grows. Each new node gets allocated in a single allocation.

The standard

I checked though the C++11 standard and could not find anything specifying how such structure should be allocated. Either I did not find the right part or it is not specified. Not using the user given allocator kind would seem a bit pointless though.