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.