使用std :: sort（）按元素块排序
我有一个边数组，它被定义为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; struct Edge { double x1, y1, x2, y2; }; Edge *p; ，我会很高兴。
但在这种情况下，double数组的块大小不是由指针类型表示的。 qsort()允许您显式指定块大小，但std::sort()通过指针类型推断块大小 。
出于性能原因（内存使用和CPU），让我们说创建新数组或以某种方式转换数组是不可取的。 出于性能原因，让我们说我们确实想使用std::sort()而不是qsort() 。
是否可以在转换数据时不浪费单个CPU周期来调用std::sort() ？
可能的方法：
一个显而易见的方法是尝试强制转换指针：
double *p = ...; struct Edge { double arr[4]; }; Edge *p2 = reinterpret_cast(p); std::sort(...);
但是如何确保数据正确对齐？ 此外，我如何确保它始终在所有平台和架构上正确对齐？
或者我可以使用typedef double[4] Edge; ？
如何重新排序矢量？ 用1..N / L初始化向量，传递std :: sort一个比较器，它将元素i1 * L..i1 * L + L与i2 * L..i2 * L + L进行比较，并且当向量正确排序时，根据新订单重新排序C数组。
回应评论：是的，事情变得复杂，但它可能只是很好的并发症！ 看看这里 。
你可以使用“stride iterator”。 “stride iterator”包装另一个迭代器和整数步长。 这是一个简单的草图：
template class stride_iterator { ... stride_iterator(Iter it, difference_type step = difference_type(1)) : it_(it), step_(step) {} stride_iterator& operator++() { std::advance(it_,step_); return *this; } Iter base() const { return it_; } difference_type step() const { return step_; } ... private: Iter it_; difference_type step_; };
此外，这些辅助函数
template stride_iterator make_stride_iter( Iter it, typename iterator_traits ::difference_type step) { return stride_iterator (it,step); } template stride_iterator make_stride_iter( stride_iterator it, typename iterator_traits ::difference_type step) { return stride_iterator (it.base(),it.step() * step); }
应该使用stride迭代器相当容易：
int array[N*L]; std::sort( make_stride_iter(array,L), make_stride_iter(array,L)+N );
自己（所有操作员）实现迭代器适配器可能不是一个好主意。 正如Matthieu指出的那样，如果你使用Boost的迭代器适配器工具，你可以安全地自己输入很多东西。
编辑：我刚刚意识到这不会做你想要的，因为std :: sort只会交换每个块的第一个元素。 我不认为这是一个简单易用的解决方案。 我看到的问题是，在使用std :: sort时，无法（轻松）自定义交换“元素”（您的块）。 您可以编写迭代器来返回带有特殊交换函数的特殊引用类型，但我不确定C ++标准是否保证std :: sort将使用通过ADL查找的交换函数。 您的实现可能会将其限制为std :: swap。
我想最好的答案仍然是：“只需使用qsort”。
我不记得究竟是怎么做的，但是如果你可以伪造匿名函数，那么你可以创建一个comp（L）函数，它返回长度为L的数组的comp版本……那样L成为参数，不是全局的，你可以使用qsort。 正如其他人所提到的，除了你的数组已经排序，或向后或类似的情况，qsort几乎与其他任何算法一样快。 （有一个原因，它毕竟叫做quicksort ……）
它不是任何ANSI，ISO或POSIX标准的一部分，但有些系统提供qsort_r()函数，它允许您将额外的上下文参数传递给比较函数。 然后你可以做这样的事情：
int comp(void *thunk, const void *a, const void *b) { int L = (int)thunk; // compare a and b as you would normally with a qsort comparison function } qsort_r(array, N, sizeof(int) * L, (void *)L, comp);
或者，如果您没有qsort_r ，则可以使用ffcall库中的callback(3)包在运行时创建闭包。 例：
#include void comp_base(void *data, va_alist alist) { va_start_int(alist); // return type will be int int L = (int)data; const void *a = va_arg_ptr(alist, const void*); const void *b = va_arg_ptr(alist, const void*); // Now that we know L, compare int return_value = comp(a, b, L); va_return_int(alist, return_value); // return return_value } ... // In a function somewhere typedef int (*compare_func)(const void*, const void*); // Create some closures with different L values compare_func comp1 = (compare_func)alloc_callback(&comp_base, (void *)L1); compare_func comp2 = (compare_func)alloc_callback(&comp_base, (void *)L2); ... // Use comp1 & comp2, eg as parameters to qsort ... free_callback(comp1); free_callback(comp2);
请注意， callback库是线程安全的，因为所有参数都在堆栈或寄存器中传递。 该库负责分配内存，确保内存可执行，并在必要时刷新指令缓存，以允许在运行时执行动态生成的代码（即闭包）。 它应该适用于各种各样的系统，但由于缺陷或缺乏实现，它也很可能无法在你的系统上运行。
另请注意，这会给函数调用增加一点开销。 上面对comp_base()每次调用都必须从传递它的列表中解压缩它的参数（这是一种高度依赖于平台的格式）并将其返回值comp_base() 。大多数时候，这个开销很小，但是为了比较函数，其中执行的实际工作非常小，并且在调用qsort()期间会多次调用，开销非常大。
对于新的问题，我们需要传递sort()一种迭代器，它不仅可以让我们比较正确的东西（即每次都要确保通过我们的double[]而不是1来执行4步）而且还要交换正确的事情（即交换4 double而不是1倍）。
我们可以通过简单地重新解释我们的双数组来完成它们，就像它是一个4个双精度数组一样。 这样做：
typedef double Edge[4];
不起作用，因为你不能分配数组，并且需要swap 。 但这样做：
typedef std::array Edge;
或者，如果不是C ++ 11：
struct Edge { double vals[4]; };
满足这两个要求。 从而：
void sort(double* begin, double* end) { typedef std::array Edge; Edge* edge_begin = reinterpret_cast(begin); Edge* edge_end = reinterpret_cast(end); std::sort(edge_begin, edge_end, compare_edges); } bool compare_edges(const Edge& lhs, const Edge& rhs) { // to be implemented }
如果您担心对齐，可以始终断言没有额外的填充：
static_assert(sizeof(Edge) == 4 * sizeof(double), "uh oh");
std::array< std::array, N > array; // or std::vector< std::vector > if N*L is not a constant std::sort( array.begin(), array.end() );
如果没有更多的工作，我不确定你能否达到同样的效果。 std::sort()用于对由两个随机访问迭代器定义的元素序列进行排序。 不幸的是，它确定了迭代器中元素的类型。 例如：
std::sort(&array[0], &array[N + L]);
将对array所有元素进行排序。 问题是它假定迭代器的下标，递增，递减和其他索引操作符跨越序列的元素。 我相信你可以对数组的切片进行排序的唯一方法（我认为这就是你所追求的），就是编写一个基于L索引的迭代器。 这就是sellibitze在stride_iterator答案中所做的 。
namespace { struct NewCompare { bool operator()( const int a, const int b ) const { return a < b; } }; } std::sort(array+start,array+start+L,NewCompare);
在现实数据集上使用std::stable_sort( ）进行测试 - 对于某些数据混合它的速度要快得多！
在许多编译器（GCC iirc）上有一个讨厌的咬合：std :: sort（）模板断言比较器是正确的，通过测试TWICE ，一旦反转，以确保结果反转！ 这绝对会完全破坏正常构建中的中等数据集的性能。 解决方案是这样的：
#ifdef NDEBUG #define WAS_NDEBUG #undef NDEBUG #endif #define NDEBUG #include #ifdef WAS_NDEBUG #undef WAS_NDEBUG #else #undef NDEBUG #endif
改编自这篇优秀的博客文章： http ： //www.tilander.org/aurora/2007/12/comparing-stdsort-and-qsort.html
Arkadiy有正确的想法。 如果您创建指针数组并对其进行排序，则可以对其进行排序：
#define NN 7 #define LL 4 int array[NN*LL] = { 3, 5, 5, 5, 3, 6, 6, 6, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 0, 0, 0, 1, 1, 1, 1 }; struct IntPtrArrayComp { int length; IntPtrArrayComp(int len) : length(len) {} bool operator()(int* const & a, int* const & b) { for (int i = 0; i < length; ++i) { if (a[i] < b[i]) return true; else if (a[i] > b[i]) return false; } return false; } }; void sortArrayInPlace(int* array, int number, int length) { int** ptrs = new int*[number]; int** span = ptrs; for (int* a = array; a < array+number*length; a+=length) { *span++ = a; } std::sort(ptrs, ptrs+number, IntPtrArrayComp(length)); int* buf = new int[number]; for (int n = 0; n < number; ++n) { int offset = (ptrs[n] - array)/length; if (offset == n) continue; // swap int* a_n = array+n*length; std::move(a_n, a_n+length, buf); std::move(ptrs[n], ptrs[n]+length, a_n); std::move(buf, buf+length, ptrs[n]); // find what is pointing to a_n and point it // to where the data was move to int find = 0; for (int i = n+1; i < number; ++i) { if (ptrs[i] == a_n) { find = i; break; } } ptrs[find] = ptrs[n]; } delete[] buf; delete[] ptrs; } int main() { for (int n = 0; n< NN; ++n) { for (int l = 0; l < LL; ++l) { std::cout << array[n*LL+l]; } std::cout << std::endl; } std::cout << "----" << std::endl; sortArrayInPlace(array, NN, LL); for (int n = 0; n< NN; ++n) { for (int l = 0; l < LL; ++l) { std::cout << array[n*LL+l]; } std::cout << std::endl; } return 0; }
输出：
3555 3666 4444 4333 2222 2000 1111 ---- 1111 2000 2222 3555 3666 4333 4444
很多这些答案看起来有点矫枉过正。 如果你真的必须用C ++风格，使用jmucchiello的例子：
template struct Block { int n_[Length]; bool operator <(Block const &rhs) const { for (int i(0); i < Length; ++i) { if (n_[i] < rhs.n_[i]) return true; else if (n_[i] > rhs.n_[i]) return false; } return false; } };
然后排序：
sort((Block<4> *)&array[0], (Block<4> *)&array[NN]);
它不必再复杂了。