地图中的随机元素
什么是从地图中select一个随机元素的好方法？ C ++。 这是我的理解是，地图没有随机访问迭代器。 关键是漫长的，地图稀疏。
map<...> MyMap; iterator item = MyMap.begin(); std::advance( item, random_0_to_n(MyMap.size()) ); 我喜欢詹姆斯的答案，如果地图很小，或者你经常不需要随机值。 如果它很大，而且你经常做足够的速度以使速度变得重要，那么你可能会保留一个单独的关键值向量来从中select一个随机值。
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 ];
当然如果地图真的很大，你可能无法存储所有这样的密钥副本。 如果你能负担得起，虽然你得到的对数时间查找的优势。
也许编写一个随机密钥，然后使用lower_boundfind实际包含的最近的密钥。
继续使用预构build映射和快速随机查找的ryan_s主题：代替vector，我们可以使用迭代器的并行映射，这应该加快随机查找的速度。
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())];
如果你的地图是静态的，那么用一个向量来存储键/值对，二进制search在log（n）时间内查找值，向量索引在常量时间内得到随机对。 您可以将vector/二进制search包装为具有随机访问function的地图。
也许你应该考虑Boost.MultiIndex ，尽pipe注意它有点太重了。
这是所有的地图项必须以随机顺序访问的情况。
- 将地图复制到一个vector。
- 洗牌vector。
在伪代码中（它密切地反映了下面的C ++实现）：
import random import time # populate map by some stuff for testing m = dict((i*i, i) for i in range(3)) # copy map to vector v = m.items() # seed PRNG # NOTE: this part is present only to reflect C++ r = random.Random(time.clock()) # shuffle vector random.shuffle(v, r.random) # print randomized map elements for e in v: print "%s:%s" % e, print
在C ++中：
#include <algorithm> #include <iostream> #include <map> #include <vector> #include <boost/date_time/posix_time/posix_time_types.hpp> #include <boost/foreach.hpp> #include <boost/random.hpp> int main() { using namespace std; using namespace boost; using namespace boost::posix_time; // populate map by some stuff for testing typedef map<long long, int> Map; Map m; for (int i = 0; i < 3; ++i) m[i * i] = i; // copy map to vector #ifndef OPERATE_ON_KEY typedef vector<pair<Map::key_type, Map::mapped_type> > Vector; Vector v(m.begin(), m.end()); #else typedef vector<Map::key_type> Vector; Vector v; v.reserve(m.size()); BOOST_FOREACH( Map::value_type p, m ) v.push_back(p.first); #endif // OPERATE_ON_KEY // make PRNG ptime now(microsec_clock::local_time()); ptime midnight(now.date()); time_duration td = now - midnight; mt19937 gen(td.ticks()); // seed the generator with raw number of ticks random_number_generator<mt19937, Vector::iterator::difference_type> rng(gen); // shuffle vector // rng(n) must return a uniformly distributed integer in the range [0, n) random_shuffle(v.begin(), v.end(), rng); // print randomized map elements BOOST_FOREACH( Vector::value_type e, v ) #ifndef OPERATE_ON_KEY cout << e.first << ":" << e.second << " "; #else cout << e << " "; #endif // OPERATE_ON_KEY cout << endl; }
有没有人试过这个？ https://github.com/mabdelazim/Random-Access-Map “用于随机访问地图的C ++模板类，就像std :: map一样，但是可以通过索引随机访问项目，语法是my_map.key（i）和my_map 。数据（ⅰ）”
