c++ - EASTLand SGI哈希表实现

Question

在这两种实现中，容器都存储了一个 node_type 的原始数组。它本质上是一个存储类型 T 的简单链表。 .

// From SGI
template <class _Val>
struct _Hashtable_node
{
  _Hashtable_node* _M_next;
  _Val _M_val;
}; 

出于教育原因，我正在实现自己的版本，我想知道为什么他们不使用 std::list<>桶的容器？为什么要编写已经存在于 std::list<> 中的代码？

我遇到的一个原因可能是 std::list<>是双向链接的，所以有浪费的空间。但是如果使用单个链表呢？为什么不用 bucket_type模板参数，以便可以更改？

Answer 1

在这些实现中不为桶使用列表类[模板]的原因是它们没有单链表和std::list<T>是双重链接的:不必要的反向指针在运行时和大小方面的额外成本将被认为是不好的。 C++2011 现在有 std::forward_list<T>这几乎是出于使用它的愿望，例如在散列容器中。这可能会提出一个问题:他们为什么不添加一个单向链表呢？答案也很简单:单向链表无法满足标准的容器要求，留待以后做出适当的选择。