【29日目】C++のSTLコンテナを比較してみる

何回か、計算量的にはOKのはずの問題で用いたコンテナの問題でTLEになったことがあったので、各コンテナの機能、実行時間等についてまとめてみた。

vector

一番よく使うやつ。push_backは遅いとか言われるけれど、試した限りは十分高速だったし、基本はこれでいい気がする。固定長の時は配列やarrayの方が高速でよいのかもしれないが、それが原因でTLEになることはなかろうからこれでよい気がする。面倒くさいし

unordered(multi)set, unordered(multi)map

ハッシュテーブル。ランダムアクセスが定数時間でできるのが特徴。ただデメリットも多い。まず遅い。10⁷要素くらい挿入で普通にTLEする。TLEもこいつのせいでなった。あとpair型のようにhash化不可能な型では使えない。あと調べたところによると、ハッシュ値が衝突すると実行スピードが大幅に落ちるらしい。いろいろとダメじゃん。

(multi)set

平衡二分探索木。以前は勝手にソートしてくれて便利、、と思っていたが、どうもハッシュテーブルに負けず遅いらしいと判明した。vectorに挿入してからソートした方が10倍くらい速い。意味わからない。それを知って以来使わなくなった。ただ、クエリ課題とかでいちいちソートしなくちゃいけないときには便利だと思います。

deque

これ便利。大好き。なんて言ったってstackとqueueの役割を両方同時にしてくれるんだもの。速度的にも問題ない。逆に単体のstack, queueってまず使う意味ない。

結論

基本は全部vectorでよい気がする。ハッシュテーブルと平衡二分探索木はやめた方が良い。ここに書いたの以外にもlistとかpriority_queueとかあるけれどまず使ったことないなあ。