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

C++ 中的分配器（出于某种原因）应该是类型化的。也就是说，特定的分配器类实例分配特定类型的对象。

但是，由于容器可能需要分配的实际类型可能与容器的值类型（容器逻辑上包含的类型）不同，因此（大多数情况下）要求分配器能够转换为替代的分配器实例，该实例分配对象任何其他类型。这个过程称为“重新绑定”，它是通过调用 来启动的allocator.rebind<U>，其中U是系统想要实际分配的类型。

作为原始分配器的反弹形式的新分配器实例必须从与原始分配器相同的内存池中分配。因此，重新绑定被视为基于类型的更改，而不是真正不同的对象。

标准库容器的实现不允许使用new或delete；它们在分配的内存中的所有动态解除/分配和对象创建/销毁都必须通过分配器执行。

当std::set<T>去插入一个项目时，它会将您的分配器重新绑定到某个节点类型，该节点类型内部包含一个T本身或足够多的正确对齐的存储以创建一个T内部。然后它将使用分配器的接口来创建该节点类型并初始化T它包含的节点类型。std::map有点复杂，但本质上它的节点类型必须存储 aKey和 a Value。

Answer 2

您提供的分配器会反弹到节点结构的类型，然后用于分配节点。

std::allocator（默认）将调用operator new，然后它将执行特定于实现的操作（通常调用malloc）。