How standard containers allocates memory for their nodes (internal structures)?

Question

I cannot figure out how std::set and std::map, for example allocate the memory for their nodes if they have allocators of type

std::allocator<Key> 

and

std::allocator<std::pair<const Key, T> > 

respectively. As far as I can guess, there should be a code like this, in std::set, for example:

std::pair<iterator, bool> insert(const value_type& value)
{
    ...
    Node * node = new Node();
    node->value = value;
    ...
    return InsertNode(node);
 }

or

std::pair<iterator, bool> insert(const value_type& value)
{
    ...
    Node * node = new Node();
    node->p_value = a1.allocate(1);
    *(node->p_value) = value;
    ...
    return InsertNode(node);
 }

where Node is some internal structure like red-black tree node, for example.

So the question is how is this Node memory allocated?

Answer 1

Allocators in C++ (for some reason) are expected to be typed. That is, a specific allocator class instance allocates objects of a specific type.

However, because the actual type a container may need to allocate can be different from the container's value type (the type the container logically contains), allocators are (mostly) required to be able to be converted into an alternate allocator instance that allocates objects of any other type. This process is called "rebinding", and it is initiated by invoking allocator.rebind<U>, where U is the type the system wants to actually allocate.

A new allocator instance which is a rebound form of the original allocator must allocate from the same memory pool as the original allocator. Rebinding is therefore treated as a type-based change, not a truly distinct object.

Implementations of standard library containers are not permitted to use new or delete; all of their dynamic de/allocation and object creation/destruction within allocated memory must be performed through the allocator.

When std::set<T> goes to insert an item, it will rebind your allocator to some node-type which internally contains either a T itself or enough properly aligned storage to create a T within. It will then use the allocator's interface to create that node type and initialize the T it contains. std::map is a bit more complicated, but essentially its node type must store a Key and a Value.

Answer 2

The allocator that you provide is rebound to the type of the node structure, and then used to allocate the nodes.

std::allocator (the default) will call operator new, which then will do something implementation-specific (usually calling malloc).