map::find()は1回で済ませよう
色々伏せて簡略化しているのですが、先日以下のようなコードを見かけました。
std::map<int, std::string> data{{1, "name1"}, {2, "name2"}};
const int key = 2;
if (data.find(key) == data.end())
{
std::cout << "Not found" << std::endl;
return -1;
}
std::cout << "key: " << key << ", value: " << data[key] << std::endl;
std::map::find でキーを検索して、ヒットしたら、キーに該当する値を取得します。動作的には全然問題ないです。
でも std::map::find の使い方として凄く勿体ないことをしています。せっかく検索をしてキーを見つけたのに、[]オペレーターで値を取得してしまっているので、動作的には2回検索していることになっています。
[]オペレーターは配列で使われるイメージが強いせいなのか、O(1)という定数時間しかかからないと思われがちですが、std::mapは全キーの中で検索する必要があり、キーを内赤黒木を使って保存しているため、実は std::map::find と同じくO(log n)という対数時間かかります。
[]オペレーターなどで沢山アクセスする場合は、std::unordered_map の方がお勧めです。unordered ということで、std::mapと違ってキーがソーティングされていないため、ソーティングが不要な場合しか使えないですが、std::unordered_map はキーをハッシュテーブルを使って保存しているため、findも[]オペレーターも平均処理時間がO(1)です。
しかし、あくまでも平均です。簡単に説明すると、内部ではハッシュ関数を使ってキーをハッシュにマッピングしてからそのハッシュをバケットに保存しているのですが、複数のキーが同じバケットに入ってしまうことがあります。全キーが同じバケットに入ってしまうという最悪のケースでは、そのバケットの中で検索することになるので、処理時間がただのリストと同じくO(n)になってしまいます。
まあ、でも狙っていない限りまずないことです。
話を戻しますが、std::map::find の後に値を取得するのであれば、以下のように std::map::find が返すイテレータを使った方が、O(1)で値を取得できます。
const auto it = data.find(key);
if (it == data.end())
{
std::cout << "Not found\n";
return -1;
}
std::cout << "key: " << it->first << ", value: " << it->second << std::endl;
std::mapのイテレーターをそのまま使うと、ヒットしたstd::pair型のオブジェクトを指しているため、キーをfirstで、それに該当する値をsecondでアクセスするようになりますが、もっと分かりやすくしたい場合は、以下のように構造化束縛でstd::pairを展開し、もっと分かりやすい名前にすることができます。
const auto it = data.find(key);
if (it == data.end())
{
std::cout << "Not found\n";
return -1;
}
auto& [_key, _value] = *it;
std::cout << "key: " << _key << ", value: " << _value << std::endl;
こうするともっと良いstd::map使い方になります。
最近はハードがどんどん強くなっているおかげで、パフォーマンスを重視するプログラム以外は、こういうのはどんどん気にしなくていいようになっていますが、わざわざ最適化しないとしても、こういう勿体ないことは避けよう、という話でした。
Discussion