sort w C++ – sortowanie kontenerów STL, własne komparatory i lambda-komparatory

Analiza sortowania w C++ STL – niestandardowe komparatory i wyrażenia lambda

Artykuł przedstawia szczegółową analizę mechanizmów sortowania w Standardowej Bibliotece Szablonów C++ (STL), skupiając się na niestandardowych komparatorach i wyrażeniach lambda. Sortowanie stanowi kluczową operację organizowania danych, a język C++ zapewnia wszechstronne narzędzia do jego realizacji dzięki nagłówkowi <algorithm>. Opracowanie obejmuje podstawy teoretyczne, praktyczne implementacje oraz zaawansowane techniki manipulowania kolejnością sortowania w różnych typach kontenerów i struktur danych.

Algorytm std::sort

Podstawowa implementacja

Funkcja std::sort wykorzystuje hybrydowy algorytm sortowania, tzw. Introsort, który łączy algorytmy Quicksort, Heapsort i sortowanie przez wstawianie w celu uzyskania optymalnej wydajności. Algorytm ten charakteryzuje się zarówno średnią, jak i pesymistyczną złożonością czasową (O(N \log N)), co czyni go odpowiednim do przetwarzania dużych zbiorów danych. Funkcja wymaga iteratorów o dostępie swobodnym, co ogranicza jej bezpośrednie zastosowanie do kontenerów takich jak std::vector, std::deque oraz klasyczne tablice. Składnia jest zunifikowana:

std::sort(RandomAccessIterator first, RandomAccessIterator last, Comparator comp = std::less<>{});

first i last wyznaczają zakres [first, last), natomiast opcjonalny parametr comp określa kryterium sortowania. Bez jawnego wskazania komparatora std::sort domyślnie sortuje rosnąco z użyciem std::less<>.

Podstawowe przykłady użycia

Sortowanie tablicy liczb całkowitych rosnąco prezentuje zachowanie domyślne:

#include <algorithm> #include <iostream> int main() { int arr[] = {5, 2, 9, 1, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); std::sort(arr, arr + n); for (int i = 0; i < n; ++i) std::cout << arr[i] << " "; // Wynik: 1 2 5 5 6 9 }

Dla porządku malejącego używa się obiektu funkcyjnego std::greater<>:

std::sort(arr, arr + n, std::greater<int>()); // Wynik: 9 6 5 5 2 1

Wbudowane komparatory i obiekty funkcyjne

Predefiniowane obiekty komparatorów

Standardowa biblioteka C++ udostępnia szablonowe obiekty komparatorów w nagłówku <functional>:

• std::greater<T> – sortuje elementy malejąco,
• std::less<T> – domyślny komparator rosnący,
• std::greater_equal<T>/std::less_equal<T> – porównania nieściśle.

Obiekty te wykorzystują odpowiadające im operatory (>, <) dla typu T, gwarantując spójność porządku.

Specjalistyczne sortowanie napisów

Sortowanie napisów bez rozróżniania wielkości liter wymaga własnego komparatora, co ilustruje elastyczność STL poza typami prymitywnymi:

bool case_insensitive_compare(const std::string& a, const std::string& b) { for (size_t i=0; i < std::min(a.length(), b.length()); ++i) if (std::tolower(a[i]) != std::tolower(b[i])) return std::tolower(a[i]) < std::tolower(b[i]); return a.length() < b.length(); } std::list<std::string> words = {"Apple", "banana", "Cherry"}; words.sort(case_insensitive_compare); // Wynik: "Apple", "banana", "Cherry"

Niestandardowe funkcje komparatorów

Wymagania strukturalne

Niestandardowe komparatory muszą spełniać zasadę ścisłego słabego porządku (strict weak ordering), obejmującą trzy własności matematyczne:

1. Nierefeksyjność – comp(x, x) = false
2. Antysymetria – comp(x, y) = true implikuje comp(y, x) = false
3. Tranzytywność – comp(x, y) i comp(y, z) implikują comp(x, z)

Naruszenie tych własności prowadzi do niezdefiniowanego zachowania.

Sortowanie po wielu polach

Dla obiektów zawierających wiele atrybutów komparatory mogą hierarchizować porównywane pola. Przykład sortowania obiektów Player najpierw po punkctach (malejąco), następnie po nazwie (rosnąco):

