c++ - 如何绕过输出迭代器的迭代？

Question

我下面实现的算法是著名的 Robert Floyd 算法，它从总共 N 个数字的数组中返回 M 个随机数。该算法返回一组元素，但在该算法中，您需要循环遍历该结果集，以检查先前找到的元素是否已添加到结果集中。

不可能遍历输出迭代器，因为它在文档中声明输出迭代器只能被取消引用一次。

template<typename Iter, typename RandomGenerator>
Iter random_element(Iter start, Iter end, RandomGenerator& g) {
    if (start == end) return start;
    std::uniform_int_distribution<> dis(0, std::distance(start, end) - 1);
    std::advance(start, dis(g));
    return start;
}

template<typename Iter>
Iter random_element(Iter start, Iter end) {
    static std::random_device rd;
    static std::mt19937 gen(rd());
    return random_element(start, end, gen);
}

//! @brief Algorithm of Robert Floyd.
template<typename InputIterator, typename OutputIterator>
OutputIterator random_n(InputIterator first, InputIterator last, OutputIterator result, size_t number) {
    // "misuse" the glibc functions to enforce the notions conform to the documentation
    typedef typename std::iterator_traits<InputIterator>::value_type ValueType;
    __glibcxx_function_requires(_InputIteratorConcept<InputIterator>);
    __glibcxx_function_requires(_OutputIteratorConcept<OutputIterator, ValueType>);
    __glibcxx_requires_valid_range(first1, last1);

    if (first == last) return result;
    if (number == 0) return result;
    assert (number <= (last - first));

    // create container to store distances, not the value itself, neither the iterator values
    std::vector<size_t> distance;
    InputIterator j = last - number + 1;

    // in the case of number=1, j will need to be the end of the array, so full array is searched
    while (j <= last) {
        InputIterator rand_index = random_element(first,j);
        size_t rand = std::distance(first, rand_index);
        if (std::find(distance.begin(), distance.end(), rand) != distance.end()) {
            distance.push_back(std::distance(first,j) - 1);
        } else {
            distance.push_back(rand);
        }
        ++j;
    }
    // fill result container
    for (size_t i = 0; i < distance.size(); ++i) {
        *result = *(first+distance[i]);
        ++result;
    }
    return result;
}

当前的解决方案创建了一个临时 vector ，用于存储相对于迭代器的距离 first，最后使用这些距离一次性填充 result 数组。虽然我看起来很丑。是否有一些特殊的迭代器构造可用于应对不能在输出迭代器上循环多次的事实？

Answer 1

您可以收紧算法的要求并要求 ForwardIterator 指向输出。