分離チェイン法でハッシュ表のfind関数とinsert関数を実装したい(C++)

Question

C++初学者です。

分離チェイン法でハッシュ表を実装する課題に取り組んでいます。
find関数とinsert関数についてご教授していただきたいことがあります。色々なネットのページを見て自分なりに考えたのですが、あまり進みませんでした。
以下にコードとエラーメッセージを提示させていただきます。

まだあまりC++について深く理解しておらず、的外れなコードを書いてたり質問をしたりしているかもしれませんがどうかよろしくお願いします。

###ソースコード

#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
#include<string>
#include<new>

using namespace std;

class HashEntry {   // key, value をセットで扱う
    int key;
    string value;
    
public:
    HashEntry(int k, string v) { key = k; value = v; }; 
    HashEntry() { key = 0; value = ""; }; 
    
friend class HashSeparate;
};

class HashSeparate {
    list<HashEntry>* table; // HashEntry の list の配列
    int table_size;    // ハッシュ表のサイズ
    // 添字は [0 .. table_size-1] の範囲になる
    int ndata;         // 実際に登録されているデータ数
    
public:
    HashSeparate( int size );
    ~HashSeparate( );
    bool Insert( int key, string value );
    bool Find( int key, string & v ) const;
    void Show() const;
    
private:
    int hash( int key ) const; // ハッシュ関数
};

HashSeparate::HashSeparate( int size ){
  table = new list<HashEntry>[size];
    table_size = size;
    ndata = 0;
}

HashSeparate::~HashSeparate( ){
    delete [] table;
}

// ハッシュ関数の一例．ハッシュ値は [0 .. table_size - 1] になる
int HashSeparate::hash( int key ) const {
    return key % table_size; 
};


bool HashSeparate::Insert( int k , string v ){
    int hi = hash(k); // ハッシュ値，つまり，配列の添字 
    string str;
    if( Find( k, str ) ) // 同じkeyがすでに登録された
        return false;
    else {
      table[hi][k]=v;   //keyを挿入する 
    //(1)ここの書き方が間違っているのでしょうか。
        ndata++; // データ数を更新する
        return true;
    }
}

bool HashSeparate::Find( int k , string & v) const {
    int hi = hash(k); // ハッシュ値
    list<HashEntry> l = table[hi];

    // 同じ key がすでに登録されたかを記録する．exists == true なら登録済み
    bool exists = false;  
    if( !l.empty() ){
        list<HashEntry>::iterator itr;
        for(itr = l.begin(); itr != l.end(); itr++) {
            if (itr->key == k){
                exists = true; // あった
		// (2)ここには何を追加すればいいのでしょうか。
		return true;
                break;
            }
	    else return false; // なかった
        }
    }

    return exists;    
}

//ハッシュ表を表示させる
void HashSeparate::Show() const {
    for(int i = 0 ; i < table_size; i++) {
        list<HashEntry> l = table[i]; 
        if( !l.empty() ){
            list<HashEntry>::iterator itr;
            for(itr = l.begin(); itr != l.end(); itr++) 
                cout << "(" << itr->key << "," << itr->value << "). ";
            cout << endl;
        }
    }
}

int main() {
    HashSeparate lectureDay(3);
    lectureDay.Insert(6, "June 16");
    lectureDay.Insert(7, "June 23");
    lectureDay.Insert(8, "June 30");
    lectureDay.Insert(9, "July 7");
    lectureDay.Show();

    int n = 3;
    string val; 
    if ( !lectureDay.Find(n, val) )
        cout << n << " is not found." << endl;
    else
        cout << n << " is found. value = " << val << endl;

    n = 9;
    if ( !lectureDay.Find(n, val) )
        cout << n << " is not found." << endl;
    else
        cout << n << " is found. value = " << val << endl;
        
    return 0;
}

###エラーメッセージ

bool HashSeparate::Insert(int, std::string)’ 内:
エラー: no match for ‘operator[]’ (operand types are ‘std::list<HashEntry>’ and ‘int’)
       table[hi][k]=v;   //(1)

Answer 1

table[hi] は list なので、table[hi][k] = v; を
table[hi].push_back(HashEntry(k, v)); または
table[hi].emplace_back(k, v); に変更すればいいんじゃないのかな？

追記
質問のコードを見て、修正してみました。

     else {
-      table[hi][k]=v;   //keyを挿入する 
-    //(1)ここの書き方が間違っているのでしょうか。
+		table[hi].emplace_back(k, v);
         ndata++; // データ数を更新する

-    list<HashEntry> l = table[hi];
+    list<HashEntry>& l = table[hi];
 
-    // 同じ key がすでに登録されたかを記録する．exists == true なら登録済み
-    bool exists = false;  
     if( !l.empty() ){
         list<HashEntry>::iterator itr;
         for(itr = l.begin(); itr != l.end(); itr++) {
             if (itr->key == k){
-                exists = true; // あった
-        // (2)ここには何を追加すればいいのでしょうか。
+                v = itr->value;
         return true;
-                break;
             }
-        else return false; // なかった
         }
     }
 
-    return exists;    
+    return false;    
 }

これでいいのでしょうか？

Comments

[Ryuji_T]

返信が大変遅くなり申し訳ございません。ありがとうございます。プログラムはうまくいきました。しかし恐縮ですが、自分はイテレータの意味をまだあまりわかっておらず、「v = itr->value;」の意味を教えていただくことはできますでしょうか。

[kazuma-s]

itr はイテレータで、これを使ってリストの要素を順番に見ていきます。
key が一致する要素が見つかったので、その値の文字列 itr->value を v にコピーします。
v は main の string val への参照ですから、そこに見つかった文字列が入ります。

[Ryuji_T]

理解できました。ありがとうございました。

Answer 2

      table[hi][k]=v;   //keyを挿入する 
    //(1)ここの書き方が間違っているのでしょうか。

間違ってますね。
list<HashEntry>* table; なんだから

table[hi]で得られるのは list<HashEntry>&、listにはoperator[]は定義されていないから
table[hi][k] できない。

Comments

[Ryuji_T]

返信が遅くなってすいません。table[hi]のkにstring型のvalueを入れる操作をしたいのですが、どういうふうに直せばいいのでしょうか。

[episteme]

listの末尾に追加したいのであれば push_back/emplace_back では?

[Ryuji_T]

table[hi].push_back(k);というふうに直したところ、
no matching function for call to ‘std::list<HashEntry>::push_back(int&)’
table[hi].push_back(k);
というエラーが表示されたのですが、型があってないということでしょうか...？

[episteme]

list<HashEntry> なんだから int が push_back できないのは自明では?

[kazuma-s]

HashEntry(int k) { key = k; value = ””; }; というコンストラクタが定義されていれば、int が push_back できるでしょう。でも定義されていませんね。

[Ryuji_T]

episteme様
「list<HashEntry> なんだから int が push_back できないのは自明では?」についてもう少し詳しく教えていただけますか

[Ryuji_T]

kazuma-s様
ありがとうございます。
その方法で試してみたところコンパイルが通りました。
ほかのところを変更せずに(1)の行だけを書き直すことは可能でしょうか。

[episteme]

わからん。てかそこ以外読んでいない。