struct Player { std::string name; int score; }; bool player_comparator(const Player& a, const Player& b) { if (a.score != b.score) return a.score > b.score; // Najpierw wyższy wynik return a.name < b.name; // Alfabet jeśli wynik równy } std::vector<Player> players = {{"Alice", 30}, {"Bob", 50}, {"Charlie", 40}}; std::sort(players.begin(), players.end(), player_comparator); /* Wynik: Bob: 50 Charlie: 40 Alice: 30 */

Wyrażenia lambda jako komparatory

Składnia i własności przechwytywania

Wyrażenia lambda pozwalają na definiowanie komparatorów „w miejscu”, bez konieczności tworzenia oddzielnych funkcji. Składnia ogólna wygląda następująco:

[capture-list](parameters) -> return-type { body }

Kluczowe cechy lamd to:

• Klamra przechwytywania – [] (nic), [&] (przez referencję), [=] (przez kopiowanie),
• Dedukcja typów – parametry auto w uogólnionych lambdach (C++14),
• Niejawny typ zwrotny – jednoargumentowe ciała automatycznie dedukują typ.

Praktyczne użycie lambd

Sortowanie par po drugim elemencie (malejąco) ukazuje wydajność lambd:

std::vector<std::pair<int, int>> coordinates = {{1,4}, {3,1}, {5,3}, {4,2}}; std::sort(coordinates.begin(), coordinates.end(), [](const auto& a, const auto& b) { return a.second > b.second; }); // Wynik: (1,4), (5,3), (4,2), (3,1)

Rekurencyjne lambdy

Obsługę rekurencji w lambdach zapewnia std::function:

std::function<int(int,int)> gcd = [&](int a, int b) -> int { return b == 0 ? a : gcd(b, a % b); }; std::cout << gcd(20, 30); // Wynik: 10

Specjalne sortowanie kontenerów

Funkcja członkowska std::list

W odróżnieniu od kontenerów sekwencyjnych, std::list posiada własną metodę do sortowania z powodu ograniczeń iteratorów dwukierunkowych:

std::list<int> numbers = {1, 4, 2, 5, 3}; numbers.sort(std::greater<int>()); // Wynik: 5, 4, 3, 2, 1

Metoda list::sort zachowuje stabilność (porządek równych elementów) i realizuje złożoność (O(N \log N)).

Kontenery asocjacyjne

Posortowane kontenery asocjacyjne (std::set, std::map) utrzymują porządek automatycznie, opierając się o komparator. Niestandardowy komparator przekazuje się przy inicjalizacji:

struct CaseInsensitiveCompare { bool operator()(const std::string& a, const std::string& b) const { return case_insensitive_compare(a, b); } }; std::set<std::string, CaseInsensitiveCompare> words = {"Banana", "apple", "Cherry"}; // Porządek: "apple", "Banana", "Cherry"

Sortowanie własnych struktur danych

Techniki sortowania struktur

Dla typów definiowanych przez użytkownika można przeciążyć operator< albo podać zewnętrzny komparator. Przykład sortowania struktur Event według czasu:

struct Event { long seconds; char type; }; bool event_comparator(const Event& a, const Event& b) { return a.seconds < b.seconds; } Event events[] = {{1,'A'}, {3,'C'}, {2,'B'}, {4,'D'}}; std::sort(std::begin(events), std::end(events), event_comparator); /* Wynik: A, B, C, D */

Podejście z przeciążeniem operatora

Przeciążenie operator< umożliwia bezpośrednie sortowanie bez jawnych komparatorów:

struct Index { int row, col; bool operator<(const Index& other) const { return (row < other.row) || ((row == other.row) && (col < other.col)); } }; std::vector<Index> indices = {{2,2}, {0,0}, {1,0}, {2,0}}; std::sort(indices.begin(), indices.end()); // Posortowane: {0,0}, {1,0}, {2,0}, {2,2}

Zaawansowane techniki komparatorów

Mieszane sortowanie po wielu polach

Złożone porządki sortowania wymagają warstwowej logiki porównawczej. Przykład: najpierw malejąco po wzroście, następnie rosnąco po nazwie:

struct Person { double height; std::string name; }; std::vector<Person> people; std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) { if (a.height != b.height) return a.height > b.height; // Najpierw wzrost malejąco return a.name < b.name; // Nazwa rosnąco });

Porównanie krotkowe (std::tie)

Przy bardziej złożonym sortowaniu można użyć std::tie do tworzenia leksykograficznych krotek:

#include <tuple> std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) { return std::tie(b.height, a.name) < std::tie(a.height, b.name); });

Abstrakcja porządku malejącego

Opakowująca klasa uogólnia sortowanie malejące:

template <typename T> struct DescendingOrder { T value; bool operator<(const DescendingOrder& other) const { return other.value < value; // Odwrócone porównanie } }; std::vector<DescendingOrder<int>> values = {5, 3, 7, 1}; std::sort(values.begin(), values.end()); // Wynik: 7, 5, 3, 1

Wydajność i stabilność sortowania

Charakterystyka stabilności

std::sort nie jest sortowaniem stabilnym – równe elementy mogą zmieniać kolejność. Stabilność gwarantuje std::stable_sort (złożoność O(N \log^2 N)) lub sortowanie std::list::sort.

Wpływ wydajności komparatorów

Niewydajne komparatory (np. głębokie kopiowanie, kosztowne transformacje) pogarszają efektywność. Przechwytywanie przez referencję w lambdach optymalizuje wykorzystanie zasobów.

std::vector<LargeObject> items; std::sort(items.begin(), items.end(), [](const LargeObject& a, const LargeObject& b) { // Przechwytywanie przez referencję return a.key() < b.key(); });

Techniki optymalizacji

• Semantyka przenoszenia – umożliwia tanie zamiany dla własnych typów;
• Sortowanie przez projekcję – wstępne przeliczanie danych, jeśli transformacje są kosztowne;
• Dobór algorytmu – stosuj std::partial_sort dla wyboru K najlepszych elementów.

Podsumowanie

C++ oferuje rozbudowany system sortowania poprzez std::sort i metody kontenerów. Niestandardowe komparatory oraz wyrażenia lambda pozwalają na precyzyjne sterowanie porządkiem, zarówno w prostych tablicach, jak i złożonych typach użytkownika. Kluczowe aspekty to zachowanie ścisłego słabego porządku, znajomość implementacji specyficznych dla kontenerów oraz optymalizacja wydajności komparatorów. Umiejętne stosowanie tych technik umożliwia efektywne i czytelne sortowanie w różnych domenach zastosowań. Tematyka do dalszej eksploracji obejmuje sortowania równoległe (std::execution::par) czy integrację z własnymi kontenerami.

Najważniejsze rekomendacje –

1. Preferuj lambdy do jednorazowych komparatorów w celu ograniczenia zanieczyszczania przestrzeni nazw;
2. Waliduj komparatory własne na przypadkach asymetrycznych i równych wartości;
3. Stosuj std::list::sort zamiast ogólnego std::sort dla list powiązanych;
4. Wielopolowe porównania realizuj za pomocą std::tie, aby zapewnić spójność;
5. Profiluj wydajność komparatorów przy dużych zbiorach danych.