unordered_map について
unordered_map で辛い思いをしたので twitter でわーわー言ってたらいろいろ勉強になったのでメモします。
まとめ
- 基本的にチェイン法っていうのでやってるっぽい
- vector< list< T > > みたいのをイメージするとわかりやすい
詳細
まとめで書いたように, 基本的には vector< list< T > > というのが全部説明している気がします。
- find() は平均計算量 O(1), 最悪計算量 O(n)
- insert(), delete() も平均計算量 O(1), 最悪計算量 O(n)
- 結局消す, 入れる場所を探さないといけないので find() が必要になる(insert は後ろに追加すれば良くね, と思うかもですが既にキーが入っている可能性があるので調べる必要があります)。vector の各要素はリストなので, その中で insert や delete は O(1) で出来る
そんな感じで計算量についてはイメージできます。結局, 全部最悪計算量が O(n) なので, 競技プログラミングに限った話をすると, CodeForces や SRM のような, hack が出来るコンテスト, 最後まで AC かどうかがわからないコンテストでは使わないほうが無難です。逆に, AtCoder のように提出してすぐ AC かわかるコンテストでは, unordered_map がダメなら map に切り替える, とかできるので使っても良さそうです。
日常的には unordered_map のほうが map より高性能な気がするので unordered_map 一択なんですかね(適当)。
ただ, マジメに考えてみると, 「ホントに O(1) で出来るのか？」という疑問が湧いてきます。
それについては, このスライドがとてもわかりやすかったです。
結局, 平均計算量が O(1) になるように, 裏でいろいろ頑張ってくれている, ということですね！ありがたい。
あ, あとここからは多分です。unordered_map は vector< list< T > > なので, vector のサイズを動的に変えているっぽい(それはスライドにも書いてある)んですが, 多分 vector の大きさは 2 倍ずつにしていけば全体的に見て insert() も O(1) で出来そうです。
