带有自定义交换的C++排序实现？

Question

有很多关于如何在 C++ 中对多个数组进行排序的问题。答案总是相同的，即使用结构体向量而不是多个数组。不幸的是，由于多种原因（I/O、部分 MPI 传输、矢量化单元的利用等），我无法执行此操作。另外，由于内存限制，我无法在排序后将结构数组转换为独立数组。我的问题是，是否存在某种高效 (n log n) 排序算法的 C++ 实现可以与自定义交换（和自定义比较）操作一起使用？

（我还是不明白为什么STL中缺少这样的选项。显然，很多C++程序员都在要求它。）

Answer 1

您可以不精确地对数据进行排序，而只能对其他数组和自定义比较器的索引进行排序。排序后，您将拥有排序索引数组，并且您可以在 O(n) 内排列所有数组。

Answer 2

一个老问题；我也在寻找解决方案，我在互联网上找到了一个。

这篇博文：

https://artificial-mind.net/blog/2020/11/28/std-sort-multiple-ranges

提供了如何完成此操作的完整实现。

简而言之。这个想法是创建一个多重迭代器，它保存一个索引并引用您拥有的所有数组（可能超过 2 个）。您需要提供：

• 一种从多重迭代器引用的内存中读取数据并为其赋值的方法
• 在两个迭代器下交换内容的方法
• 比较两个迭代器内容的方法

完成上述所有操作后，您可以直接在数组上使用

std::sort

，而无需复制它们或使用任何辅助数组。我认为它没有理由不能与算法的并行版本一起使用。