在C++中检索std :: map的随机密钥元素

Question

如何在C++中获取std :: map的随机密钥？使用迭代器？ 我不想要额外的数据结构来维护

Answer 1

std::map迭代器是双向的，这意味着选择一个随机密钥将是O(n)。在不使用其他数据结构的情况下，基本上唯一的选择是使用std::advance，其随机增量为begin()。例如：

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

（或使用（例如）std::mt19939换出rand()如果你有<random>访问）。

Answer 2

这取决于你的目的是随机的。 std::map是一个排序的容器，但不支持按元素编号随机访问。鉴于这一点和关键集合的知识，您可以使用lower_bound或upper_bound来随机选择要在其中查找地图的点，以便在该地点附近找到要素。这有一种趋势，即根据它们与地图中其他元素之间的差距来选择元素，这意味着如果元素/间隙本身是有效的随机元素，重复选择的随机元素将不会是初始结果平均分配。例如，假设您的密钥为大写字母，并且键“C”，“O”，“Q”和“S”在地图中。如果你从AZ生成一个随机字母，你很可能最终选择C，O或S而不是Q，因为只有PQR接近Q并且使用上限或下限，你最终会选择其中的两个，尽管只有4个元素，但仍有2/26的机会。尽管如此，如果选择C，O，Q和S时有一些随机性，那么你可能会认为差距和选择是随机的。

你可以通过像这样刺入容器，然后做一个随机数的迭代器增量/减量来改善，但它仍然不会是真正的随机数。

一个真正随机的结果需要推进一个一个遍历遍历列表或要避免的二级索引容器。