C++ではハッシュはどのように書けばよいのでしょうか？

質問

配列はできることがわかりましたが、ハッシュは、C++ではどのように記述ふれば良いのでしょうか？

/*

C++ VS2005でハッシュのようなことは可能でしょうか？

*/

int main(void){

/* Perlの場合
%ken = (
"北海道"=>"札幌市",
"宮城県"=>"仙台市",
"東京都"=>"東京(新宿区)",
"愛知県"=>"名古屋市",
"大阪府"=>"大阪市",
"広島県"=>"広島市",
"福岡県"=>"福岡市",
"沖縄県"=>"那覇市",
);

print $ken{"東京都"};
*/

return 0;
}

回答No.1

jacta · ベストアンサー

本当に必要なのは、ハッシュではなく連想配列ですね。
それであれば、std::map クラステンプレートを使うことで実現できます。

std::map<std::string, std::string> ken;
ken["北海道"] = "札幌市";
ken["宮城県"] = "仙台市";
...

std::cout << ken["東京都"] << std::endl;

本当にハッシュが必要であれば、stdext::hash_map クラステンプレートも使えますが非標準です。

回答No.3

mikaemi

すでに、回答がありますが、現在の標準のC++の標準ライブラリにはハッシュ表を実装しているものはありません。連想配列は、バランス木を使った map です。線形順序がつけられる要素であれば map でも十分でしょう。速度的には、よいハッシュ関数があるのならハッシュの方が速いのかもしれませんが、大体は map でも遜色ないスピードがでると思います。

ちなみに、将来、標準になるであろうものは、unordered_map というものです。TR1(technical report)に入っていて、GNU コンパイラなどでは用意されています。ただし、「多バイト文字を basic_string<char> や basic_ostream<char> に扱わせて移植性はあるのか？」という問題はありますけれど（笑）まあ、しかし、perl に比べて、初期設定が面倒ですよねぇ。。
====
#include <tr1/unordered_map>
#include <iostream>
#include <utility>
#include <string>

int main()
{
typedef std::pair<const std::string, std::string> pair;
pair a[] = {
std::make_pair("北海道", "札幌市"),
std::make_pair("宮城県", "仙台市"),
std::make_pair("東京都", "東京(新宿区)"),
std::make_pair("愛知県", "名古屋市"),
std::make_pair("大阪府", "大阪市"),
std::make_pair("広島県", "広島市"),
std::make_pair("福岡県", "福岡市"),
std::make_pair("沖縄県", "那覇市"),
};
pair *a_end = a + sizeof a / sizeof a[0];
std::tr1::unordered_map<std::string, std::string> hm(a, a_end);

std::cout << hm["北海道"] << '\n';
std::cout << hm["沖縄県"] << '\n';
}
===
% ./a.out
札幌市
那覇市

回答No.2

El-ahrairah

連想配列が必要ならばstd::mapが利用できますが、std::mapに使われているアルゴリズムは二分木です。二分木とハッシュは共に連想配列を実現しますが、どちらを使用するかはメモリ使用量と効率のトレードオフです。また、ハッシュの性能はハッシュ関数次第です。
ハッシュはSTLに含まれないので、ハッシュを使う必要があるならばBoost等サードパーティのライブラリを利用するか自分で実装しましょう。実装方法はB. Stroustrup「プログラミング言語 C++」等が参考になります。