c++ - C++ で std::map のランダム キー要素を取得する

Question

c++ で std::map のランダムキーを取得する方法は? イテレータを使用していますか？余分なデータ構造を維持したくない

Answer 1

std::mapイテレータは双方向です。つまり、ランダムなキーを選択するとO(n). 別のデータ構造を使用しない場合、基本的に唯一の選択肢は、std::advanceからのランダムなインクリメントで使用することbegin()です。例えば：

std::map<K, V> m;
auto it = m.begin();
std::advance(it, rand() % m.size());
K random_key = it->first;

（または、にアクセスできる場合はrand()（たとえば）と交換します）。std::mt19939<random>

Answer 2

それはあなたの目的のために何がランダムであるかによって異なります。 std::mapはソートされたコンテナですが、要素番号によるランダム アクセスはサポートしていません。それと一連のキーの知識があれば、マップを掘り下げるポイントをランダムに選択するlower_boundかupper_bound、その近くの要素を見つけることができます。これは、要素とマップ内の他の要素との間のギャップに基づいて要素を選択し続ける傾向があります。つまり、要素/ギャップ自体が事実上ランダムである場合、最初の結果は事実上ランダムであると見なされる可能性がありますが、ランダム要素の繰り返し選択は行われません。均等に分散。

たとえば、キーが大文字で、キー「C」、「O」、「Q」、および「S」がマップにあったとします。AZ からランダムな文字を生成すると、PQR のみが Q の近くにあり、上限または下限を使用すると、それらの 2 つを選択することになるため、Q よりも C、O、または S になる可能性がはるかに高くなります。 4つの要素しかないにもかかわらず、2/26のチャンス。それでも、そもそも C、O、Q、および S の選択にランダム性があった場合、ギャップと選択はランダムであると主張できます。

このようにコンテナに突き刺してから、イテレータのインクリメント/デクリメントの小さな乱数を実行することで、それを少し改善できますが、それでも真にランダムにはなりません。

真にランダムな結果を得るには、リスト、または回避したいセカンダリ インデックス コンテナーを 1 つずつトラバーサルする必要があります。