C++. Сортировка с компаратором

Сортировка с компаратором

Вектор (как и массив)  можно сортировать с помощью функции sort(). Но эта функция по умолчанию сортирует по возрастанию. Чтобы отсортировать массив в другом порядке нужно использовать так называемый компаратор - функцию, которая сравнивая два объекта задает порядок сортировки.
 

Пример

Пример компаратора, сортирующего элементы массива по возрастанию.

bool cmp(int first, int second) 
{
    return first < second;
}

и сортировка вектора A, c использованием созданного компаратора:

sort(A.begin(), A.end(), cmp );

Вспомнить про итераторы

По условию задачи видно, что надо применить устойчивую (стабильную) сортировку, поэтому вместо sort надо применить stable_sort.

В качестве компаратора также можно указать функциональный объект, который можно создать перед вызовом функцией сортировки.

Функциональный объект (функтор) - это обычный класс/структура, у которого перегружен оператор ().

Например:

struct 
{ 
     bool operator()(int a, int b) const 
     { 
        return a < b; 
     } 
} cmp;

Пример

// Функтор для сортировки по возрастанию
struct Ascending {
    bool operator()(int a, int b) {
        return a < b;  // если a < b, то a будет перед b
    }
};

int main() {
    vector<int> numbers = {5, 2, 8, 1, 9};
    
    // Сортируем используя наш функтор
    sort(numbers.begin(), numbers.end(), Ascending());
    
    for (int n : numbers) {
        cout << n << " ";  // 1 2 5 8 9
    }
    return 0;
}

Плюсы:

• Можно хранить состояние (переменные внутри)
• Быстрее чем указатели на функции
• Можно передавать параметры

 

Главное запомнить:

1. Функциональный объект = класс с operator()
2. Для сортировки - создаем функтор с bool operator()(a, b)
3. Возвращает true если a должен быть перед b
4. Использование: sort(начало, конец, ИмяФунктора())

Лямбда - это безымянная функция, которую можно создать прямо в том месте, где она нужна.

vector<int> numbers = {5, 2, 8, 1, 9};
    
    // Сортируем через лямбду
    sort(numbers.begin(), numbers.end(), [](int a, int b) {
        return a < b;  // от меньшего к большему
    });

Синтаксис лямбды

[](параметры) -> возвращаемый_тип { тело_функции }