c++ - O(1) の unordered_set からのランダム要素

Question

O(1) 時間で unordered_set からランダムな要素を取得できると人々が言及しているのを見てきました。私はこれでそうしようとしました:

std::unordered_set<TestObject*> test_set;

//fill with data

size_t index = rand() % test_set.size();
const TestObject* test = *(test_set.begin() + index);

ただし、unordered_set イテレーターは + と整数をサポートしていません。 beginsize_t パラメータを指定できますが、これは要素ではなくバケットのインデックスです。バケットをランダムに選択してから、その中の要素をランダムに選択すると、非常に不均衡なランダム分布になります。

適切な O(1) ランダム アクセスの秘訣は何ですか? 問題がある場合、これは VC++ 2010 にあります。

Answer 1

「ランダムアクセス」の意味は、あなたが言及している場合に使用されていたため、誤解されていると思います。

「ランダムアクセス」はランダム性とは何の関係もありません。これは、「ランダムに」要素にアクセスすることを意味します。つまり、コンテナ内の任意の要素にアクセスします。withなどの要素に直接アクセスするstd::vector::operator[]ことはランダムアクセスですが、コンテナを反復処理することはできません。

これを「ランダムアクセスメモリ」の略であるRAMと比較してください。