ゆき社長

シーゲンガーのお勉強 ゲームプログラマ、ゲーマー、色々!

unordered_map、unordered_multimap

ちょっとわけあって、C++のリファレンスなるものを 生意気にも書いている

そんなわけで、今まで適当に使ってきた STLの勉強にもなって ありがたい

C++11 になって、std::unordered_map、std::unordered_multimap というコンテナが増えた。

std::map 等は、キーの順番にデータが保存されますが(だいたい2分木で実装するようです)

std::unordered_map等は、順番が保障されません。

理由は hash値でやってるのですね。

もちろんメリットは検索速度です

std::map等では sizeが増えると 対数的に検索時間が増えますが

hash値を使っているので 基本的に 定数時間で操作できます

ってこれ、名前が変な名前になってるけど boost::hash_map です。

どうやら、ほかのライブラリとの名前の衝突を避けるために unordered_mapという変な名前になったそうです

ってことでサンプル

#include <iostream>

#include <map>

#include <unordered_map>

using namespace std;

template <class Map>

void print(const char* name, const Map& m)

{

cout << name << " : {";

for (const auto& x : m) {

cout << "[" << x.first << "," << x.second << "], ";

}

cout << "}" << std::endl;

}

int main()

{

map<int, char> m;

m.insert(std::make_pair(30,'a'));

m.insert(std::make_pair(10,'b'));

m.insert(std::make_pair(20,'c'));

m.insert(std::make_pair(40,'d'));

m.insert(std::make_pair(15,'e'));

m.insert(std::make_pair(4,'f'));

unordered_map<int, char> u;

u.insert(std::make_pair(30,'a'));

u.insert(std::make_pair(10,'b'));

u.insert(std::make_pair(20,'c'));

u.insert(std::make_pair(40,'d'));

u.insert(std::make_pair(15,'e'));

u.insert(std::make_pair(4,'f'));

print("m", m);

print("u", u);

}

#実行結果

m : {[4,f], [10,b], [15,e], [20,c], [30,a], [40,d], }

u : {[30,a], [10,b], [4,f], [20,c], [40,d], [15,e], }

std::mapの方は、Keyの値でちゃんとソートされてますが

std::unordered_mapの方は、よくわからない順列ですよね

hash関数は 実装依存なので、コンパイラによって結果が違う可能性があります

私の環境は VisualStudio2012です。

もちろん hash関数を自前で用意すれば、実装依存なくできます