Stroustrupのhash_mapの実装が間違っていますか？

Question

私は、Straustrupのhash_mapの実装を見ています。これは彼が

template<class Key, class T, class H = Hash<Key>, class EQ = equal_to<Key>, class A = allocator<T> > 
class hash_map 
{ 
private: // representation 
    struct Entry { 
     key_type key; 
     mapped_type val; 
     Entry* next; // hash overflow link 
     bool erased; 
     Entry(key_type k, mapped_type v, Entry* n) 
     : key(k), val(v), next(n), erased(false) { } 
    }; 

    vector<Entry> v; // the actual entries 
    vector<Entry*> b; // the hash table: pointers into v 
    // ... 

private: 
    float max_load; // keep v.size()<=b.size()*max_load 
    float grow; // when necessary, resize(bucket_count()*grow) 
    size_type no_of_erased; // number of entries in v occupied by erased elements 
    Hasher hash; // hash function 
    key_equal eq; // equality 
    const T default_value; // default value used by [] 
}; 

それを実装していますどのように直感を与えるそして、これは[]

template<class Key, class T, class H = Hash<Key>, class EQ = equal_to<Key>, class A = allocator<T> > 
mapped_type& hash_map::operator[](const key_type& k) 
{ 
    size_type i = hash(k)%b.size(); // hash 
    for(Entry* p = b[i]; p; p = p->next) // search among entries hashed to i 
     if (eq(k,p->key)) { // found 
      if (p->erased) { // re-insert 
       p->erased = false; 
       no_of_erased--; 
       return p->val = default_value; 
      } 
      return p->val; 
     } 

    // not found: 
    if (b.size()*max_load < v.size()) { // if ‘‘too full’’ 
     resize(b.size()*grow); // grow 
     return operator[](k); // rehash 
    } 

    v.push_back(Entry(k,default_value,b[i])); // add Entry 
    b[i] = &v.back(); // point to new element 
    return b[i]->val; 
} 

それでは、iをハッシュするためにマッピングされた3つの要素がある想像してみましょうオペレータの実装ですが、それらのどれもに対応していません新しいキーkを入力したら、別のエントリをリストb[i]に追加する必要があります。代わりに、vベクトルに別のEntryが作成され、b[i]がそのエントリのアドレスに置き換えられます（古い3つのエントリが失われる）。

私は何かが恋しい、または本当に問題がありましたか？

P.S.私はBjarne Straustrup、第3版の "The C++ Programming language"を見ています。この機能は500ページ目にあります。

Answer 1

ハッシュエントリはリンクリストを形成します。

v.push_back(Entry(k,default_value,b[i])); // add Entry 

がb[i]参照してください：新しいエントリが挿入されると、それは（nullの可能性）のエントリのリストの前の頭を与えていますか？

次に、nextフィールドにそのエントリへのリンクを作成します。次にリストの先頭を新しいエントリを指すようにb[i]に移動します。

b[i] = &v.back(); // point to new element