c++ - 在 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;

（或者如果您有权访问，则rand()与（例如）交换）。std::mt19939<random>

Answer 2

这取决于您的目的是随机的。 std::map是一个排序容器，但不支持按元素编号随机访问。鉴于这一点以及对一组键的了解，您可以随机选择一个点来挖掘地图，lower_bound或者在该点upper_bound附近找到一个元素。这倾向于根据元素与地图中其他元素之间的间隙来继续选择元素，这意味着如果元素/间隙本身是有效随机的，则初始结果可能被认为是有效随机的，但随机元素的重复选择不会是平均分配。

例如，假设您的键是大写字母，而键“C”、“O”、“Q”和“S”在地图中。如果你从 AZ 生成一个随机字母，你最终会比 Q 更有可能最终出现在 C、O 或 S 上，因为只有 PQR 在 Q 附近并且使用上限或下限你最终会选择其中两个，所以尽管只有 4 个元素，但有 2/26 的机会。不过，如果一开始对 C、O、Q 和 S 的选择有一些随机性，你可以争辩说差距和选择是随机的。

您可以通过像这样插入容器，然后执行少量随机数的迭代器递增/递减来改进这一点，但它仍然不是真正随机的。

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