ポインタsizeof(void*) == sizeof(size_t)のハッシュが単に にキャストしているとしsize_tます。私のセットに要素が含まれているかどうかを知りたいのですが、どちらが速くなりますstd::set<void*>かstd::unordered_set<void*>?
仕組みは知っていますstd::setが、 には詳しくありませんstd::unordered_set。まあ、順序付けられていないセットはハッシュとバケットを使用し、交差が発生しない場合 (私の場合)、複雑さはO(1)であることを知っています。しかし、この絶え間ない複雑さがどれほどのものかはわかりません。
コンテナー内の日付の量が適切である場合、私の実際のシナリオでは 100 未満です¹。しかし、私の好奇心は、要素が少ない場合と要素が多い場合の両方に関係しています。
¹ 要素の量が非常に少ないため、a でも十分にstd::vector機能します。
重要な部分は小さな脚注にあると思います。
要素の量が非常に少ないため、 a でも
std::vector問題なく動作します。
std::vectorstd::setは、メモリの連続した領域に要素を割り当てるため、およびよりもキャッシュ フレンドリーですstd::unordered_set(これは標準で義務付けられています)。
また、ルックアップと挿入の複雑さはorstd::vectorよりも悪いですが(それぞれ線形対O(log N)と償却O(1) )、データの局所性と高いキャッシュ ヒット率が計算の複雑さを支配し、パフォーマンスが向上する可能性があります。 .std::setstd::unordered_set
とにかく、一般的に、選択したデータ構造のパフォーマンスへの影響は、それらに対して実行する操作の種類とその頻度にも依存します-これはあなたの投稿では言及されていません.
ただし、いつものように、 1 つにコミットする前にさまざまな代替案を測定し、アプリケーションがパフォーマンス要件を満たすのを妨げるボトルネックを表しているという証拠がない場合は、常により単純な設計を優先してください。
unordered_setset多くの実装よりもキャッシュの局所性が優れています。しかし、あなたのケースでは要素の数が非常に少ないため、 avectorはキャッシュに完全に収まる可能性が高いため、要素を検索する O(n) の複雑さにもかかわらず、より良い選択になります。