Сортировка по блокам элементов со станд.:: вид ()

Он не является частью какого-либо стандарта 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 , вы можете использовать пакет callback (3) из библиотеки ffcall для создания замыканий в время выполнения. Пример:

#include <callback.h>
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, e.g. as parameters to qsort
...
free_callback(comp1);
free_callback(comp2);

Обратите внимание, что библиотека обратного вызова является потокобезопасной, поскольку все параметры передаются в стеке или в регистрах. Библиотека заботится о распределении памяти, проверке ее выполнения и очистке кеша инструкций, если необходимо, чтобы разрешить динамически сгенерированный код (то есть закрытие) во время выполнения. Предположительно, он работает на большом количестве систем, но он s также вполне возможно, что это не сработает на вашем, либо из-за ошибок, либо из-за отсутствия реализации.

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

I don't remember exactly how to do this, but if you can fake anonymous functions, then you can make a comp(L) function that returns the version of comp for arrays of length L... that way L becomes a parameter, not a global, and you can use qsort. As others mentioned, except in the case where your array is already sorted, or backwards or something, qsort is going to be pretty much just as fast as any other algorithm. (there's a reason it's called quicksort after all...)

std::array< std::array<int, L>, N > array;
// or std::vector< std::vector<int> > if N*L is not a constant
std::sort( array.begin(), array.end() );

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

std::sort(&array[0], &array[N + L]);

отсортирует все элементы массива . Проблема в том, что он предполагает, что индексы, приращения, декремента и другие индексирующие операторы итератора перебирают элементы последовательности. Я считаю, что единственный способ сортировать срезы массива (я думаю, это то, что вам нужно), - это написать итератор, который индексирует на основе L .

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 () утверждает, что компаратор верен, проверяя его ДВАЖДЫ , один раз перевернув его, чтобы гарантировать обратный результат! Это полностью убьет производительность для умеренных наборов данных в обычных сборках. Решение выглядит примерно так:

#ifdef NDEBUG
  #define WAS_NDEBUG
  #undef NDEBUG
#endif
#define NDEBUG
#include <algorithm>
#ifdef WAS_NDEBUG
  #undef WAS_NDEBUG
#else
  #undef NDEBUG
#endif

Адаптировано из этой замечательной записи в блоге: http://www.tilander.org/aurora/2007/12/comparing-stdsort-and-qsort.html

Для этого можно использовать «итератор шага». «Итератор шага» оборачивает другой итератор и целочисленный размер шага. Вот простой набросок:

template<typename Iter>
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<typename Iter>
stride_iterator<Iter> make_stride_iter(
    Iter it,
    typename iterator_traits<Iter>::difference_type step)
{
    return stride_iterator<Iter>(it,step);
}

template<typename Iter>
stride_iterator<Iter> make_stride_iter(
    stride_iterator<Iter> it,
    typename iterator_traits<Iter>::difference_type step)
{
    return stride_iterator<Iter>(it.base(),it.step() * step);
}

, должны упростить использование итераторов шага:

int array[N*L];
std::sort( make_stride_iter(array,L),
           make_stride_iter(array,L)+N );

Самостоятельная реализация адаптера итератора (со всеми операторами), вероятно, не лучшая идея. Как отметил Матье, вы можете обезопасить себя от набора текста, если воспользуетесь, например, инструментами адаптера итератора Boost .

Edit: Я только что понял, что это не то, что вы хотели, поскольку std :: sort будет обменивать только первый элемент каждого блока. Я не думаю, что для этого есть простое и портативное решение. Проблема, которую я вижу, заключается в том, что замена «элементов» (ваших блоков) не может быть (легко) настроена при использовании std :: sort. Вы могли бы написать свой итератор так, чтобы он возвращал специальный ссылочный тип со специальной функцией обмена , но я не уверен, гарантирует ли стандарт C ++, что std :: sort будет использовать функцию обмена который ищется через ADL. Ваша реализация может ограничить его до std :: swap.

Думаю, лучший ответ по-прежнему: «Просто используйте qsort».

Многие из этих ответов кажутся излишними. Если вам действительно нужно сделать это в стиле C ++, используя пример jmucchiello:

template <int Length>
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]);

Это не должно быть более сложным.

Аркадий прав. Вы можете выполнить сортировку на месте, если создадите массив указателей и отсортируете его:

#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