c++ - 对动态大小的对象进行排序

Answer 1

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

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如果您愿意，也可以调用。）由于 STLsort内联比较调用，您可能无法获得最快的排序。如果您的系统所做的只是排序，那么添加代码以使自定义迭代器工作可能是值得的。但是，如果您的系统大部分时间都在做排序以外的事情，那么您获得的额外收益可能只是整个系统的噪音。

Answer 2

鉴于巨大的大小（4GB），我会认真考虑动态代码生成。将自定义排序编译到共享库中，并动态加载它。唯一的非内联调用应该是对库的调用。

使用预编译的头文件，编译时间实际上可能并没有那么糟糕。整个<algorithm>标题不会改变，你的包装逻辑也不会改变。您只需要每次重新编译一个谓词。而且由于它是您获得的单个功能，因此链接是微不足道的。

Answer 3

如果您可以将对象叠加到缓冲区上，那么您可以使用std::sort，只要您的叠加类型是可复制的。（在本例中，4 个 64 位整数）。使用 4GB数据，您将需要大量内存。

正如评论中所讨论的，您可以根据一些固定大小的模板选择可能的大小。您必须在运行时从这些类型中进行选择（switch例如，使用语句）。这是一个具有各种大小的模板类型的示例以及对 64 位大小进行排序的示例。

这是一个简单的例子：

#include <vector>
#include <algorithm>
#include <iostream>
#include <ctime>

template <int WIDTH>
struct variable_width
{
   unsigned char w_[WIDTH];
};

typedef variable_width<8> vw8;
typedef variable_width<16> vw16;
typedef variable_width<32> vw32;
typedef variable_width<64> vw64;
typedef variable_width<128> vw128;
typedef variable_width<256> vw256;
typedef variable_width<512> vw512;
typedef variable_width<1024> vw1024;

bool operator<(const vw64& l, const vw64& r)
{
   const __int64* l64 = reinterpret_cast<const __int64*>(l.w_);
   const __int64* r64 = reinterpret_cast<const __int64*>(r.w_);

   return *l64 < *r64;
}

std::ostream& operator<<(std::ostream& out, const vw64& w)
{
   const __int64* w64 = reinterpret_cast<const __int64*>(w.w_);
   std::cout << *w64;
   return out;
}

int main()
{
   srand(time(NULL));
   std::vector<unsigned char> buffer(10 * sizeof(vw64));
   vw64* w64_arr = reinterpret_cast<vw64*>(&buffer[0]);

   for(int x = 0; x < 10; ++x)
   {
      (*(__int64*)w64_arr[x].w_) = rand();
   }

   std::sort(
      w64_arr,
      w64_arr + 10);

   for(int x = 0; x < 10; ++x)
   {
      std::cout << w64_arr[x] << '\n';
   }

   std::cout << std::endl;

   return 0;
}

Answer 4

我同意std::sort使用自定义迭代器、引用和值类型；最好尽可能使用标准机械。

您担心内存分配，但现代内存分配器在分配小块内存方面非常有效，尤其是在重复使用时。你也可以考虑使用你自己的（有状态的）分配器，从一个小池中分发长度为s 的块。

Answer 5

由于只有 31 种不同的对象变体（1 到 32 个字节），您可以轻松地为每个变体创建对象类型，并std::sort根据 switch 语句选择调用。每个调用都将内联并高度优化。

某些对象大小可能需要自定义迭代器，因为编译器会坚持填充本机对象以对齐地址边界。在其他情况下，指针可以用作迭代器，因为指针具有迭代器的所有属性。

Answer 6

#define OBJECT_SIZE 32
struct structObject
{
    unsigned char* pObject;
    bool operator < (const structObject &n) const
    {
        for(int i=0; i<OBJECT_SIZE; i++)
        {
            if(*(pObject + i) != *(n.pObject + i))
                return (*(pObject + i) < *(n.pObject + i));
        }

        return false;       
    }
};

int _tmain(int argc, _TCHAR* argv[])
{       
    std::vector<structObject> vObjects;
    unsigned char* pObjects = (unsigned char*)malloc(10 * OBJECT_SIZE); // 10 Objects


    for(int i=0; i<10; i++)
    {
        structObject stObject;
        stObject.pObject = pObjects + (i*OBJECT_SIZE);      
        *stObject.pObject = 'A' + 9 - i; // Add a value to the start to check the sort
        vObjects.push_back(stObject);
    }

    std::sort(vObjects.begin(), vObjects.end());


    free(pObjects);

跳过#define

struct structObject
{
    unsigned char* pObject; 
};

struct structObjectComparerAscending 
{
    int iSize;

    structObjectComparerAscending(int _iSize)
    {
        iSize = _iSize;
    }

    bool operator ()(structObject &stLeft, structObject &stRight)
    { 
        for(int i=0; i<iSize; i++)
        {
            if(*(stLeft.pObject + i) != *(stRight.pObject + i))
                return (*(stLeft.pObject + i) < *(stRight.pObject + i));
        }

        return false;       
    }
};

int _tmain(int argc, _TCHAR* argv[])
{   
    int iObjectSize = 32; // Read it from somewhere

    std::vector<structObject> vObjects;
    unsigned char* pObjects = (unsigned char*)malloc(10 * iObjectSize);

    for(int i=0; i<10; i++)
    {
        structObject stObject;
        stObject.pObject = pObjects + (i*iObjectSize);      
        *stObject.pObject = 'A' + 9 - i; // Add a value to the start to work with something...  
        vObjects.push_back(stObject);
    }

    std::sort(vObjects.begin(), vObjects.end(), structObjectComparerAscending(iObjectSize));


    free(pObjects);