时间戳

首页 > 解决方案 > 标准容器如何为其节点（内部结构）分配内存？

c++ - 标准容器如何为其节点（内部结构）分配内存？

问题描述

我无法弄清楚 std::set 和 std::map 如何为它们的节点分配内存，如果它们具有类型的分配器

std::allocator<Key>

和

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

分别。据我猜测，std::set 中应该有这样的代码，例如：

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

或者

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);
 }

其中 Node 是一些内部结构，例如红黑树节点。

那么问题来了，这个 Node 内存是如何分配的呢？

标签： c++

解决方案

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

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

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

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

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

推荐阅读