Élément aléatoire dans une carte

Question

quelle est la bonne façon de sélectionner un élément aléatoire sur une carte? C ++. Je crois comprendre que les cartes n'ont pas d'itérateurs d'accès aléatoire. La clé est longue et longue et la carte est peu peuplée.

Answer 1

map<...> MyMap;
iterator item = MyMap.begin();
std::advance( item, random_0_to_n(MyMap.size()) );

Answer 2

J'aime la réponse de James si la carte est petite ou si vous n'avez pas besoin d'une valeur aléatoire très souvent. S'il est grand et que vous le faites assez souvent pour que la vitesse soit importante, vous pourrez peut-être conserver un vecteur distinct de valeurs clés pour sélectionner une valeur aléatoire.

 map<...> MyMap;
vector<...> MyVecOfKeys; // <-- add keys to this when added to the map.

map<...>::key_type key = MyVecOfKeys[ random_0_to_n(MyVecOfKeys.size()) ];
map<...>::data_type value = MyMap[ key ];
 

Bien sûr, si la carte est vraiment énorme, vous ne pourrez peut-être pas stocker une copie de toutes les clés comme celle-ci. Si vous pouvez vous le permettre, vous obtenez l'avantage des recherches en temps logarithmique.

Answer 3

Peut-être établissez une clé aléatoire, puis utilisez lower_bound pour trouver la clé la plus proche réellement contenue.

Answer 4

Poursuite du thème ryan_s des cartes préconstruites et de la recherche aléatoire rapide: au lieu du vecteur, nous pouvons utiliser une carte parallèle d'itérateurs, ce qui devrait accélérer un peu la recherche aléatoire.

 map<K, V> const original;
...

// construct index-keyed lookup map   
map<unsigned, map<K, V>::const_iterator> fast_random_lookup;
map<K, V>::const_iterator it = original.begin(), itEnd = original.end();
for (unsigned i = 0; it != itEnd; ++it, ++i) {
  fast_random_lookup[i] = it;
}

// lookup random value
V v = *fast_random_lookup[random_0_to_n(original.size())];
 

Answer 5

Si votre carte est statique, au lieu d'une carte, utilisez un vecteur pour stocker vos paires clé / valeur dans l'ordre des clés, une recherche binaire pour rechercher des valeurs en temps log (n) et l'index vectoriel pour obtenir des paires aléatoires en temps constant . Vous pouvez envelopper la recherche vectorielle / binaire pour ressembler à une carte avec une fonction d'accès aléatoire.