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関数を自前で用意すれば、実装依存なくできます