c++ - 在恒定时间内从没有严格元素顺序的容器中获取随机元素

Question

我有一个自定义容器，它通过唯一 ID(简单的 int64)提供对其元素的访问。此 ID 不是索引悬停器，因此容器的用户不应该关心内部元素的顺序。

我已经实现了最简单的前向迭代器，它提供了 operator++ 以便能够使用具有基于范围的 for 循环的容器。

但是现在，我想通过生成随机数并使用 std::next 从容器中获取随机元素，所有这些都在常数时间内进行，因此前向迭代器是不够的，因为它的 operator++ 将被调用 N 次，引入线性复杂度。为了实现恒定速度，我必须提供 operator+= 这将使我的前向迭代器成为一种随机访问迭代器(容器能够提供恒定时间访问)。我在这里正确吗？如果是这样，它引入了一个顺序的概念，它并不真正适用于我的容器。

因此，我需要恒定时间的随机访问，但没有像 vector 中那样的严格顺序，例如。我的逻辑错误在哪里？

Answer 1

你的修改策略container::iterator让您访问“随机”元素是单调的。因为您总是会在 0 之间选择一个数字和 container::size() , 并将其添加到 container::begin() , 你需要捕获 container ，不仅仅是一个迭代器

您应该做的是添加一个成员 template< class Generator > container::reference container::random_element( Generator& g ) , 委托(delegate)给 std::uniform_int_distribution 选择元素，然后离开 container::iterator作为ForwardIterator (或者可能是 BidirectionalIterator )。