c++ - 使用 std::sort() 按元素 block 排序

Question

我有一个边数组，它被定义为 C 风格的 double 组，其中每 4 个 double 定义一个边，如下所示:

double *p = ...;
printf("edge1: %lf %lf %lf %lf\n", p[0], p[1], p[2], p[3]);
printf("edge2: %lf %lf %lf %lf\n", p[4], p[5], p[6], p[7]);

所以我想使用 std::sort() 按边长对它进行排序。如果它是 struct Edge { double x1, y1, x2, y2; }; Edge *p;，我可以走了。

但在这种情况下，double 数组的 block 大小不是由指针类型表示的。 qsort() 允许您显式指定 block 大小，但 std::sort() 通过指针类型推断 block 大小。

出于性能原因(内存使用和 CPU)，假设创建新数组或以某种方式转换数组是不可取的。再次出于性能原因，假设我们确实想使用 std::sort() 而不是 qsort()。

是否可以调用 std::sort() 而不浪费单个 CPU 周期来转换数据？

可能的方法:

一个明显的方法是尝试强制转换指针:

double *p = ...;
struct Edge { double arr[4]; };
Edge *p2 = reinterpret_cast<Edge*>(p);
std::sort(...);

但是如何确保数据正确对齐？另外，如何确保它始终在所有平台和架构上正确对齐？

或者我可以使用 typedef double[4] Edge; 吗？

Answer 1

有一个重排序 vector 怎么样？你用 1..N/L 初始化 vector ，传递 std::sort 比较元素 i1*L..i1*L+L 到 i2*L..i2*L+L 的比较器，当你的 vector 被正确排序时, 根据新顺序对 C 数组重新排序。

回应评论:是的，事情变得复杂了，但这可能只是一个很好的复杂化!看看here .