0

我在下面实现的算法是著名的 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;
}

当前的解决方案创建一个临时向量，用于存储相对于迭代器的距离，first并最终result使用这些距离一次性填充数组。不过对我来说它看起来很丑。是否有一些特殊的迭代器构造用于处理不能在输出迭代器上循环多次的事实？

4

2 回答 2

3

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

于 2013-05-10T12:00:39.087 回答
1

你的函数可以做任何它想做的事情。然后，您需要向用户指定如何使用模板化参数。

名称OutputIterator只是一个标识符；它没有从标准中引入任何限制或功能。它是一种文档形式，因此如果您进行第二次传递并将迭代器用作输入，那OutputIterator将是一个误导性的名称。

根据标准，ForwardIterator需要多遍保证，即您可以保留迭代器的先前值并多次读取其引用的对象，并且仍然保持相同的值，并且底层序列仍然存在。这一切似乎对你的目的来说是必要和充分的。所以你可以调用模板参数ForwardIterator。但它仍然只是一个名字。在实现更严格的系统之前，C++ 模板使用鸭子类型。

该标准建议并命名了某些通用接口，但一切正常。

于 2013-05-10T12:08:28.827 回答