Sortare

Funcția std::sort() din fișierul de antet <algorithm> este destinată pentru sortarea unui interval de elemente. Primii doi parametri ai funcției reprezintă iteratorii de început și sfârșit ai intervalului de elemente care trebuie sortate. Al treilea parametru, care este opțional, reprezintă o funcție de comparație sau un comparator. Dacă comparatorul nu este specificat, elementele vor fi sortate în ordine crescătoare (de exemplu, șirurile de caractere vor fi sortate în ordine lexicografică).

De exemplu, să sortăm un vector de șiruri de caractere în mod implicit:

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

int main()
{
    std::vector<std::string> people {"Tom", "Bob", "Sam", "Alice", "Kate"};
 
    std::sort(begin(people), end(people)); // sortăm vectorul people
 
    for (const auto& person : people)
    {
        std::cout << person << std::endl;
    }
}

În acest caz, sortăm întregul vector people, de aceea în funcția std::sort se transmit iteratorii pentru începutul și sfârșitul vectorului. Rezultatul va fi următorul:

Alice
Bob
Kate
Sam
Tom

Astfel, șirurile de caractere sunt sortate în ordine lexicografică (după literele de început ale șirurilor).

Acum să aplicăm un comparator. De exemplu, să sortăm vectorul în funcție de lungimea șirurilor de caractere:

#include <iostream>
#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;
    }
}

În acest caz, funcția compare este definită ca un comparator. Comparatorul trebuie să primească două valori și să returneze un rezultat de tip bool – dacă prima valoare trebuie să vină înaintea celei de-a doua, se returnează true. În acest exemplu, funcția compare primește două șiruri de caractere și returnează true dacă lungimea primului șir este mai mică decât a celui de-al doilea. Astfel, ieșirea va fi:

Tom
Bob
Sam
Kate
Alice

Adică șirurile sunt sortate în funcție de lungimea lor, în ordine crescătoare.

std::ranges::sort()

Începând cu standardul C++20, pentru sortarea elementelor unui container se poate utiliza o abordare simplificată – funcția std::ranges::sort(), care primește containerul de sortat ca parametru:

#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>     // pentru std::ranges

int main()
{
    std::vector<std::string> people {"Tom", "Bob", "Sam", "Alice", "Kate"};
 
    std::ranges::sort(people);  // sortăm vectorul people
 
    for (const auto& person : people)
    {
        std::cout << person << std::endl;
    }
}

Prin default, datele sunt sortate în ordine crescătoare (în cazul șirurilor de caractere, în ordine lexicografică).

Ieșirea va fi:

Alice
Bob
Kate
Sam
Tom

De asemenea, ca al doilea parametru se poate transmite o funcție comparator, care va determina modul în care se compară valorile:

#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>     // pentru 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); // sortăm vectorul people cu ajutorul comparatorului compare
 
    for (const auto& person : people)
    {
        std::cout << person << std::endl;
    }
}

Folosind funcția comparator compare, ordonăm elementele în funcție de lungimea lor:

Tom
Bob
Sam
Kate
Alice

Sortare cu proiecție

Funcția std::ranges::sort suportă proiecția datelor pentru funcția comparatorului. De exemplu:

#include <iostream>
#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;
    }
}

Aici, vectorul sortat conține obiecte Person, care stochează un nume într-un câmp de tip șir de caractere (name). Am fi putut defini o funcție de comparator pentru obiectele Person, dar în acest caz putem utiliza funcția comparator definită anterior pentru a compara șirurile de caractere.

În std::ranges::sort(), ca al treilea parametru se transmite o funcție de proiecție care convertește obiectul Person într-un șir de caractere (funcția personToString). Astfel, aceste date vor fi transmise funcției comparator pentru a compara două obiecte Person.