使用std :: sort()按元素块排序

Question

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

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数组的块大小不是由指针类型表示的.qsort()允许您显式指定块大小,但通过指针类型std::sort() 推断块大小.

出于性能原因(内存使用和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

拥有一个重新排序向量怎么样？您使用 1..N/L 初始化向量，传递 std::sort 一个比较器，该比较器将元素 i1*L..i1*L+L 与 i2*L..i2*L+L 进行比较，并且当您的向量正确排序时，根据新顺序对 C 数组重新排序。

回应评论：是的，事情变得复杂，但这可能只是很好的复杂化！看看这里。