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

이 구현의 버킷리스트 클래스 [템플릿]을 사용하여 하지 이유는 그들이 단일 연결리스트를 가지고 있지 않았고 std::list<T>이 이중으로 연결되어 있다는 것입니다 : 측면에서 불필요한 다시 포인터의 추가 비용 실행 시간과 크기가 나쁜 것으로 간주됩니다. C++ 2011은 이제 std::forward_list<T>을 사용하고 있습니다. 해시 된 컨테이너에서. 이것은 질문을 제기 할 수 있습니다. 왜 그들은 단일 링크 목록을 추가하지 않았습니까? 이것에 대한 대답은 또한 간단합니다 : 단일 연결 목록은 표준의 컨테이너 요구 사항을 따를 수 없으며 나중에 적절한 선택을하도록 남겨졌습니다.