Сортировка вектора указателей

#cpp

Есть вектор указателей на объекты класса. Как выполнить его сортировку по одному
из полей этого класса при помощи функции сравнения? Как она должна выглядеть?

std::vector scanArray;

    

Ответы

Ответ 1

Сортировка

Как выглядит функция сравнения — это известно только вам, данных о структуре MyClassScan
вы не предоставляете.

Как сортировать? Очень просто, нужно использовать std::sort или подобный алгоритм.
Сигнатуру вызова можно найти по ссылке.

Функция сравнения

Теперь, как написать правильный компаратор (функцию сравнения). Такая функция принимает
на вход два объекта и возвращает true, если один больше/меньше другого (бинарное отношение).
К примеру, std::less задает отношение «меньше»:

auto less = std::less();
std::cout << less(1, 0) << "\n";  // 0
std::cout << less(1, 1) << "\n";  // 0
std::cout << less(0, 1) << "\n";  // 1


Как написать такую функцию, думаю, понятно. Нужно лишь учитывать, что вы работаете
с указателями, которые могут быть нулевыми. Что делать, если на вход подали такой указатель
— решать вам.

Пример:

struct Test { int val = 0; };

bool cmp_test(const Test* a, const Test* b) {
    return !a || !b ? 0 : a->val < b->val;
}

int main() {
    Test a, b;
    a.val = 0; b.val = 1;
    std::cout << cmp_test(b, a) << "\n";  // 0
    std::cout << cmp_test(b, b) << "\n";  // 0
    std::cout << cmp_test(a, b) << "\n";  // 1
    return 0;
}


Или используя лямбды:

struct Test { int val = 0; };

int main() {
    auto cmp_test = [](const Test* a, const Test* b) {
        return !a || !b ? 0 : a->val < b->val;
    };
    Test a, b;
    a.val = 0; b.val = 1;
    std::cout << cmp_test(b, a) << "\n";  // 0
    std::cout << cmp_test(b, b) << "\n";  // 0
    std::cout << cmp_test(a, b) << "\n";  // 1
    return 0;
}


Функтор сравнения

На этом месте нужно задать вопрос: почему мы писали auto less = std::less();?
А именно, зачем круглые скобки и что же такое std::less?

Рассмотрим типичную функцию, использующую компаратор. К примеру, минимум:

template T min(const T a, const T b, CMP cmp) {
    return cmp(a, b) ? a : b;
}


Наша функция принимает на вход два объекта и компаратор для них и возвращает меньший
объект. К примеру:

Test a, b;
a.val = -1; b.val = 1;
auto m = min(&a, &b, cmp_test);
std::cout << m->val << "\n";  // -1


Что же такое cmp внутри функции min? В нашем коде это указатель на функцию. Наша
min принимает указатель на функцию и вызывает ее.

Но если сравнений происходит много (а в сортировке их много), мы будем терять немного
времени на вызов функции. Значит, мы хотим сделать нашу функцию inline.

Проблема в том, что указатель на функцию мы заранее не знаем, а значит не можем инлайнить
реализацию. К примеру, у нас может быть два компаратора с одинаковой сигнатурой, и
мы можем передать ссылку на любой из них:

auto cmp_test1 = [](const Test* a, const Test* b) {
    return !a || !b ? 0 : a->val < b->val;
};

auto cmp_test2 = [](const Test* a, const Test* b) {
    return !a || !b ? 0 : a->val > b->val;
};

    ...

Test a, b;
a.val = -1; b.val = 1;
auto m1 = min(&a, &b, cmp_test1);
auto m2 = min(&a, &b, cmp_test2);
std::cout << m1->val << "\n";  // -1
std::cout << m2->val << "\n";  // 1


В коде выше шаблонизатор вывел одну спецификацию шаблона min, которая принимает указатель
на функцию.

