c++ - unordered_set を unordered_map のキーとして保存することをお勧めします

Question

unordered_set を unordered_map のキーとして保存しようとしていますが、それは良い考えですか、それとも std::set を使用してデータを保存し、std::map を使用して std::set をキーとして保存する必要があります。パフォーマンス/ルックアップに適しているのはどれですか?

どんな提案も役に立ちます

Answer 1

多くのデータ構造のパフォーマンス関連の質問と同様に、正確な答えはデータ セットによって異なります。
ルックアップのパフォーマンスのみに関心があることを考慮すると、小さなデータ セットでは通常、コンテナーの順序付けられたバージョンの使用が好まれます。ここで、「データ セット」は、キー タイプ (set と unordered_set) のキー内の要素の平均数を意味します。外側のマップ タイプ (マップと unordered_map) の (set, value_type) アイテムの数。ちなみに、 unordered_map 、 value_type> など、順序付けられたコンテナーと順序付けられていないコンテナーを混在させることを妨げるものは何もありません。
それでも、どちらのコンテナーが優れているかを 100% 確実にする唯一の方法は、実際のデータでこれをプロファイリングすることです。

それを念頭に置いて、ここにいくつかの詳細があります：

• 外側のコンテナーの場合、ハッシュ コンテナーの通常の特性に基づいて、unordered_map を使用するとルックアップのパフォーマンスが向上する可能性が高くなります。ただし、キー コンテナーのハッシュ小なり演算子と関数の比較パフォーマンスに依存する微妙な影響があります。
• キー コンテナーの場合、ルックアップのパフォーマンスは、コンテナーの less-than-operator (外側のコンテナーがマップの場合) またはそのハッシュ関数 (外側のコンテナーが unordered_map の場合) の相対的なパフォーマンスの影響を受けます。

後でこれを測定するためにいくつかの実際のテストを投稿しようとします。