C++ 中的随机排列范围迭代器

Question

我希望以随机顺序迭代“范围”{0...n}。

我有一个范围为 {0..n} 的迭代器：

class range
{
private:
    int last;
    int iter;

public:
    range(int end):
        last(end),
        iter(0)
    {}

    // Iterable functions
    const range& begin() const { return *this; }
    const range& end() const { return *this; }

    // Iterator functions
    bool operator!=(const range&) const { return iter < last; }
    bool operator==(const range&) const { return iter == last; }
    void operator++() { ++iter; }
    int operator*() const { return iter; }
};

我希望使用 shuffle 创建它的随机排列，然后我可以在 for 循环中使用它：

range ob_range = range(n_objects);
std::uniform_int_distribution<int> distr(0, 10000);
std::shuffle(ob_range.begin(), ob_range.end(), distr);

for (int i : ob_range)
{

但是我收到一条错误消息，我无法解密：

“struct”中没有名为“difference_type”的类型 std::iterator_traits’

如何修复我的代码？

（请注意，我尝试使用它，我在代码片段中找到了它：

std::random_device rd;
std::mt19937 g(rd());
std::shuffle(ob_range.begin(), ob_range.end(), g);

但我被告知“错误：‘random_device’不是‘std’的成员”）

Answer 1

为了实现在 C++ 中迭代随机排列范围的目标，您需要对代码进行一些调整。关键问题源于这样一个事实：您的

range

类不满足

std::shuffle

所期望的标准 STL 迭代器的要求。具体来说，

std::shuffle

需要随机访问迭代器，但是您的

range

类没有提供随机访问所需的接口，例如

difference_type

，以及通过

operator[]

进行随机访问。

解决此问题的方法如下：

解决方案：

1. 您可以使用

   std::vector<int>

   来存储您的范围并对其进行随机播放。
2. 然后您可以迭代这个打乱后的向量。

这是您的代码的有效更新版本：

#include <iostream>
#include <vector>
#include <algorithm> // for std::shuffle
#include <random>    // for std::random_device, std::mt19937

class range {
private:
    int last;
    std::vector<int> vec; // Store the range

public:
    range(int end) : last(end) {
        // Create a vector containing {0, 1, 2, ..., end-1}
        for (int i = 0; i < last; ++i) {
            vec.push_back(i);
        }
    }

    // Function to return a shuffled version of the range
    std::vector<int> get_shuffled_range() {
        std::random_device rd;  // Initialize random number generator
        std::mt19937 g(rd());   // Use Mersenne Twister engine
        std::shuffle(vec.begin(), vec.end(), g);
        return vec;
    }
};

int main() {
    int n_objects = 10; // Set the number of elements
    range ob_range(n_objects);

    // Get the shuffled range
    std::vector<int> shuffled_range = ob_range.get_shuffled_range();

    // Iterate over the shuffled range
    for (int i : shuffled_range) {
        std::cout << i << " ";
    }

    std::cout << std::endl;

    return 0;
}

说明：

1. range 类： 我们没有创建自定义迭代器，而是将数字存储在

   std::vector<int>

   中，可以轻松地对其进行洗牌和迭代。
2. 改组： 使用

   std::shuffle

   引擎将

   std::mt19937

   函数应用于向量，该引擎以来自

   std::random_device

   的随机数作为种子。
3. 迭代：洗牌后，您可以使用标准的基于范围的 for 循环来迭代数字。

为什么此修复有效：

• std::vector<int>

  满足随机访问迭代器的要求，这是

  std::shuffle

  所期望的。
• 您遇到的错误（

  no type named 'difference_type' in 'struct std::iterator_traits'

  ）是因为您原来的自定义迭代器类没有提供充当随机访问迭代器所需的组件（例如，

  difference_type

  、

  operator[]

  等）。使用

  std::vector<int>

  可以消除这个问题。

现在，运行代码将以随机顺序打印范围

{0, 1, 2, ..., n-1}

。