recupera l'elemento chiave casuale per std :: map in C++

Question

come ottenere la chiave casuale per std :: map in C++? usando l'iteratore? Non desidero mantenere la struttura dati aggiuntiva

Answer 1

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>).

Answer 2

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.