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

Question

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

- user1393608

Answer 1

std::map 迭代器是双向的，这意味着选择一个随机键将会是 O(n)。不使用其他数据结构，基本上您唯一的选择是使用 begin() 的随机增量以及 std::advance。例如：

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

（或者如果您可以使用，则可以将rand()替换为（例如）std::mt19939）。

- Yuushi

---

现在有了 std::next :) - erip

@erip，你能详细解释一下std::next吗？为什么它会比std::advance更好（或不同）？ - mannyglover

@mannyglover 这已经是几年前的事了，所以有些模糊。我认为这是一种挖苦方式，因为“你唯一的选择是使用std::advance”这个评论在技术上并不完全正确（但实际上确实是正确的选择）。 - erip

请注意，std::advance（和std::next）的复杂度通常是线性的，但如果容器具有随机访问，例如std::vector，则为常数。因此，这是一种非常好的完全通用的方法，可以从容器中获取随机元素而不影响性能。 - jmon12

Answer 2

这取决于你的目的需要什么随机性。 std :: map 是一个排序的容器，但不支持按元素编号进行随机访问。鉴于此并了解键集，您可以使用 lower_bound 或 upper_bound 随机选择要进入地图的点以找到附近的元素。这倾向于基于地图中它们与其他元素之间的差距选择元素，这意味着如果元素/间隙本身有效随机，则初始结果可能被认为是有效随机的，但是重复选择随机元素将不会均匀分布。

例如，假设您的键是大写字母，并且键'C'，'O'，'Q'和'S'在地图中。如果您从A-Z生成随机字母，则很可能会停留在C，O或S上，而不是Q，因为只有PQR接近Q，使用上限或下限您会选择其中两个，因此只有2/26的机会，尽管只有4个元素。不过，如果最初选择C，O，Q和S具有某些随机性，那么您可以认为间隙和选择是随机的。

你可以通过像这样刺入容器，然后进行少量的迭代器增减操作来改进它，但这仍然不是真正的随机。

真正的随机结果需要通过逐个遍历列表或你想要避免的二级索引容器来实现。

- Tony Delroy