0

C ++でハッシュテーブルの線形プローブを実装したかったのですが、キーと値のペアは次のようなジェネリック型になります: vector< ペア< キー、値> > (キー、値はジェネリック型です)。

ここで、セルが占有されている場合の線形プローブでは、空のセルが見つかるまでベクトルをトラバースし、そのセルに新しいペアを配置します。

問題は、ジェネリック型では、特定のセルが占有されているかどうかをどのように確認できるかということです。これらの条件は使用できません:

if(key == '\0')//As key is not of type string

また

if(key == 0)//As key is not of type int

では、ベクトル内の特定のセルが空かどうかを確認するにはどうすればよいでしょうか? コンセプトを誤解していた場合は、訂正してください。

4

3 に答える 3

2

ベクトルの要素に意味のあるキーと値があるかどうかを確認できると思います：

if(vector[i] == std::pair<key, value>())
    //empty

または、キーのみを気にする場合

if(vector[i].first == key())
    //empty

keyこのアプローチは、 type のデフォルトのコンストラクターが、「空」または「無効な」キーと見なされるオブジェクトを構築することを前提としています。

于 2016-10-10T08:10:50.773 に答える
0

ハッシュに「デフォルトで構築された」要素を持つ可能性を排除したくない場合は、std::bitset(データ構造の最大サイズが事前にわかっている場合) または のような並列データ構造を構築できますstd::vector<bool>。以下では、 を呼び出しますhas。実際に挿入された有効な要素が含まれているhas[i]場合は true になります。vector[i]

したがって、操作は次のように変更する必要があります。

  • inserti : 次のような位置が見つかるまでベクトルをスキャンし続けます。has[i] == false
  • 位置 i の要素を削除: にhas[i]設定false

お役に立てれば

于 2016-10-10T10:16:00.870 に答える