2

私はC++で単純なハッシュテーブルに取り組んでいます。指定されたキーのハッシュテーブルを挿入、削除、および検索するメソッドがあります。C ++マップSTLコンテナーが私の状況を処理できることは知っていますが、教育演習として自分自身をコーディングしたいと思います。

基本的に、単一の文字列を受け取り、それを他の文字列のベクトルにマップするハッシュテーブルがあります。.Add（）または.Delete（）を呼び出すと期待どおりに動作するため、これはメソッドで簡単に実行できます。ただし、ベクターに対してこれらの操作を実行できるクラスに対して、オーバーロードされた[]演算子を作成したいと思います。

たとえば、ベクターにアイテムを追加したい場合は、次のように記述できます。

     hashTable [string1] = newString;

これにより、新しい文字列がベクターのメンバーとして設定されます。削除と検索についても同じことが言えます。

    hashTable [string1] = "";
    cout << hashTable [string1] << endl;

[]私の主な問題は、この機能を取得するために演算子をオーバーロードする方法がわからないことです。現在、この関数をコーディングしています。基本的な1対1の文字列の一致では機能しますが、文字列とベクトルの一致では機能しません。

    //更新するベクトルへの参照を返し、再割り当てしますか？

        vector＆HashClass :: operator []（const string index）
        {{
           assert（size> = 0 && size <maxSize）;
           ハッシュキー）;
           hashTable[index]を返します;     
        }

私は、後で割り当てる必要があるベクトルリターンを持つという考えに最も固執していると思います。ユーザーとして、私はこの厄介なものを見つけるでしょう。

4

2 に答える 2

2

この質問は、別の質問と密接に関連しています。割り当て以外の存在しない値にアクセスするときに、どのような動作が必要ですか。言い換えれば、あなたが書くときに何をしたいですか：

std::cout << hashTable[string] << std::endl;

そしてstringテーブルに存在しませんか？

考えられるアプローチは2つあります。エラーと見なして例外をスローするか、中止するか、または同様の方法です。または、デフォルトコンストラクターで構築された、または以前にクライアントによって提供された、ある種のデフォルトを返すことができます。

標準マップとunordered_mapは、デフォルトのコンストラクターを使用して新しい値を作成する2番目のアプローチを採用しています。これにより、非常に単純な解決策が可能になりますoperator[]。存在しない場合は挿入し、デフォルト値で初期化します。次に、それへの参照を返します。 hashTable[string] = newString;参照を介して既存の値に割り当てます。

多くのユースケースでは、最初のアプローチが望ましいでしょう（おそらく contains関数を使用するので、何かが見つかるかどうかを事前にテストできますoperator[] ）。最初のアプローチを実装するには、最初にアクセスのタイプごとに特定の機能を実装する必要があります。

template <typename Key, typename Value>
class HashTable
{
public:
    Value* get( Key const& key ) const;
    void set( Key const& key, Value const& value );
};

（私は一般的にこれらを公開します。クライアントによる使用を禁止する理由はありません。）

operator[]次に、次のようにプロキシを返すように定義します。

template <typename Key, typename Value>
class HashTable
{
public:
    class Proxy
    {
        HashTable* myOwner;
        Key myKey;
    public:
        Proxy( HashTable* owner, Key const& key )
            : myOwner( owner )
            , myKey( key )
        {
        }

        operator Value const&() const
        {
            Value const* result = myOwner->get( myKey );
            if ( result == NULL ) {
                //  Desired error behavior here...
            }
            return *result;
        }

        Proxy const& operator==( Value const& value ) const
        {
            myOwner->set( myKey, value );
            return *this;
        }
    };

    Value* get( Key const& key ) const;
    void set( Key const& key, Value const& value );

    Proxy operator[]( Key const& key )
    {
        return Proxy( this, key );
    }
};

したがって、あなたが書くとき：

hashTable[key] = newString;

、プロキシは;operator=を呼び出します。hashTable.put( key, newString )ただし、他のコンテキストでは、プロキシで暗黙の型変換を呼び出します。これにより、が呼び出されますhashTable.get( key )。

場合によっては、デフォルト値を返したい場合でも、このソリューションを使用することが望ましい場合があります。get関数はハッシュテーブルに何も挿入する必要がないため、テーブルがすべてのミスでいっぱいになることはありません。operator[]onをオーバーロードできるconstので、constハッシュテーブルでも使用できます。また、デフォルトのコンストラクターを持つために値型を必要としません。

これには、標準で使用されているソリューションに関して1つの欠点があります。オーバーロードoperator.できないため、プロキシを参照のように動作させることはできません。

hashTable[string].someFunction();

動作しません。回避策operator->はプロキシでオーバーロードすることですが、これはやや不自然な構文につながります。

hashTable[string]->someFunction();  //  But the hash table contains
                                    //  values, not pointers!!!

（参照への暗黙の変換によって誤解されないでください。暗黙の変換はa式では 考慮されませんa.b。）

于 2012-09-28T12:53:29.817 に答える
0

C ++では、[]連想コンテナへのアクセスには通常、デフォルトのセマンティクスが与えられます。つまり、マップされた型のオブジェクトを作成し、キーを使用して挿入し、挿入されたマップされたオブジェクトへの参照を返します。

したがって、次のoperator[]ように実装されます。

    string& HashClass::operator[](const string index)
    {
       assert(size >= 0 && size < maxSize); 
       Hash(key);
       vector &v = hashTable[index];     
       if (index in v) {
          ...
       } else {
          v.push_back(string());
          return v.back();
       }
    }
于 2012-09-28T11:48:39.203 に答える