地图中的随机元素

Question

从地图中选择随机元素的好方法是什么？C++.据我所知,地图没有随机访问迭代器.密钥很长,地图人口稀少.

Answer 1

map<...> MyMap;
iterator item = MyMap.begin();
std::advance( item, random_0_to_n(MyMap.size()) );

Answer 2

如果地图很小或者你不经常需要随机值,我喜欢詹姆斯的回答.如果它很大并且您经常这样做以使速度变得重要,那么您可以保留一个单独的键值向量来从中选择随机值.

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

当然,如果地图真的很大,你可能无法存储这样的所有键的副本.如果你能负担得起,虽然你可以在对数时间内获得查找的优势.

Answer 3

也许绘制一个随机密钥,然后使用lower_bound来查找实际包含的最近密钥.

Answer 4

继续 ryan_s 预构造映射和快速随机查找的主题：我们可以使用迭代器的并行映射代替向量，这应该会加快随机查找的速度。

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