Сортировка

Функция std::sort() из заголовочного файла <algorithm> предназначена для сортировки диапазон элементов. Первые два параметра функции представляют начальный и конечный итераторы сортируемого диапазона. Третий необязательный параметр представляет функцию сравнения или компаратор. Если компаратор не указан, то элементы сортируются по возрастанию (например, строки сортируются в лексикографическом порядке).

Например, отсортируем вектор строк по умолчанию:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main()
{
    std::vector<std::string> people {"Tom", "Bob", "Sam", "Alice", "Kate"};  

    std::sort(begin(people), end(people)); // сортируем вектор people

    for(const auto& person: people )
    {
        std::cout << person << std::endl;
    }
}

В данном случае сортируем весь вектор people, поэтому в функцию std::sort передаются итераторы на начало и конец вектора. И в данном случае мы получим следующий результат:

Alice
Bob
Kate
Sam
Tom

То есть строки сортируются в лексикографическом порядке (как идут в алфавите начальные буквы строк). Теперь применим компаратор, например, отсортируем вектор в зависимости от длины строк:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

bool compare(const std::string& left, const std::string& right) 
{ 
    return left.length() < right.length(); 
}

int main()
{
    std::vector<std::string> people {"Tom", "Bob", "Sam", "Alice", "Kate"};  

    std::sort(begin(people), end(people), compare);

    for(const auto& person: people )
    {
        std::cout << person << std::endl;
    }
}

В качестве компаратора здесь определена функция compare. Компаратор должен принимать два значения и возвращать значение типа bool - если первое значение должно идти до второго, то возвращается true. И в случае выше функция compare принимает две строки и возвращает true, если длина первой строки меньше второй. Соответственно теперь консольный вывод будет следующим:

Tom
Bob
Sam
Kate
Alice

То есть строки отсортированы по длине по возрастанию.

std::ranges::sort()

Начиная со стандарта C++20 также для сортировки элементов контейнера можно использовать упрощенный подход - функцию std::ranges::sort(), которая в качестве параметра принимает сортируемый контейнер:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <ranges>		// для std::ranges

int main()
{
    std::vector<std::string> people {"Tom", "Bob", "Sam", "Alice", "Kate"};  

    std::ranges::sort(people);	// сортируем вектор people

    for(const auto& person: people )
    {
        std::cout << person << std::endl;
    }
}

По умолчанию данные сортируются по возрастанию (в случае со строками в лексикографическом порядке)

Alice
Bob
Kate
Sam
Tom

Также в качестве второго параметра можно передать функцию компаратора, которая определяет принцип сравнения значений:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <ranges>		// для std::ranges

bool compare(const std::string& left, const std::string& right) 
{ 
    return left.length() < right.length(); 
}

int main()
{
    std::vector<std::string> people {"Tom", "Bob", "Sam", "Alice", "Kate"};  

    std::ranges::sort(people, compare);	// сортируем вектор people с помощью компаратора compare

    for(const auto& person: people)
    {
        std::cout << person << std::endl;
    }
}

С помощью функции-компаратора compare упорядочиваем элементы по возрастанию их длин:

Tom
Bob
Sam
Kate
Alice

Сортировка с проекцией

Функция std::ranges::sort поддерживает проекцию данных для функции компаратора. Например:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <ranges>

class Person
{
public:
    Person(std::string name): name{name}{}
    std::string getName() const {return name;}
private:
    std::string name;
};

bool compare(const std::string& left, const std::string& right) 
{ 
    return left.length() < right.length(); 
}
std::string personToString(const Person& person){ return person.getName();}
int main()
{ 
    std::vector<Person> people {Person{"Tom"}, Person{"Kate"}, Person{"Bob"}, Person{"Alice"}};
    std::ranges::sort(people, compare, personToString);

    for(const auto& person: people )
    {
        std::cout << person.getName() << std::endl;
    }
}

Здесь сортируемый вектор содержит объекты Person, который хранит имя в строковом поле name. Мы могли бы определить для сравнения данных Person еще одну функцию компаратора. Но в данном случае мы также можем использовать и ранее определенную функцию компаратора для сравнения строк. Но в этом случае в std::ranges::sort() в качестве третьего параметра передается функция проекции из Person в std::string - функция personToString, которая возвращает имя объекта Person. Именно эти данные и будут передаваться в функцию компаратора при сравнении двух объектов.