come ottenere la chiave casuale per std :: map in C++? usando l'iteratore? Non desidero mantenere la struttura dati aggiuntivarecupera l'elemento chiave casuale per std :: map in C++
risposta
std::map
Gli iteratori sono bidirezionali, il che significa che la selezione di una chiave casuale sarà O(n)
. Senza utilizzare un'altra struttura dati, in pratica l'unica scelta è quella di utilizzare std::advance
con un incremento casuale da begin()
. Per esempio:
std::map<K, V> m;
auto it = m.begin();
std::advance(it, rand() % m.size());
K random_key = it->first;
(o sostituendo rand()
con (per esempio) std::mt19939
se si ha accesso a <random>
).
Dipende da cosa è casuale per il tuo scopo. std::map
è un contenitore ordinato, ma non supporta l'accesso casuale per numero di elemento. Detto questo e la conoscenza del set di chiavi, puoi selezionare casualmente un punto in cui scavare nella mappa usando lower_bound
o upper_bound
per trovare un elemento vicino a questo. Questo ha la tendenza a mantenere gli elementi di prelievo in base al divario tra loro e altri elementi nella mappa, il che significa che mentre il risultato iniziale può essere considerato efficacemente casuale se gli elementi/intervalli sono essi stessi effettivamente casuali, la selezione ripetuta di elementi casuali non sarà distribuito uniformemente.
Ad esempio, diciamo che le vostre chiavi erano lettere maiuscole e che i tasti "C", "O", "Q" e "S" erano nella mappa. Se generi una lettera casuale dall'AZ, avresti molta più probabilità di finire su C, O o S rispetto a Q, dato che solo PQR sono vicini a Q e usando il limite superiore o inferiore avresti finito per selezionarne due, quindi 2/26 possibilità nonostante ci siano solo 4 elementi. Tuttavia, se all'inizio vi fosse una certa casualità nella selezione di C, O, Q e S, si potrebbe obiettare che le lacune e le scelte sono casuali.
Si potrebbe migliorare un po 'accoltellando nel contenitore in questo modo, quindi facendo un piccolo numero casuale di incrementi/decrementi dell'iteratore, ma non sarebbe ancora casuale.
Un risultato veramente casuale richiede l'avanzamento di una traversata uno alla volta attraverso l'elenco o il contenitore di indicizzazione secondario che si desidera evitare.
Ora c'è 'std :: next'. :) – erip