EASTL и SGI Hashtable реализация

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

Причина, по которой не использует класс списка [template] для сегментов в этих реализациях, заключается в том, что у них не было односвязного списка, а std::list<T> имеет двойную связь: дополнительная стоимостьненужный обратный указатель с точки зрения времени выполнения и размера будет считаться плохим.C ++ 2011 теперь имеет std::forward_list<T>, что во многом связано с желанием использовать его, например, в хешированном контейнере.Это может поставить вопрос: почему тогда они не добавили односвязный список?Ответ на это также прост: односвязный список не может соответствовать требованиям контейнера к стандарту, и он был оставлен на потом, чтобы сделать соответствующий выбор.