EASTL和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>，这在很大程度上是出于使用它的愿望，例如在散列容器中。这可能会提出一个问题:为什么他们不添加一个单链表？这个问题的答案也很简单:单链接列表不能遵循标准的容器要求，它被留给以后做出适当的选择。