pobierz losowy element klucza dla std :: map w C++

Question

jak uzyskać losowy klucz dla std :: map w C++? używając iteratora? Nie chcę, aby dodatkowa struktura danych była obsługiwana.

Answer 1

std::map Iteratory są dwukierunkowe, co oznacza, że ​​wybranie losowego klucza będzie miało postać O(n). Bez użycia innej struktury danych, zasadniczo jedynym wyborem jest użycie std::advance z losowym przyrostem z begin(). Na przykład:

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

(lub wymieniając rand() z (na przykład) std::mt19939 jeśli masz dostęp do <random>).

Answer 2

Zależy od tego, co jest losowe dla Twojego celu. std::map to posortowany kontener, ale nie obsługuje dostępu losowego według numeru elementu. Biorąc to pod uwagę i wiedzę o zestawie kluczy, możesz losowo wybrać punkt, w którym chcesz zagłębić się w mapę, używając lower_bound lub upper_bound, aby znaleźć element w pobliżu. Ma to skłonność do utrzymywania elementów zbioru w oparciu o lukę między nimi a innymi elementami na mapie, co oznacza, że ​​początkowy wynik może być uważany za efektywny losowo, jeśli same elementy/luki są faktycznie przypadkowe, powtarzalny wybór losowych elementów nie będzie równomiernie.

Na przykład, powiedzmy, że twoje klucze były dużymi literami, a klawisze "C", "O", "Q" i "S" były na mapie. Jeśli wygenerujesz losową literę od AZ, będziesz bardziej prawdopodobne, że skończysz na C, O lub S niż Q, ponieważ tylko PQR znajduje się w pobliżu Q i używa górnej lub dolnej granicy, którą wybierzesz wybierając dwie z nich, więc szansa 2/26, mimo że są tylko 4 elementy. Mimo to, gdyby na początku była losowość wyboru C, O, Q i S, można by argumentować, że luki i wybór są przypadkowe.

Możesz trochę poprawić, dźgając w taki pojemnik, a następnie wykonując małą losową liczbę przyrostów/deklinacji iteratora, ale nadal nie będzie to naprawdę losowe.

Prawdziwie losowy wynik wymaga przechodzenia jeden po drugim przez listę lub dodatkowego zasobnika indeksującego, którego chcesz uniknąć.