从满足谓词的迭代器的容器中均匀地获取迭代器

Joe Mitchell 发表于 Dev

乔·米切尔

我有一个容器，我想选择一个随机满足谓词的迭代器。如果有助于具体说明，则该容器就是一个地图。

天真的，我会这样说：

std::count_if 获取范围内的元素数。

选择一个随机数btwn0和num_elements-1。

创建一个lambda来构成一个有状态谓词，该谓词计数到随机数，然后仅返回true。

std::find_if 与lambda。

请问这将工作，并且有更好的方法吗？另外，我可以使用count代替count_if，并在断言失败时重新生成数字。如果我认为该谓词大部分是正确的，则可能会很有用，但对于我的目的而言效果不佳。

塞尔奇克

您可以通过将所有谓词为真的迭代器存储在单独的容器中，然后使用随机数从中选择迭代器，来以内存换取性能。这样，您只需要遍历该序列一次（但是，请注意，您仍然需要一个正向迭代器，因为一旦移至下一个元素，存储的输入迭代器就会失效）。例如：

template<typename ForwardIterator, typename Predicate>
  ForwardIterator random_iterator(ForwardIterator first,
                                  ForwardIterator last,
                                  Predicate pred)
{
  // store iterators to elements where the predicate is true
  std::deque<ForwardIterator> store;
  for (; first != last; ++first)
    if pred(*first)
      store.push_back(first);

  // if no element satisfies the predicate, return last
  if (store.size() == 0)
    return last;

  // get a random number in range [0, store.size())
  int rand = get_random_number(store.size());

  // return the corresponding iterator
  return store[rand];
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。