在恒定时间内从没有严格元素顺序的容器中获取随机元素
Obtaining random element from container which doesn't have strict element order in constant time
我有一个自定义容器，它通过唯一 ID（简单的 int64）提供对其元素的访问。这个ID不是index hoverer，所以容器的使用者不应该关心里面元素的顺序。
我已经实现了最简单的前向迭代器，它提供 operator++ 能够使用具有基于范围的 for 循环的容器。
但是现在，我想通过生成随机数并使用 std::next 从容器中获取随机元素，所有这些都在常数时间内进行，因此前向迭代器是不够的，因为它的 operator++ 将被调用 N 次引入线性复杂度。为了实现恒定速度，我必须提供 operator+= 这将使我的前向迭代器成为一种随机访问迭代器（容器能够提供恒定时间访问）。我在这里正确吗？如果是这样，它引入了一个 order 的概念，它并不真正适用于我的容器。
因此，我需要固定时间随机访问，但没有严格的顺序，例如 vector。我的逻辑错在哪里？
您修改 container::iterator 以允许您访问 "random" 元素的策略是单一的。因为您总是会选择 0 和 container::size() 之间的数字，并将其添加到 container::begin()，所以您需要抓住 container，而不仅仅是迭代器 [=19] =]
您应该做的是添加一个成员 template< class Generator > container::reference container::random_element( Generator& g )，委派给 std::uniform_int_distribution to pick the element, and leave container::iterator as a ForwardIterator (or potentially a BidirectionalIterator)。
我有一个自定义容器，它通过唯一 ID（简单的 int64）提供对其元素的访问。这个ID不是index hoverer，所以容器的使用者不应该关心里面元素的顺序。
我已经实现了最简单的前向迭代器，它提供 operator++ 能够使用具有基于范围的 for 循环的容器。
但是现在，我想通过生成随机数并使用 std::next 从容器中获取随机元素，所有这些都在常数时间内进行，因此前向迭代器是不够的，因为它的 operator++ 将被调用 N 次引入线性复杂度。为了实现恒定速度，我必须提供 operator+= 这将使我的前向迭代器成为一种随机访问迭代器（容器能够提供恒定时间访问）。我在这里正确吗？如果是这样，它引入了一个 order 的概念，它并不真正适用于我的容器。
因此，我需要固定时间随机访问，但没有严格的顺序，例如 vector。我的逻辑错在哪里？
您修改 container::iterator 以允许您访问 "random" 元素的策略是单一的。因为您总是会选择 0 和 container::size() 之间的数字，并将其添加到 container::begin()，所以您需要抓住 container，而不仅仅是迭代器 [=19] =]
您应该做的是添加一个成员 template< class Generator > container::reference container::random_element( Generator& g )，委派给 std::uniform_int_distribution to pick the element, and leave container::iterator as a ForwardIterator (or potentially a BidirectionalIterator)。