Problem

假设我有一个包含一些数据的大字节数组（最多 4GB）。这些字节对应于不同的对象，使得每个s字节（认为 s 最多 32）将构成单个对象。一个重要的事实是这个尺寸s对于所有对象都是相同的，不存储在对象本身中，并且在编译时不知道。

目前，这些对象只是逻辑实体，而不是编程语言中的对象。我对这些对象进行了比较，其中包括对大多数对象数据进行字典顺序比较，并使用一些不同的功能来使用剩余数据打破联系。现在我想对这些对象进行排序有效率的（这确实会成为应用程序的瓶颈）。

到目前为止的想法

我想到了几种可能的方法来实现这一目标，但每种方法似乎都会产生一些相当不幸的后果。您不必阅读所有这些内容。我尝试用粗体打印每种方法的核心问题。 If你将建议其中一种方法，then您的答案也应该回答相关问题。

1.C快速排序

当然，C 快速排序算法也可用于 C++ 应用程序。它的签名几乎完全符合我的要求。但事实上，使用该函数将禁止比较函数的内联，这意味着每次比较都会产生函数调用开销。我本来希望有一种方法可以避免这种情况。任何关于如何C的经验qsort_r与STL相比，在性能方面会非常受欢迎。

2. 使用指向数据的对象进行间接访问

编写一堆持有各自数据指针的对象是很容易的。然后就可以对它们进行排序。这里有两个方面需要考虑。一方面，仅移动指针而不是移动所有数据意味着更少的内存操作。另一方面，不移动对象可能会破坏内存局部性，从而破坏缓存性能。更深层次的快速排序递归实际上可以从几个缓存页面访问所有数据的机会几乎完全消失。相反，每个缓存的内存页在被替换之前只会产生很少的可用数据项。如果有人可以提供一些关于复制和内存局部性之间权衡的经验，我会非常高兴。

3. 自定义迭代器、引用和值对象

我编写了一个类，用作内存范围上的迭代器。取消引用此迭代器不会产生引用，而是会产生一个新构造的对象来保存指向数据和大小的指针s这是在迭代器构造时给出的。所以这些对象可以进行比较，我什至有一个实现std::swap对于这些。不幸的是，看来std::swap还不够std::sort。在该过程的某些部分，我的 gcc 实现使用插入排序（如__insertion_sort在文件中stl_alog.h) 将一个值移出序列，将多个项目移动一步，然后将第一个值移回序列中的适当位置：

          typename iterator_traits<_RandomAccessIterator>::value_type
            __val = _GLIBCXX_MOVE(*__i);
          _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
          *__first = _GLIBCXX_MOVE(__val);

您是否知道不需要值类型但可以单独使用交换操作的标准排序实现？

所以我不仅需要我的类作为参考，而且我还需要一个类来保存临时值。由于我的对象的大小是动态的，我必须在堆上分配它，这意味着内存分配在递归树的最叶子上。也许一种替代方案是具有静态大小的 vue 类型，该类型应该足够大以容纳我当前打算支持的大小的对象。但这意味着两国之间的关系将会出现更多的黑客行为。reference_type和value_type的迭代器类。这意味着我必须更新我的应用程序的大小，以便有一天支持更大的对象。丑陋的。

如果您能想到一种干净的方法来让上述代码来操作我的数据，而不必动态分配内存，那将是一个很好的解决方案。我已经在使用 C++11 功能，因此使用移动语义或类似功能不会有问题。

4. 自定义排序

我什至考虑重新实现所有的快速排序。也许我可以利用这样一个事实，即我的比较主要是字典比较，即我可以按第一个字节对序列进行排序，并且仅当所有元素的第一个字节都相同时才切换到下一个字节。我还没有弄清楚这方面的细节，但是如果有人可以建议一个参考、一个实现，甚至一个规范名称来用作这种按字节词典排序的关键字，我会非常高兴。我仍然不相信只要我付出合理的努力，我就能超越 STL 模板实现的性能。

5.完全不同的算法

我知道有很多很多那里有各种各样的排序算法。其中一些可能更适合我的问题。基数排序我首先想到的是这个，但我还没有真正考虑清楚。如果您可以建议更适合我的问题的排序算法，请这样做。最好有实施，但即使没有。

Question

所以基本上我的问题是这样的：
“如何有效地对堆内存中动态大小的对象进行排序？”

这个问题的任何答案只要适合我的情况就是好的，无论是否与我自己的想法有关。对以粗体标记的各个问题的答案，或任何其他可能帮助我在替代方案之间做出决定的见解，也将很有用，特别是如果对单一方法没有明确的答案时。

最实用的解决方案是使用C风格qsort你提到的。

template <unsigned S>
struct my_obj {
    enum { SIZE = S; };
    const void *p_;
    my_obj (const void *p) : p_(p) {}
    //...accessors to get data from pointer
    static int c_style_compare (const void *a, const void *b) {
        my_obj aa(a);
        my_obj bb(b);
        return (aa < bb) ? -1 : (bb < aa);
    }
};

template <unsigned N, typename OBJ>
void my_sort (const char (&large_array)[N], const OBJ &) {
    qsort(large_array, N/OBJ::SIZE, OBJ::SIZE, OBJ::c_style_compare);
}

（或者，您可以致电qsort_r如果你愿意的话。）从STL开始sort内联比较调用，您可能无法获得最快的排序。如果您的系统所做的只是排序，那么添加代码以使自定义迭代器正常工作可能是值得的。但是，如果您的系统大部分时间都在做排序以外的事情，那么您获得的额外增益可能对整个系统来说只是噪音。