[c++] Random element in a map



Answers

I like James' answer if the map is small or if you don't need a random value very often. If it is large and you do this often enough to make speed important you might be able to keep a separate vector of key values to select a random value from.

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 ];

Of course if the map is really huge you might not be able to store a copy of all the keys like this. If you can afford it though you get the advantage of lookups in logarithmic time.

Question

what is a good way to select a random element from a map? C++. It is my understanding that maps don't have random access iterators. The key is a long long and the map is sparsely populated.







Continuing ryan_s theme of preconstructed maps and fast random lookup: instead of vector we can use a parallel map of iterators, which should speed up random lookup a bit.

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())];



Maybe you should consider Boost.MultiIndex, although note that it's a little too heavy-weighted.




Related



Tags

c++ c++   random   map