Ответ 1

Поскольку существует только 31 различных вариаций объектов (от 1 до 32 байтов), вы можете легко создать тип объекта для каждого и выбрать вызов std::sort на основе оператора switch. Каждый вызов будет встроен и оптимизирован.

Для некоторых размеров объектов может потребоваться пользовательский итератор, поскольку компилятор будет настаивать на добавлении собственных объектов для выравнивания к границам адресов. Указатели могут использоваться как итераторы в других случаях, поскольку указатель имеет все свойства итератора.

Ответ 2

Наиболее практичным решением является использование стиля 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 вставляет вызовы сравнения, вы не можете получить самую быструю сортировку. Если вся ваша система выполняет сортировку, возможно, стоит добавить код, чтобы заставить пользовательские итераторы работать. Но если в большинстве случаев ваша система делает что-то другое, кроме сортировки, дополнительная прибыль, которую вы получите, может быть просто помехой для вашей общей системы.

Ответ 3

Если вы можете наложить объект на свой буфер, вы можете использовать std::sort, если ваш тип наложения можно скопировать. (В этом примере 4 64-битных целых числа). С 4 ГБ данных вам понадобится много памяти.

Как обсуждалось в комментариях, вы можете иметь выбор возможных размеров на основе некоторого количества шаблонов фиксированного размера. Вы должны были бы выбрать из этих типов во время выполнения (например, с помощью инструкции 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;
}

Ответ 4

Я согласен с std::sort с использованием пользовательского итератора, ссылки и типа значений; лучше всего использовать стандартную технику, где это возможно.

Вы беспокоитесь о распределении памяти, но современные распределители памяти очень эффективны при раздаче небольших фрагментов памяти, особенно при многократном повторном использовании. Вы также можете рассмотреть возможность использования собственного (stateful) распределителя, выдающего куски длины из небольшого пула.

Ответ 5

Учитывая огромный размер (4 ГБ), я бы серьезно подумал о динамическом генерации кода. Скомпилируйте пользовательский сортир в общую библиотеку и динамически загрузите его. Единственным неинтерминированным вызовом должен быть вызов в библиотеку.

С предварительно скомпилированными заголовками время компиляции может быть не так уж плохо. Целый заголовок <algorithm> не изменяется, а также ваша логика обертки. Вам просто нужно перекомпилировать один предикат каждый раз. И поскольку это единственная функция, которую вы получаете, соединение является тривиальным.

Ответ 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);