如何在自定义容器中正确使用std::allocator？

Question

我正在尝试开发我自己的容器，它将实现散列 table。主要要求是这个容器必须兼容STL。现在我不知道如何为内部容器需要分配内存和初始化对象。

主要问题是如何管理此类容器的密钥？我是否需要为键的哈希函数生成的索引分配另一个存储空间？然后 link 使用节点存储桶将它们存储到实际存储中？

我的容器有模板参数。

template<
    class Key, class T, class Hasher = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Alloc = std::allocator<std::pair<const Key, T>>>
class my_hashtable_v1 {

但是后来我使用这样的内部成员类型来为我的容器分配节点。

template<class T>
struct ch_node_t : hash_node {
    template<class... Args>
    ch_node_t(Args&&... args) : value(std::forward<Args>(args)...) {
    }
    T value;
};

using node_type = ch_node_t<T>;
using storage_allocator_ = typename Alloc::template rebind<node_type>::other;

这样分配节点是否正确？这是来自 insert 方法的一段代码。

auto node = &storage_[slot];
if(!node_traits::is_allocated(*node)) {
  new(node) node_type(v.second);
  node_traits::link_head(*node);
  --freelist_;
}

其中 storage 是指向已分配池的指针。这就是我分配池的方式：

storage_ = storage_allocator_.allocate(size_);

我无法理解的主要问题是如何正确使用 std::allocator<std::pair<const Key, T>> 管理节点密钥？我需要分别创建索引和存储之类的东西吗？

探索 std::unordered_map 代码很难得到这些答案，这就是为什么我在开发自定义容器时向您寻求指导。

Answer 1

为了分配给另一种类型的对象（我们称之为Node）而不是std::allocator_traits<Alloc>::value_type（我们称之为T），其中Alloc可能是自定义分配器类型，您必须 rebind 分配器才能获得类型 Node:

的分配器

using node_alloc_t = std::allocator_traits<Alloc>::rebind_alloc<Node>;
node_alloc_t node_alloc;
node_alloc.allocate(size_);

But how to deal with keys properly? Do I need to create another storage for indexes?

您不一定需要为密钥创建单独的存储空间。您可以将它们存储在节点中。例如，这就是基于树的容器的工作方式。

And my node type don't contain any key.

如果要单独存储密钥，则需要为它们分配存储空间。

如何在自定义容器中正确使用std::allocator？

How to use std::allocator in custom container properly?

c++

memory-management

allocator