std::unordered_map や boost::flat_map などのハッシュマップはほぼ $O(1)$ で探索でき，赤黒木の std::map に比べて探索も走査も速いとされている．
また unordered_map と map の使用は似ており，置換すること自体はさほど難しくない．
では常に map の代わりに unordered_map を使えばいいのかというと，いろいろと問題がある．
まず map は半順序さえ定義しておけば任意のユーザー定義型をキーに使えるが，unordered_map は std::hash の特殊化などが必要になる．
また要素数が少ないときは unordered_map のほうが定数倍が大きく，遅くなることがある．実際，適当な競プロで比較実験したところ，実行時間にはほとんど差がなかった．入力が大きい問題であっても，重複を削除したあとの要素数がさほどでもなく，定数倍の影響が効く可能性がある．競プロではとりあえず map で書いておき，TLE 境界例が出たときだけ考慮すればよいと思う．
さらに VC++ では以下のような罠が存在した．
仮に map を unordered_map に置換する場合，動作テストだけでなくベンチマークが必須．
なおコンテナの検索が不要で，単に（ソートされた）ユニークなリストが欲しいだけであれば，std::vector + std::sort + std::unique のほうが遥かに高速である．
ハッシュテーブル一般については私はほとんど理解していないが，unordered_map より高速なハッシュマップはいくつもあるとのこと．
必要に応じて勉強したい．