c++ - 使用 STL 排序就地排序表

Question

我有一个存储为 (i,j,k) 格式(来自稀疏矩阵)的巨大表(大约 50Gb)

uint32_t * idx1, * idx2;
float * vals;
uint32_t tablesize;

并且我想使用作为 idx1 和 idx2 函数的给定比较函数对其进行适当的排序。这可以使用 std::sort 完成吗？

具体来说，稀疏矩阵中每个值为 v 的非零条目 (i,j) 的存储方式是将 i 放在 idx1 中，将 j 放在 idx2 中，将 v 放在 vals 中的相应条目中。然后我想根据 (i1, j1, v1) <= (i2, j2, v2) if

对这些条目进行排序

(i1 < i2) || (i1==i2 && j1 <= j2)

我能够搜集到的关于在非标准数据类型上使用 std::sort 的示例假设每个被比较的项目都是一个类的单个实例；这里每个项目都由不同数组中的三个值表示。

Answer 1

不幸的是，要说服 std::sort 或任何标准库使用 strip 化数据非常困难。它旨在假设数据可以通过单个 = 复制，通过一次 move 移动或通过一次 swap 交换。

最好的办法是使用 boost::iterator_facade 编写一个自定义迭代器类来包装数据，并从 std::sort 中隐藏 strip 数据格式。过去我想做类似的事情，但我的工作区不允许我们使用 boost。 编辑: 当您的门面被取消引用时，它可能需要创建某种可以分配/移动/交换的代理对象，并对每个 strip 数组做正确的事情。这不是微不足道的。

下一个最佳选择是制作一个从零到 N 的 int 数组，每个数组代表 strip 化数据数组中的一个索引。将自定义仿函数写入 std::sort 以对数组进行排序以符合您的条件。当您拥有如此庞大的数据集时，这显然远非理想。