はstd :: mapのランダムキー要素をC++で取得します

Question

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

Answer 1

std::mapイテレータは双方向です。つまり、ランダムキーを選択するとO(n)となります。別のデータ構造を使用しない場合、基本的に唯一の選択はbegin()のランダムな増分でstd::advanceを使用することです。たとえば、次のように

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

（それとも、<random>へのアクセス権を持っている場合（例えば）std::mt19939でrand()をスワップアウト）。

Answer 2

これは、あなたの目的に応じてランダムなものに依存します。 std::mapはソートされたコンテナですが、要素番号によるランダムアクセスはサポートされていません。キーセットの知識と知識があれば、lower_boundまたはupper_boundを使用してマップを掘り起こすポイントをランダムに選択して、その近くのエレメントを見つけることができます。これは、それらの要素とマップの他の要素との間のギャップに基づいて要素をピッキングする傾向があります。つまり、要素/ギャップ自体が効果的にランダムであれば、初期結果は効果的にランダムと見なされますが、均等に分散。

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

このようにしてコンテナに刺し込み、小さな反復子の増分/減分を行うことで少し改善できますが、依然として本当にランダムではありません。

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