はじめに

趣味で AtCoder のコンテストに参加するようになって、中途半端な勉強した結果、逆に実装が雑になってしまっている部分もあります。

特に最近、「 昇順ソートされている数列 が作りたいなぁ。とりあえず std::set に突っ込んでおこう」程度の発想でコンテナを選んだら、TLEが出てしまって原因の切り分けに苦しむことが複数回ありました。

コンテナ内部のデータ構造を考えれば差はあるだろうけど、言ぅてそんな極端な差はないのでは？という気持ちでいたので、ここらで std::set は重い という話を体感してみようと、テストプログラムを書いて処理時間を計測してみた記録です。

我が家の PC の WSL2
バックグラウンドでもいろいろ動いているので、それほど厳密には測定してません。

測定結果①：構築

ランダムで生成した 64bit整数 $2 \times 10^5$ 個をテキストファイルから読み込んで、昇順ソートされている状態にするまでの処理時間(単位:マイクロ秒)
vector は push_back() でメモリを拡張しています。

case	priority_queue	vector + sort	set
1	118540	143572	215521
2	121401	145315	218956
3	123471	150026	215841
4	119003	151527	211504
5	118323	146019	208502

case	priority_queue	vector	set
1	446	403	34641
2	662	413	33037
3	625	498	33978
4	456	452	32136
5	456	393	33350

重いわ。
せっかくだから std::set が得意なはずのノード削除とか、二分探索の処理時間も測ろうと思ってましたが、打ち切りました。
今後はソートされていてほしい程度の意図で std::set は使わないことにします