Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

retrieve random key element for std::map in c++

Tags:

c++

std

map

how to get random key for std::map in c++ ? using iterator? I don't want extra data structure to be maintained

like image 736
user1393608 Avatar asked Mar 15 '13 05:03

user1393608


People also ask

How do I find the key of a map in C++?

To check for the existence of a particular key in the map, the standard solution is to use the public member function find() of the ordered or the unordered map container, which returns an iterator to the key-value pair if the specified key is found, or iterator to the end of the container if the specified key is not ...

How do I find the element in std::map?

The C++ function std::map::find() finds an element associated with key k. If operation succeeds then methods returns iterator pointing to the element otherwise it returns an iterator pointing the map::end().

How do you get a random element from a set in C++?

To get a random element from a set first take a random number using rand() function then take a modulas (%) by set size so that our iterator will not go out of bounds. Now, to get random element just iterate idx=rand() % s. size() times to get random element.


2 Answers

std::map iterators are Bidirectional, which means selecting a random key will be O(n). Without using another data structure, basically your only choice is to use std::advance with a random increment from begin(). For example:

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

(Or swapping out rand() with (for example) std::mt19939 if you have access to <random>).

like image 130
Yuushi Avatar answered Oct 05 '22 23:10

Yuushi


It depends what's random for your purpose. std::map is a sorted container, but doesn't support random access by element number. Given that and knowledge of the set of keys, you can randomly select a point at which to dig into the map using lower_bound or upper_bound to find an element near there. This has a tendency to keep picking elements based on the gap between them and other elements in the map, which means while the initial result may be considered effectively random if the elements/gaps are themselves effectively random, repeated selection of random elements will not be evenly distributed.

For example, say your keys were upper case letters, and the keys 'C', 'O', 'Q' and 'S' were in the map. If you generate a random letter from A-Z, you'd be much more likely to end up on C, O or S than Q, as only PQR are near Q and using upper or lower bound you'd end up selecting two of those, so 2/26 chance despite there being only 4 elements. Still, if there was some randomness to the selection of C, O, Q and S to begin with, you could argue that that the gaps and choice are random.

You could improve on that a little by stabbing into the container like this, then doing a small random number of iterator increments/decrements, but it still wouldn't be truly random.

A truly random result requires advancing a one-by-one traversal through the list, or the secondary indexing container you want to avoid.

like image 44
Tony Delroy Avatar answered Oct 06 '22 00:10

Tony Delroy