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

Question

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

whatever_rng_type rng2(rng1);

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

其中相同的 RNG 状态用于两个 shuffle。但是，我没有看到任何要求这些洗牌实际上在我检查的标准草案中产生相同的顺序。

std::shuffle必须使用提供的 RNG 作为其随机源，但实现也可能会执行某些操作，例如为不同的元素大小采用不同的代码路径。也许实现可能会对某些类型使用 AVX512 收集/分散指令，而对其他类型使用通用的非矢量化代码路径，这可能会影响结果排序。

使用相同的种子执行两次洗牌实际上是获得相同订单的安全方法吗？我在以后的标准版本或缺陷报告中遗漏了什么吗？

Answer 1

我仔细检查了标准，同意没有任何要求 shuffle 对其随机数的使用做出任何保证。它只是简单地指出：

\n

\n

“如果该函数的实现使用了随机数，则 g 引用的对象应作为实现\xe2\x80\x99s 随机性源。”。

\n

\n

因此，剩下的问题似乎是您是否对任何特定\n实现定义的或观察到的行为感兴趣，或者坚持使用符合标准的便携式解决方案（例如，混洗代理对象或使用数组\nindex)...?

\n

根据您的评论，您似乎反对索引数组建议，因此下面 - 使用自定义迭代器和代理来对向量本身进行洗牌的实现...

\n

（做得不够仔细 - 更多的是概念/插图的证明，所以在使用任何重要的东西之前请仔细检查......）

\n

该方法需要一个move_together对象来保存对向量的引用，然后传递shuffle iterator具有指向该move_together对象的指针和正在处理的向量中的索引的 s。您可以通过放弃move_together对象并直接在迭代器中使用对两个向量的指针或引用来简化这一过程。当迭代器被取消引用时，它们返回支持swapping 的代理对象。

\n

它表面上适用于 GCC 10.2 和 clang 10，但另一个编译器可能有不同的实现std::shuffle，需要更全面的迭代器或代理......

\n

#include <iostream>\n#include <vector>\n#include <random>\n#include <string>\n#include <algorithm>\n\ntemplate <typename T1, typename T2>\nstruct move_together;\n\ntemplate <typename T1, typename T2>\nstruct proxy\n{\n    const move_together<T1, T2>* p_;\n    const size_t i_;\n    proxy& operator=(const proxy& rhs);\n};\n\ntemplate <typename T1, typename T2>\nstruct move_together\n{\n    move_together(std::vector<T1>& v1, std::vector<T2>& v2)\n      : v1_(v1), v2_(v2)\n    { }\n    struct iterator\n    {\n        using iterator_category = std::random_access_iterator_tag;\n        using difference_type = ssize_t;\n        using value_type = proxy<T1, T2>;\n        using pointer = value_type*;\n        using reference = value_type&;\n\n        const move_together* p_;\n        size_t i_;\n        value_type operator*() { return {p_, i_}; }\n        bool operator==(const iterator& rhs) const { return i_ == rhs.i_; }\n        bool operator!=(const iterator& rhs) const { return !(*this == rhs); }\n        difference_type operator-(const iterator& rhs) const\n           { return i_ - rhs.i_; }\n        iterator operator+(int distance) const\n           { return {p_, i_ + distance}; }\n        iterator operator++(int) { auto x = *this; ++i_; return x; }\n        iterator& operator++() { ++i_; return *this; }\n    };\n\n    iterator begin() { return {this, 0}; }\n    iterator end()   { return {this, std::min(v1_.size(), v2_.size())}; }\n    std::vector<T1>& v1_;\n    std::vector<T2>& v2_;\n};\n\ntemplate <typename T1, typename T2>\nproxy<T1, T2>& proxy<T1, T2>::operator=(const proxy<T1, T2>& rhs)\n{\n    p_->v1_[i_] = rhs.p_->v1_[rhs.i_];\n    p_->v2_[i_] = rhs.p_->v2_[rhs.i_];\n}\n\ntemplate <typename T1, typename T2>\nvoid swap(proxy<T1, T2> lhs, proxy<T1, T2> rhs) {\n    using std::swap;\n    swap(lhs.p_->v1_[lhs.i_], rhs.p_->v1_[rhs.i_]);\n    swap(lhs.p_->v2_[lhs.i_], rhs.p_->v2_[rhs.i_]);\n}\n\nint main()\n{\n    std::vector<int> v1{ {1, 2, 3, 4, 5} };\n    std::vector<std::string> v2{ {"one", "two", "three", "four", "five"} };\n\n    std::random_device rd;\n    std::mt19937 rng{rd()};\n\n    move_together m{v1, v2};\n    std::shuffle(m.begin(), m.end(), rng);\n\n    for (const auto& x : v1) std::cout << x << '/';\n    std::cout << '\\n';\n    for (const auto& x : v2) std::cout << x << '/';\n    std::cout << '\\n';\n}\n

\n