c++ - std::shuffle 的顺序可以依赖于 RNG 之外的任何东西吗？

Question

为了以相同的顺序打乱两个 vector ，很容易做类似的事情

whatever_rng_type rng2(rng1);

std::shuffle(vec1.begin(), vec1.end(), rng1);
std::shuffle(vec2.begin(), vec2.end(), rng2);

其中相同的 RNG 状态用于两个 shuffle。但是，我没有看到任何要求这些洗牌实际上在 standard draft 中产生相同的顺序。我检查了。 std::shuffle必须使用提供的 RNG 作为其随机源，但实现也可能会执行某些操作，例如为不同的元素大小采用不同的代码路径。也许实现可能对某些类型使用 AVX512 收集/分散指令，而对其他类型使用通用的非矢量化代码路径，这可能会影响结果排序。
使用相同的种子执行两次洗牌实际上是获得相同订单的安全方法吗？我在以后的标准版本或缺陷报告中遗漏了什么吗？

Answer 1

我仔细检查了标准并同意没有任何要求 shuffle 对其使用随机数做出任何保证。它简单地说:

"To the extent that the implementation of this function makes use of random numbers, the object referenced by g shall serve as the implementation’s source of randomness.".

所以，剩下的问题似乎是你是否对
任何特定的实现定义或观察到的行为
实现，或将坚持符合标准的可移植
解决方案(例如改组代理对象或使用一组
指数)...？
根据您的评论，您似乎反对索引数组的建议，所以在下面 - 使用自定义迭代器和代理对 vector 本身进行洗牌的实现......
(做得不是很仔细 - 更多的是概念/插图的证明，所以在使用任何重要的东西之前仔细检查......)
该方法需要一个 move_together保持对 vector 的引用的对象，然后传递 shuffle iterator s 具有指向 move_together 的指针对象和正在处理的 vector 中的索引。您可以通过前面的 move_together 来简化这一点。对象并直接在迭代器中具有指向两个 vector 的指针或引用。当迭代器被取消引用时，它们返回然后支持 swap 的代理对象。平。
它表面上适用于 GCC 10.2 和 clang 10，但可能有不同的 std::shuffle 实现。对于另一个需要更完整的迭代器或代理的编译器....

#include <iostream>
#include <vector>
#include <random>
#include <string>
#include <algorithm>

template <typename T1, typename T2>
struct move_together;

template <typename T1, typename T2>
struct proxy
{
    const move_together<T1, T2>* p_;
    const size_t i_;
    proxy& operator=(const proxy& rhs);
};

template <typename T1, typename T2>
struct move_together
{
    move_together(std::vector<T1>& v1, std::vector<T2>& v2)
      : v1_(v1), v2_(v2)
    { }
    struct iterator
    {
        using iterator_category = std::random_access_iterator_tag;
        using difference_type = ssize_t;
        using value_type = proxy<T1, T2>;
        using pointer = value_type*;
        using reference = value_type&;

        const move_together* p_;
        size_t i_;
        value_type operator*() { return {p_, i_}; }
        bool operator==(const iterator& rhs) const { return i_ == rhs.i_; }
        bool operator!=(const iterator& rhs) const { return !(*this == rhs); }
        difference_type operator-(const iterator& rhs) const
           { return i_ - rhs.i_; }
        iterator operator+(int distance) const
           { return {p_, i_ + distance}; }
        iterator operator++(int) { auto x = *this; ++i_; return x; }
        iterator& operator++() { ++i_; return *this; }
    };

    iterator begin() { return {this, 0}; }
    iterator end()   { return {this, std::min(v1_.size(), v2_.size())}; }
    std::vector<T1>& v1_;
    std::vector<T2>& v2_;
};

template <typename T1, typename T2>
proxy<T1, T2>& proxy<T1, T2>::operator=(const proxy<T1, T2>& rhs)
{
    p_->v1_[i_] = rhs.p_->v1_[rhs.i_];
    p_->v2_[i_] = rhs.p_->v2_[rhs.i_];
}

template <typename T1, typename T2>
void swap(proxy<T1, T2> lhs, proxy<T1, T2> rhs) {
    using std::swap;
    swap(lhs.p_->v1_[lhs.i_], rhs.p_->v1_[rhs.i_]);
    swap(lhs.p_->v2_[lhs.i_], rhs.p_->v2_[rhs.i_]);
}

int main()
{
    std::vector<int> v1{ {1, 2, 3, 4, 5} };
    std::vector<std::string> v2{ {"one", "two", "three", "four", "five"} };

    std::random_device rd;
    std::mt19937 rng{rd()};

    move_together m{v1, v2};
    std::shuffle(m.begin(), m.end(), rng);

    for (const auto& x : v1) std::cout << x << '/';
    std::cout << '\n';
    for (const auto& x : v2) std::cout << x << '/';
    std::cout << '\n';
}