C++ 地图中的随机元素
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/158836/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Random element in a map
提问by Deathbob
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.
从地图中选择随机元素的好方法是什么？C++。我的理解是地图没有随机访问迭代器。钥匙很长很长，地图人烟稀少。
回答by James Curran
map<...> MyMap;
iterator item = MyMap.begin();
std::advance( item, random_0_to_n(MyMap.size()) );
回答by ryan_s
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.
当然，如果地图真的很大，您可能无法像这样存储所有密钥的副本。如果您能负担得起，尽管您可以获得对数时间查找的优势。
回答by Assaf Lavie
Maybe draw up a random key, then use lower_boundto find the closest key actually contained.
也许随机拟定一个key，然后使用lower_bound找到实际包含的最接近的key。
回答by Constantin
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.
继续 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())];
回答by ejgottl
If your map is static, then instead of a map, use a vector to store your key/value pairs in key order, binary search to look up values in log(n) time, and the vector index to get random pairs in constant time. You can wrap the vector/binary search to look like a map with a random access feature.
如果您的地图是静态的，则使用向量代替地图，按键顺序存储键/值对，二分搜索以 log(n) 时间查找值，并使用向量索引以恒定时间获取随机对. 您可以将矢量/二元搜索包装成具有随机访问功能的地图。
回答by Weipeng L
Maybe you should consider Boost.MultiIndex, although note that it's a little too heavy-weighted.
也许您应该考虑Boost.MultiIndex，但请注意它的权重有点过大。
回答by user3259383
Has anyone tried this? https://github.com/mabdelazim/Random-Access-Map"C++ template class for random access map. This is like the std::map but you can access items random by index with syntax my_map.key(i) and my_map.data(i)"
有没有人试过这个？ https://github.com/mabdelazim/Random-Access-Map“随机访问映射的 C++ 模板类。这类似于 std::map，但您可以使用语法 my_map.key(i) 和 my_map 通过索引随机访问项目.data(i)"
回答by Matheus Toniolli
std::random_device dev;
std::mt19937_64 rng(dev());
std::uniform_int_distribution<size_t> idDist(0, elements.size() - 1);
auto elementId= elements.begin();
std::advance(elementId, idDist(rng));
Now elementId is random :)
现在 elementId 是随机的 :)
回答by jfs
Here is the case when allmap items must be access in random order.
这是所有地图项必须以随机顺序访问的情况。
- Copy the map to a vector.
- Shuffle vector.
- 将地图复制到矢量。
- 洗牌向量。
In pseudo-code (It closely reflects the following C++ implementation):
在伪代码中（它密切反映了以下 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
In C++:
在 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;
}
