在c++中使用STL算法同时洗牌两个向量的任何方法?

Question

我正在把一个Java程序移植到c++。我有一段代码可以在Java中同时对两个数组进行排序，它产生了一种方法来返回经过排序的数组的下标，这样就可以用来对另一个数组(相同长度的)进行相应的排序。在c++中，我用以下算法对向量进行洗牌

#include <vector>
#include <algorithm>
#include <random>
#include <iostream>
using namespace std;
int main(void) {
vector<int> A, B;

for (int n=0; n<10; n++) {
A.push_back(n);
B.push_back(n);
}

std::random_device rd;
std::mt19937 gen;
std::uniform_int_distribution<> rnd(0, A.size()-1);
for (int n=0; n<A.size(); n++) {
int m = rnd(gen);
std::swap(A[n], A[m]);
std::swap(B[n], B[m]);
}

for (auto it: A) cout << it << " ";
cout << endl;
for (auto it: B) cout << it << " ";
cout << endl;
return 0;
}

它的工作原理。但我想知道是否有任何STL算法可以同时洗牌两个或多个容器。

Answer 1

edit: Armin删除了他的回答，所以我的回答似乎断章取义了。让我们扩大

tl;dr不，在STL中没有函数对多个容器应用相同的shuffle。STL非常大，但不能做所有事情。对算法的具体要求太多了。你所问的不是通常的做法。

然而，没有什么能阻止你编写自己的算法。例如，您可以复制cppreference.com(第三版)上std::shuffle上显示的算法并对其进行修改。

#include <iterator>
template<class URBG, class RandomIt1, class RandomIt2>
static void SameShuffleToMany(URBG&& g, RandomIt1 first1, RandomIt1 last1, RandomIt2 first2) {
using diff_t = typename std::iterator_traits<RandomIt1>::difference_type;
using distr_t = std::uniform_int_distribution<diff_t>;
using param_t = typename distr_t::param_type;
distr_t D;
diff_t n = last1 - first1;
for (diff_t i = n-1; i > 0; --i) {
diff_t j = D(g, param_t(0, i));
std::swap(first1[i], first1[j]);
std::swap(first2[i], first2[j]);
}
}

哎呀，你甚至可以使用可变模板参数来并行处理两个以上的容器。

然而，正如评论中建议的那样，这个问题有多种解决方案。每个解决方案都有它自己的优点和缺点。我在下面做了一个速度测试。然而，Armin和Jamit的解决方案将需要额外的内存来存储重新排序输出的新索引和目标。

---

老回答

我做了一些比较的工作台代码

#include <benchmark/benchmark.h>
#include <vector>
#include <algorithm>
#include <random>
#include <iostream>
static constexpr auto N = 1000;
static std::vector<int> CreateVector() {
std::vector<int> out;
out.reserve(N);
std::generate_n(back_inserter(out), N,
[gen = std::mt19937(std::random_device{}())] () mutable { return gen();}
);
return out;
}
static void BM_Original(benchmark::State& state) {
auto a = CreateVector();
auto b = a; // elementwise copy
for (auto _ : state) {
std::random_device rd;
std::mt19937 gen(std::random_device{}());
std::uniform_int_distribution<> rnd(0, a.size()-1);
for (int n = 0; n < a.size(); ++n) {
int m = rnd(gen);
std::swap(a[n], a[m]);
std::swap(b[n], b[m]);
}
}
if (!std::equal(cbegin(a), cend(a), cbegin(b)))
std::cout << "Vectors are not equal!n";
}
// Register the function as a benchmark
BENCHMARK(BM_Original);
static void BM_Jamit(benchmark::State& state) {
auto a = CreateVector();
auto b = a; // elementwise copy
for (auto _ : state) {
std::vector<int> idx(N);
std::iota(begin(idx), end(idx), 0);
std::mt19937 g(std::random_device{}());
std::shuffle(begin(idx), end(idx), g);
std::vector<int> aout; aout.reserve(N);
std::transform(cbegin(idx), cend(idx), back_inserter(aout), [&](int i) { return a[i]; });
a = std::move(aout);
std::vector<int> bout; bout.reserve(N);
std::transform(cbegin(idx), cend(idx), back_inserter(aout), [&](int i) { return b[i]; });
b = std::move(bout);
}
if (!std::equal(cbegin(a), cend(a), cbegin(b)))
std::cout << "Vectors are not equal!n";
}
// Register the function as a benchmark
BENCHMARK(BM_Jamit);
static void BM_Armin(benchmark::State& state) {
auto a = CreateVector();
auto b = a; // elementwise copy
for (auto _ : state) {
const unsigned int seedValue = std::random_device()();
std::mt19937 uniformRandomBitGenerator{};
uniformRandomBitGenerator.seed(seedValue);
std::shuffle(begin(a), end(a), uniformRandomBitGenerator);
uniformRandomBitGenerator.seed(seedValue);
std::shuffle(begin(b), end(b), uniformRandomBitGenerator);
}
if (!std::equal(cbegin(a), cend(a), cbegin(b)))
std::cout << "Vectors are not equal!n";
}
// Register the function as a benchmark
BENCHMARK(BM_Armin);

#include <iterator>
template<class URBG, class RandomIt1, class RandomIt2>
static void SameShuffleToMany(URBG&& g, RandomIt1 first1, RandomIt1 last1, RandomIt2 first2) {
using diff_t = typename std::iterator_traits<RandomIt1>::difference_type;
using distr_t = std::uniform_int_distribution<diff_t>;
using param_t = typename distr_t::param_type;
distr_t D;
diff_t n = last1 - first1;
for (diff_t i = n-1; i > 0; --i) {
diff_t j = D(g, param_t(0, i));
std::swap(first1[i], first1[j]);
std::swap(first2[i], first2[j]);
}
}
static void BM_Mine(benchmark::State& state) {
auto a = CreateVector();
auto b = a; // elementwise copy
for (auto _ : state) {
std::mt19937 g{std::random_device{}()};
SameShuffleToMany(g, begin(a), end(a), begin(b));
}
if (!std::equal(cbegin(a), cend(a), cbegin(b)))
std::cout << "Vectors are not equal!n";
}
// Register the function as a benchmark
BENCHMARK(BM_Mine);
BENCHMARK_MAIN();

得到的CPU时间为:

• 原值:108600 ns
• Jamit: 76000 ns
• Armin: 122000 ns
• 矿山:102000 ns

链接到QuickBench让我知道这是否适合你。我不认为那里的链接分享工作得像GodBolt那样好。