Поэтому применяется трюк в виде функтора.
Функтор — структура с определенным оператором operator(). Такая структура выглядит,
как функция, но на самом деле это класс. Рассмотрим std::less:

template  struct less : binary_function  {
    bool operator() (const T& x, const T& y) const { return x < y; }
};


Итак, мы создали структуру less (наследование от binary_function, вообще, не обязательно,
см. комментарий @alexolut). Экземпляры структуры ведут себя похожим на функцию образом
— их можно «вызывать»:

auto cmp = less();  // Создаем экземпляр структуры
std::cout << cmp(1, 0) << "\n";  // 0  // Используем operator()
std::cout << cmp(1, 1) << "\n";  // 0
std::cout << cmp(0, 1) << "\n";  // 1


Чем это кардинально отличается от указателя на функцию? А тем, что для каждой такой
структуры шаблонизатор выведет свою спецификацию. Мы можем использовать такие структуры
точно так же, как и функции:

Test a, b;
a.val = -1; b.val = 1;
auto m = min(&a, &b, less());
std::cout << m->val << "\n";  // -1


Однако теперь мы передаем внутрь не указатель на некоторую функцию, а экземпляр конкретного
класса. А значит, реализация operator() известна для каждой спецификации и ее можно
заинлайнить.

Для нашего Test такой функтор будет выглядить так:

struct cmp_test3 : binary_function  {
    bool operator() (const Test* a, const Test* b) const {
        return !a || !b ? 0 : a->val < b->val;
    }
};


TLDR

#include 
#include 
#include 
#include 

struct Test {
    int val = 0;
    Test(int a): val(a) {};
};

struct cmp_test : std::binary_function  {
    bool operator() (const Test* a, const Test* b) const {
        return !a || !b ? 0 : a->val < b->val;
    }
};

int main() {
    Test a(1), b(3), c(2), d(4);
    std::vector v {&a, &b, &c, &d};

    std::sort(v.begin(), v.end(), cmp_test());

    for (auto i: v)
        std::cout << i->val << " ";  // 1 2 3 4

    return 0;
}


Ответ 2

#include 
#include 

struct MyClassScan
{
    int sortedField;
    int otherField;

    MyClassScan(int _sortedField, int _otherField)
    : sortedField(_sortedField)
    , otherField(_otherField)
    {}
};

bool ComparatorFunction(const MyClassScan* left, const MyClassScan* right)
{
    return left->sortedField < right->sortedField;
}

struct ComparatorClass
{
    bool operator () (const MyClassScan* left, const MyClassScan* right) const
    {
        return left->sortedField < right->sortedField;
    }
};

int main()
{
    std::vector pointersVector = { new MyClassScan(5, 1), new MyClassScan(4,
2), new MyClassScan(3, 3), new MyClassScan(2, 4), new MyClassScan(1, 5) };

    // способ 1
    std::sort(pointersVector.begin(), pointersVector.end(), [](const MyClassScan*
left, const MyClassScan* right){ return left->sortedField < right->sortedField; });

    // способ 2
    std::sort(pointersVector.begin(), pointersVector.end(), ComparatorFunction);

    // способ 3
    std::sort(pointersVector.begin(), pointersVector.end(), ComparatorClass());

    for (auto it = pointersVector.begin(); it != pointersVector.end();)
    {
        delete *(it++);
    }
}




При необходимости добавьте везде проверки на nullptr.

Если возникнет необходимость сотировать сразу по нескольким полям класса, то воспользуйтесь
std::tie в соответствующих местах:

std::tie(left->sortedField, left->otherField) < std::tie(right->sortedField, right->otherField)


вместо

left->sortedField < right->sortedField


Ответ 3

Просто:

std::sort(begin(scanArray), end(scanArray), [](const MyClassScan* a, const MyClassScan
*b) {
  return a->someField < b->someField;
});


Если более обще: то просто передать свой компаратор в алгоритм std::sort: http://www.cplusplus.com/reference/algorithm/sort