google - sparsehash

google codeにて公開されているsparsehashがなかなか速くていいそうです。
http://code.google.com/p/google-sparsehash/

要素アクセスの際のオーバーヘッドが2bits/entry。よく分からんのでこの辺要勉強。

メモリ効率を重視した sparse_hash_map/set
実行速度を重視した dense_hash_map/set
どっちを使ってもC++コンパイラにくっついてくるハッシュや、STLのmapよりいい感じ。
ベンチマークは以下のページとか参照。
http://articles.blog79.fc2.com/blog-entry-35.html
http://d.hatena.ne.jp/berupon/20050507

使い方はSGIのハッシュなんかと同じらしい。
そっちを使ったことが無いからどのくらい同じかは分からない。

導入方法(2008/05/10時点)

sparsehash-xxx/src/google/ の中にヘッダファイルが入ってます。libとかDLLとかは無い。

UNIX系の場合
- そのまま使えばいいようです。
Windowsの場合
- sparsehash-xxx/src/google/sparsehash/sparseconfig.h を、sparsehash-xxx/src/windows/google/sparsehash/sparseconfig.h と置き換えます。
Macの場合
- (´･ω･`)ワカンネ

使い方

#include <google/dense_hash_map>
#include <iostream>
int main(){
    /*
     * インスタンス生成。以下は最低限の設定。
     * テンプレートの部分は map の場合、前から順に
     *  ・Key - ハッシュキーの型
     *  ・T - 中身の型
     *  ・HashFcn - ハッシュ生成に使うクラス型（？）
     *  ・EqualKey - ハッシュ値が被った時の判定に使うクラス型（？）
     *  ・Alloc - アロケータの型（？）
     * こんな感じ。
     * set はまた使った時にでも書きます。
     */
    google::dense_hash_map<char *, int> aiu;
    /*
     * イテレータ生成。
     * 型の指定部分は生成した本体に合わせる。まぁ当たり前ですね。
     */
    google::dense_hash_map<char *, int>::iterator iter;
    /*
     * 次のメソッドは使う前に必ず呼べとのことだそうです。
     * 引数には key_type 型の参照を渡すそうなのですが、
     * key_type型については分からないので説明省略。
     * 分かったらまた何か書きます。
     */
    aiu.set_empty_key(NULL);
    
    aiu["first"] = 123;
    aiu["second"] = 456;
    aiu["third"] = 789;
    
    std::cout << "普通に値を参照" << std::endl;
    std::cout << "first = " << aiu["first"] << std::endl;
    std::cout << "second = " << aiu["second"] << std::endl;
    std::cout << "third = " << aiu["third"] << std::endl;
    
    std::cout << "イテレータのみでの連続参照" << std::endl;
    for(iter = aiu.begin(); iter != aiu.end(); iter++){
        std::cout << iter->first << iter->second << std::endl;
    }
    
    std::cout << "ちょっと回りくどいやり方" << std::endl;
    for(iter = aiu.begin(); iter != aiu.end(); iter++){
        std::cout << iter->first << aiu[iter->first] << std::endl;
    }
    
    return 0;
}