C ++での単純なハッシュマップの実装

StackOverflow https://stackoverflow.com/questions/266206

  •  06-07-2019
  •  | 
  •  

質問

私はC ++を初めて使用します。 Javaでは、ハッシュマップをインスタンス化して使用するのは簡単です。 C ++で簡単な方法でそれを行う方法を知りたいのですが、私は多くの異なる実装を見てきましたが、どれも私には単純に見えませんでした。

役に立ちましたか？

解決

ほとんどのコンパイラは、 std :: hash_map を定義する必要があります。今後の C ++ 0x 標準では、 std :: unordered_map 。その STLページはかなり標準です。 Visual Studioを使用している場合、 Microsoft にはページがありますその上。

クラスをキーとしてではなく値として使用する場合、特別なことをする必要はありません。すべてのプリミティブ型（ int 、 char 、 bool 、さらには char * など）は、「正常に動作する」必要があります。 hash_map のキーとして。ただし、それ以外の場合は、独自のハッシュ関数と等式関数を定義して、「ファンクター」を記述する必要があります。クラスでそれらをラップします。

クラスが MyClass と呼ばれ、すでに定義されていると仮定します：

size_t MyClass::HashValue() const { /* something */ }
bool MyClass::Equals(const MyClass& other) const { /* something */ }

これらのメソッドをオブジェクトでラップするには、2つのファンクターを定義する必要があります。

struct MyClassHash {
  size_t operator()(const MyClass& p) const {
    return p.HashValue();
  }
};

struct MyClassEqual {
  bool operator()(const MyClass& c1, const MyClass& c2) const {
    return c1.Equals(c2);
  }
};

そして、 hash_map / hash_set を次のようにインスタンス化します：

hash_map<MyClass, DataType, MyClassHash, MyClassEqual> my_hash_map;
hash_set<MyClass, MyClassHash, MyClassEqual> my_hash_set;

その後はすべて正常に機能するはずです。

他のヒント

C ++でハッシュマップを使用するのは簡単です！標準のC ++マップを使用するようなものです。 unordered_map のコンパイラ/ライブラリ実装を使用するか、 boost 、または他のベンダー。以下に簡単なサンプルを示します。あなたが与えられたリンクをたどればもっと見つけるでしょう。

#include <unordered_map>
#include <string>
#include <iostream>

int main()
{
    typedef std::tr1::unordered_map< std::string, int > hashmap;
    hashmap numbers;

    numbers["one"] = 1;
    numbers["two"] = 2;
    numbers["three"] = 3;

    std::tr1::hash< std::string > hashfunc = numbers.hash_function();
    for( hashmap::const_iterator i = numbers.begin(), e = numbers.end() ; i != e ; ++i ) {
        std::cout << i->first << " -> " << i->second << " (hash = " << hashfunc( i->first ) << ")" << std::endl;
    }
    return 0;
}

boost.unordered をご覧ください、およびそのデータ構造。

boostの無秩序クラスを試してください。

C ++での単純なハッシュマップ（ハッシュテーブル）の実装をご覧ください。値のペアと個別の連鎖戦略。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top