[C++] Algorytmy biblioteki standardowej: cheetsheet

Wprowadzenie

Biblioteka standardowa C++ (potocznie, aczkolwiek niepoprawnie zwana STLem) to nie tylko kontenery, ale także algorytmy.
Algorytmy z biblioteki standardowej są tym co warto znać, będąc więcej niż początkującym programistą C++. Standardy kodowania wielu firm programistycznych zalecają używanie algorytmów zamiast "gołych pętli". Ponadto np. certyfikaty znajomości programowania, m.in. C++ Certified Professional Programmer – CPP (udzielany przez C++ Institute), kładą bardzo duży nacisk na biegłe władanie tymi algorytmami.
W dobie AI do kodowania nadal znajomość algorytmów jest pożądana, gdyż z moich obserwacji AI samo z siebie ich nie stosuje, raczej trzeba mu napisać, że znoobił i powinien użyć algorytmów, wtedy przyzna nam racje i zrobi co sugerujemy, ale wpierw musimy znać algorytmy.

Dlaczego algorytmy lepsze od pętli

Jak to powiedział Św. Jan Paweł II: "Człowiek nie jest w stanie pracować, gdy nie widzi sensu pracy, gdy sens ten przestaje być dla niego przejrzysty, gdy zostaje mu niejako przesłonięty", tak więc poniżej zestawiam argumenty za stosowaniem algorytmów:

• Są poprawne - robiąc to samo samodzielnie jednak łatwo się pomylić
• Poprawiają czytelność - lepiej oddają intencje w zwięzłym kodzie.
• Są dojrzałe - były udoskonalane przez wiele standardów, obsługują naprawdę wiele przypadków i pamiętają o szczegółach
• Są wydajne – implementacje algorytmów z biblioteki standardowej są zwykle bardzo dopracowane. Często korzystają z trików niedostępnych (lub trudno dostępnych) w zwykłym kodzie użytkownika: lepszej współpracy z optymalizatorem kompilatora oraz niskopoziomowych instrukcji procesora (intrinsics – specjalne funkcje, które mapują się bezpośrednio na instrukcje procesora, np. SIMD). Dzięki temu potrafią być szybsze od ręcznie napisanej pętli, nawet gdy wydaje się, że pętla robi dokładnie to samo.
  
• Standardy kodowania zalecają/wymagają ich użycie - nie tylko ogólny standard kodowania CppCoreGuidelines, ale też standardy kodowania w wielu firmach specjalizujących się w pisaniu kodu.
• Przyśpieszają pisanie kodu - często jest szybciej oddelegować pracę do zaimplementowanego nazwanego algorytmu niż samemu go robić.
• Są zoptymalizowane pod przypadek ogólny.

Jak się uczyć algorytmów

Istnieje strona referencyjna zawierająca wykaz algorytmów dostępnych w bibliotece standardowej C++, ale ta lista mimo iż jest idealnym miejscem do sprawdzenia szczegółów, to jednak jest ona ciężka w nauce dla nieznających tych algorytmów. Zwłaszcza, że C++ się zmienia i pojawiają się nie tylko implementacje kolejnych algorytmów, ale też mechanizmy wpływające na prawie wszystkie algorytmy m.in. "Execution policies".

Niegdyś wspaniałym źródłem wiedzy o algorytmach jest książka STL w praktyce Scotta Meyersa - jednakże problemem jest to, że książka ta jest sprzed C++11, przez co wiele informacji się zdezaktualizowało (nawet mimo iż C++ trzyma olbrzymią kompatybilność wsteczną to jednak pewne mechanizmy wyleciały).

Rozpoczynamy naukę algorytmów

Poniżej moje przemyślenia jak się ich uczyć, oraz zestawienia tabelaryczne wraz z tym co ważne. Poniższy opis nie zastąpi szczegółowej dokumentacji na stronie CppReference, ale pozwoli ogarniać algorytmy, oraz być referencją do szybkiego sprawdzenia czy przypominania.

Warunki wstępne

Algorytmy są poniekąd zwieńczeniem biblioteki standardowej C++, wymagane jest płynne posługiwanie się C++, szablonami, wyrażeniami lambda, jak również kontenerami. Jeśli nie spełniasz tych kryteriów uzupełnij przed przejściem dalej.

Podział algorytmów

Algorytmy (w bazowej formie) dzielą się na kilka grup:

• operacje niemodyfikujące
• operacje modyfikujące

Powyższe można jeszcze podzielić bardziej szczegółowo np. (są to grupy wg uznania, nie standardu, można więc podzielić inaczej):

• podział danych: partition, partition_copy, stable_partition, partition_point, is_partitioned
• sortowania: sort, stable_sort, partial_sort, partial_sort_copy, is_sorted, is_sorted_until, nth_element
• przeszukiwania binarne: lower_bound, upper_bound, equal_range, binary_search
• operacje na zbiorach: includes, set_union, set_intersection, set_difference, set_symmetric_difference
• operacje na kopcu (nie stosie — to sterta/kopiec, binary heap, nie LIFO): push_heap, pop_heap, make_heap, sort_heap, is_heap, is_heap_until
• min/max: std::min, std::max, minmax, min_element, max_element, minmax_element, clamp
• kopiowania: copy, copy_if, copy_n, copy_backward, move, move_backward
• podmiany elementów: swap, iter_swap, swap_ranges
• generowania: fill, fill_n, generate, generate_n
• transformacji: transform, replace, replace_if, replace_copy, replace_copy_if
• usuwania: remove, remove_if, remove_copy, remove_copy_if, unique, unique_copy
• zmiany kolejności: reverse, reverse_copy, rotate, rotate_copy, shift_left, shift_right, shuffle
• próbkowania: sample
• permutacji: next_permutation, prev_permutation, is_permutation
• porównywania leksykograficznego: lexicographical_compare, lexicographical_compare_three_way
• numeryczne (nagłówek
  < numeric >
  ): iota, accumulate, reduce, inner_product, transform_reduce, partial_sum, inclusive_scan, exclusive_scan, transform_inclusive_scan, transform_exclusive_scan, adjacent_difference
• z języka C: qsort, bsearch
• inne: merge, inplace_merge (łączenie posortowanych zakresów — nie są to formalnie operacje na zbiorach, bo nie usuwają duplikatów), specjalizowane algorytmy z
  < memory >
   (uninitialized_copy, uninitialized_fill, destroy, construct_at i pokrewne)

Sposoby korzystania z algorytmów w różnych standardach C++

Zasadniczo skupię się w tym artykule na najbardziej "tradycyjnej" formie korzystania z algorytmów, czyli przez podawanie zakresów, jest to przykładowo forma:

Dlaczego zakres

Algorytmy są na tyle ogólne, że są w stanie współpracować nie tylko z kontenerami, ale też z tablicami, oraz też zakresami (ang. ranges , którym poświęciłem oddzielny artykuł). Stąd będę używał ogólnego określenia w tym artykule "zakres" - bo określa to wszystko z czym algorytmy współpracują, co prawda najczęściej będę pod spodem używał kontenerów do demonstracji algorytmów.

Jaki kawałek algorytmów będzie przedstawiony

Wszystkich algorytmów jest około stu, każdy z nich ma wiele wersji, które się zmieniały między standardami C++ (dochodziły nowsze wersje, lub się robiły bardziej ), dlatego postaram się przedstawić najważniejsze wersje, z uwzględnieniem wymagań, pewnych pułapek, często złożoności obliczeniowej, oraz też standardu C++, jednakże będą to skrótowe informacje.

Algorytmy niemodyfikujące Cheetsheet

Poniżej lista wszystkich algorytmów określonych jako niemodyfikujące. Co prawda, jak ktoś chce to może przy ich pomocy dokonać pewnych zmian (np. jeśli ww.  jako funkcje dostanie coś modyfikującego elementy, a elementy nie będą ).

Poniżej są wymienione algorytmy, niektóre z nich nie mają podanych wymagań, jednakże wymagania "oczywiste" są:

• z początku zakresu należy móc dotrzeć do końca zakresu
• równocześnie inny wątek nie powinien modyfikować zakresu

Najpierw szybki indeks do przypomnienia — pełny opis ze składnią, złożonością i uwagami jest pod tabelką (parametry skrócone: f/l = first/last, f1/l1/f2/l2 = first1/last1/first2/last2 funkcje/predykaty wg liczby argumentów: g1 = funkcja jednoargumentowa, g2 = funkcja wieloargumentowa, p1 = predykat jednoargumentowy, p2 = predykat dwuargumentowy — generator bezargumentowy (gen) nie występuje w tej sekcji, pojawi się przy algorytmach modyfikujących). Dopisek ", c2?" oznacza opcjonalny parametr porównujący dwa elementy — czyli że istnieją dwie wersje: jedna z domyślnym , a druga z możliwością wstrzyknięcia własnego "porównywacza". Typ zwracany podany jest po dwukropku;  oznacza, że zwraca iterator.

algorytm	standard	opis
for_each( f, l, g1 )->g1	C++98	Wywołaj g1 dla każdego elementu i zwróć g1
for_each_n( f, n, g1 )->it	C++17	Wywołaj g1 na pierwszych n elementach
all_of( f, l, p1 )->bool	C++11	Czy p1 prawdziwy dla wszystkich elementów?
any_of( f, l, p1 )->bool	C++11	Czy p1 prawdziwy dla co najmniej jednego elementu?
none_of( f, l, p1 )->bool	C++11	Czy wszystkie elementy nie spełniają p1?
find( f, l, value )->it	C++98	Znajdź pozycje pierwszego elementu równego value albo l
find_if( f, l, p1 )->it	C++98	Znajdź pozycje pierwszego elementu spełniającego p1 albo l
find_if_not( f, l, p1 )->it	C++11	Znajdź pozycje pierwszego elementu niespełniającego p1 albo l
find_end( f1, l1, f2, l2, c2 ? )->it	C++98	Znajdź pozycje ostatniego wystąpienie drugiego [f2,l2) zakresu w pierwszym [f1,l1)
find_first_of( f1, l1, f2, l2, c2 ? )->it	C++98	Znajdź pierwszą pozycje dowolnego elementu z zakresu [f2, l2]
adjacent_find( f, l, c2 ? )->it	C++98	Znajdź początek pierwszej pary równych sąsiednich elementów
count( f, l, value )->ptrdiff	C++98	Ile elementów równych value
count_if( f, l, p1 )->ptrdiff	C++98	Ile elementów spełnia p1
C/C++ mismatch( f1, l1, f2, c2 ? )->pair < it1, it2 > mismatch( f1, l1, f2, l2, c2 ? )->pair < it1, it2 > /* C++14, bezpieczniejsza*/	C++98 / C++14	Pierwsza para różniących się elementów z dwóch zakresów
C/C++ equal( f1, l1, f2, c2 ? )->bool equal( f1, l1, f2, l2, c2 ? )->bool /*C++14, bezpieczniejsza*/	C++98 / C++14	Czy dwa zakresy są identyczne
search( f1, l1, f2, l2, c2 ? )->it search( f1, l1, f2, l2, searcher )->it /*C++17*/	C++98 / C++17	Znajdź pierwsze wystąpienie drugiego zakresu w pierwszym
search_n( f, l, n, value, c2 ? )->it	C++98	Znajdź pozycje pierwszych n kolejnych elementów równych value

std::for_each (też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} for_each ^funkcja)
Wykonuje funkcję  dla każdego elementu zakresu —  może być funktorem, lambdą, ale też zwykłą funkcją (bez wrappera typu ). Z założenia nie modyfikuje elementów, ale jeśli podamy funktor modyfikujący, a zakres nie będzie stały (nie const-iteratory), modyfikacja się uda. Zwraca podaną funkcję/funktor — dzięki temu można odzyskać stan funktora po przejściu całego zakresu.

std::for_each_n (C++17)
Stosuje  do pierwszych  elementów od  ( ujemne to UB). W odróżnieniu od  zwraca iterator , nie obiekt  — nie da się więc odzyskać stanu funktora. Przydatne, gdy nie mamy pod ręką  albo liczy się tylko określona liczba początkowych elementów.

std::all_of / std::any_of / std::none_of (C++11)
Sprawdzają, czy predykat jest prawdziwy: dla wszystkich / dla przynajmniej jednego / dla żadnego elementu.

std::find / std::find_if / std::find_if_not (też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} find ^funkcja / _{» Język C++» standard C++» Algorytmy ♦} find_if ^funkcja)
zwraca pierwszy element równy ;  pierwszy element, dla którego predykat zwraca ;  — dla którego zwraca . Każdy z nich zwraca , gdy nic nie pasuje.

std::find_end (też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} find_end ^funkcja)
Wyszukuje ostatnie wystąpienie podzakresu wyznaczonego przez  w zakresie źródłowym . Zwraca iterator na początek znalezionej podsekwencji, lub , gdy nie znaleziono.

std::find_first_of
Zwraca pierwszy element zakresu , który jest równy któremukolwiek z elementów zakresu  (domyślnie wg ).

std::adjacent_find
Przeszukuje zakres do momentu znalezienia pierwszej pary sąsiadujących, równych sobie elementów. Zwraca iterator na pierwszy z tej pary (lub , gdy nie znaleziono).

std::count / std::count_if (też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} count ^funkcja / _{» Język C++» standard C++» Algorytmy ♦} count_if ^funkcja)
Zliczają liczbę elementów równych  / spełniających predykat. Zawsze dokładnie N porównań/wywołań predykatu — w odróżnieniu od  nie przerywają się wcześniej, bo muszą przejść cały zakres. Zwracają  (zwykle ), nie  — dla naprawdę wielkich zakresów to istotne.

std::mismatch
Zwraca pozycje z obu zakresów, w których elementy pierwszy raz się różnią.

std::equal (też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} equal ^funkcja)
Sprawdza, czy dwa zakresy są sobie równe element po elemencie.

std::search (też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} search ^funkcja)
Wyszukuje podciąg wyznaczony przez  w zakresie źródłowym . Zwraca pozycję jego początku, lub , gdy nie znaleziono.

std::search_n
Szuka pierwszego wystąpienia  kolejnych (sąsiadujących) elementów równych . Zwraca iterator na początek znalezionej podsekwencji, lub , gdy nie znaleziono; dla  zwraca . Przydatne np. do szukania "trzech kolejnych zer" w sekwencji.

Algorytmy modyfikujące

Omówione wyżej algorytmy niemodyfikujące odpowiadały na pytania „czy", „ile" i „gdzie" — żaden z nich nie zmienia zawartości zakresu (a przynajmniej nie taki jest jego zamysł, o czym była mowa przy ). Poniżej zestaw algorytmów, które albo modyfikują zakres źródłowy w miejscu, albo tworzą zmodyfikowaną kopię pod innym adresem. Grupuję je tak, jak w zestawieniu na początku artykułu.

Podział danych (partitioning)

"Partycjonowanie" to przegrupowanie zakresu tak, by elementy spełniające predykat znalazły się przed elementami go niespełniającymi (bez pełnego sortowania) — to dokładnie to, co robi krok "partition" algorytmu quicksort, i to jest chyba najlepsza analogia do zapamiętania tej grupy.

algorytm	standard	opis
partition( f, l, p1 )->it	C++98	Przegrupuj — spełniające p1 przed niespełniającymi. Zwraca punkt podziału
stable_partition( f, l, p1 )->it	C++98	Jak partition, zachowując względną kolejność w obu grupach
partition_copy( f, l, dst_true, dst_false, p1 )->pair < it, it >	C++11	Kopiuje do dwóch osobnych miejsc wg p1
is_partitioned( f, l, p1 )->bool	C++11	Czy zakres jest już podzielony wg p1
partition_point( f, l, p1 )->it	C++11	Punkt podziału już podzielonego zakresu (szukanie binarne)

std::partition / std::stable_partition
Przenoszą elementy spełniające  na początek zakresu, resztę na koniec. Zwracają iterator na pierwszy element drugiej grupy (punkt podziału). Różnica:  nie gwarantuje zachowania względnej kolejności elementów w obrębie każdej z grup (i wymaga tylko ),  tę kolejność zachowuje (kosztem wymogu  i potencjalnie gorszej złożoności, gdy brakuje dodatkowej pamięci).

std::partition_copy (C++11)
Nie modyfikuje źródła (wystarczy ) — kopiuje elementy spełniające  do , resztę do . Zwraca parę iteratorów końcowych obu miejsc docelowych. Zakresy docelowe nie mogą nachodzić na zakres źródłowy ani na siebie nawzajem.

std::is_partitioned / std::partition_point (C++11)
sprawdza (liniowo, w jednym przejściu), czy w zakresie wszystkie elementy spełniające  poprzedzają te niespełniające.  zakłada, że zakres JEST już tak podzielony (to założenie, nie coś co sprawdza — niespełnienie to UB) i szuka punktu podziału szukaniem binarnym, analogicznie do  poniżej — stąd O(log N) porównań, choć samych "kroków" iteratora może być O(N) przy iteratorach nie będących .

Sortowanie

algorytm	standard	opis
sort( f, l, c2 ? )	C++98	Sortuj cały zakres — [b]O(N log N)[/b] gwarantowane od C++11
stable_sort( f, l, c2 ? )	C++98	Sortuj zachowując kolejność elementów równych
partial_sort( f, mid, l, c2 ? )	C++98	Posortuj tylko pierwsze (mid-f) elementów
partial_sort_copy( f, l, df, dl, c2 ? )->it	C++98	partial_sort z wynikiem w osobnym miejscu
nth_element( f, nth, l, c2 ? )	C++98	Quickselect — nth trafia na docelową pozycję
is_sorted( f, l, c2 ? )->bool	C++11	Czy zakres jest posortowany
is_sorted_until( f, l, c2 ? )->it	C++11	Pierwszy element psujący posortowanie

std::sort (też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} sort ^{szablon funkcji})
Wymaga  (stąd nie zadziała bezpośrednio na  — tam trzeba użyć metody składowej ). NIE jest stabilny — elementy "równe" wg komparatora mogą zmienić względną kolejność.

std::stable_sort
Jak , ale zachowuje względną kolejność elementów "równych" wg komparatora — kluczowe przy sortowaniu wielokluczowym (np. najpierw sortujesz po nazwisku, potem stabilnie po dziale — w efekcie w obrębie działu kolejność alfabetyczna nazwisk przetrwa). Implementacja typowo korzysta z merge sort, stąd potrzeba dodatkowej pamięci dla gwarancji O(N log N); bez niej degraduje do O(N log²N).

std::partial_sort / std::partial_sort_copy
sortuje tylko fragment od  do  (wyłącznie), tak by zawierał M najmniejszych elementów całego zakresu we właściwej kolejności — reszta (od  do ) pozostaje w nieokreślonej kolejności. Klasyczne zastosowanie: "top-K najlepszych wyników" bez sortowania całości.  robi to samo, ale nie modyfikuje źródła (wystarczy ) i pisze do osobnego zakresu docelowego — liczba faktycznie posortowanych elementów to , zwracany iterator wskazuje na koniec zapisanego fragmentu.

std::nth_element
Po wywołaniu element na pozycji  to dokładnie ten element, który znalazłby się tam po pełnym posortowaniu — wszystkie elementy przed nim są , wszystkie po nim  (ale BEZ dalszego uporządkowania w obrębie tych dwóch grup). To Quickselect — średnio liniowe, znacznie szybsze niż pełne sortowanie, gdy potrzebujesz np. tylko mediany albo k-tego percentyla.

std::is_sorted / std::is_sorted_until (C++11)
zwraca ;  zwraca iterator na pierwszy element psujący porządek (lub , gdy cały zakres jest posortowany) — przydatne przy diagnozowaniu "gdzie dokładnie" dane przestają być posortowane.

Przeszukiwania binarne

Cztery poniższe algorytmy wymagają, by zakres był już posortowany (a precyzyjniej: partycjonowany względem szukanej wartości — w praktyce niemal zawsze oznacza to posortowany) — nieposortowany zakres to niezdefiniowane zachowanie, nie błąd czasu kompilacji ani wyjątek.

algorytm	standard	opis
lower_bound( f, l, value, c2 ? )->it	C++98	Pierwsza pozycja, gdzie można wstawić value zachowując porządek (pierwszy element >= value)
upper_bound( f, l, value, c2 ? )->it	C++98	Jak wyżej, ale pierwszy element > value
equal_range( f, l, value, c2 ? )->pair < it, it >	C++98	Para {lower_bound, upper_bound} — cały podzakres równy value
binary_search( f, l, value, c2 ? )->bool	C++98	Czy value istnieje w zakresie

std::lower_bound / std::upper_bound
zwraca iterator na pierwszy element NIE mniejszy od  (czyli );  — na pierwszy element ściśle większy od . Różnica tych dwóch iteratorów to liczba elementów równych  (zero, gdy value nie występuje). To budulec do wstawiania z zachowaniem sortowania: .

std::equal_range / std::binary_search (binary_search też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} binary_search ^{szablon funkcji})
to po prostu para  (choć zwykle liczona wydajniej niż dwa osobne wywołania).  zwraca tylko  — jeśli potrzebujesz też pozycji, użyj  i porównaj wynik z  (tak jest wydajniej niż wołać oba).

Operacje na zbiorach

Wszystkie poniższe wymagają posortowanych zakresów wejściowych (tym samym komparatorem, którym potem sortowany jest — i będzie — wynik) i traktują je jak zbiory/multizbiory. Zakres wyjściowy nie może pokrywać się z żadnym z wejściowych.

algorytm	standard	opis
includes( f1, l1, f2, l2, c2 ? )->bool	C++98	Czy zakres 2 jest podzbiorem (multizbioru) zakresu 1
set_union( f1, l1, f2, l2, dst, c2 ? )->it	C++98	Suma zbiorów do dst
set_intersection( f1, l1, f2, l2, dst, c2 ? )->it	C++98	Część wspólna do dst
set_difference( f1, l1, f2, l2, dst, c2 ? )->it	C++98	Elementy z zakresu 1 nieobecne w zakresie 2
set_symmetric_difference( f1, l1, f2, l2, dst, c2 ? )->it	C++98	Elementy obecne w dokładnie jednym z zakresów

std::includes
Sprawdza, czy każdy element zakresu 2 występuje w zakresie 1 z co najmniej taką samą krotnością (czyli zakres 2 jako multizbiór zawiera się w zakresie 1). Oba zakresy muszą być posortowane tym samym porządkiem.

std::set_union / std::set_intersection
Dla elementu występującego  razy w zakresie 1 i  razy w zakresie 2:  zapisze  kopii,  —  kopii. Wynik jest posortowany.

std::set_difference / std::set_symmetric_difference
:  kopii elementu (to, co zostaje z zakresu 1 po "odjęciu" zakresu 2) — niesymetryczne, kolejność argumentów ma znaczenie. :  kopii — elementy, które nie są częścią wspólną (to, co dałoby XOR na zbiorach).

Operacje na kopcu (stercie, ang. heap)

Kopiec binarny (nie mylić ze stosem/LIFO!) to struktura umożliwiająca O(log N) wstawianie i O(log N) pobranie największego (lub najmniejszego, wg komparatora) elementu — to właśnie na tych pięciu/sześciu algorytmach oparty jest std::priority_queue. Reprezentacja to zwykły zakres o dostępie swobodnym (np. ), interpretowany jako drzewo binarne wg konwencji "rodzic na indeksie i, dzieci na 2i+1 i 2i+2".

algorytm	standard	opis
make_heap( f, l, c2 ? )	C++98	Zbuduj kopiec z zakresu — [b]O(N)[/b]
push_heap( f, l, c2 ? )	C++98	Dołącz ostatni element do istniejącego kopca
pop_heap( f, l, c2 ? )	C++98	Przenieś szczyt kopca na koniec zakresu
sort_heap( f, l, c2 ? )	C++98	Posortuj kopiec (heapsort) — po tym to już nie kopiec
is_heap( f, l, c2 ? )->bool	C++11	Czy zakres spełnia własność kopca
is_heap_until( f, l, c2 ? )->it	C++11	Pierwsza pozycja psująca własność kopca

std::make_heap
Przekształca dowolny zakres w kopiec max (lub min, z odpowiednim ) w miejscu. Mimo że budowanie kopca "od zera" wygląda na O(N log N) (N wstawień razy O(log N)), sprytny algorytm Floyda robi to w O(N) — to klasyczna, trochę nieoczywista sztuczka algorytmiczna warta zapamiętania.

std::push_heap / std::pop_heap
Typowy wzorzec użycia z : żeby dodać element, najpierw  (element trafia na koniec, jeszcze poza kopcem), potem  (włącza go do kopca). Żeby zdjąć maksimum:  (przenosi maksimum na koniec zakresu i przywraca własność kopca dla reszty), potem dopiero  (fizycznie usuwa z kontenera). Same / NIE zmieniają rozmiaru kontenera — to typowy błąd dla początkujących, którzy zapominają o drugim kroku (/).

std::sort_heap / std::is_heap / std::is_heap_until (C++11)
to w istocie heapsort — powtarza  aż do wyczerpania zakresu; wynikowy zakres jest posortowany, ale przestaje być kopcem. / działają analogicznie do /.

Min / max

algorytm	standard	opis
min( a, b, c2 ? )->const T &	C++98	Mniejsza z dwóch wartości
max( a, b, c2 ? )->const T &	C++98	Większa z dwóch wartości
minmax( a, b, c2 ? )->pair < const T &, const T & >	C++11	Para {min,max} — jednym przebiegiem
min_element( f, l, c2 ? )->it	C++98	Iterator na (pierwsze) minimum zakresu
max_element( f, l, c2 ? )->it	C++98	Iterator na (pierwsze) maksimum zakresu
minmax_element( f, l, c2 ? )->pair < it, it >	C++11	Para iteratorów {min,max} zakresu
clamp( v, lo, hi, c2 ? )->const T &	C++17	Obetnij v do przedziału od lo do hi

std::min / std::max / std::minmax (min/max też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} min ^funkcja / _{» Język C++» standard C++» Algorytmy ♦} max ^{szablon funkcji})
Działają na WARTOŚCIACH, nie na zakresach (stąd brak par iteratorów) — łatwo je pomylić z / poniżej.  jest wydajniejszy niż osobne wywołanie  i  — potrzebuje najwyżej jednego porównania zamiast dwóch.

std::min_element / std::max_element / std::minmax_element (min_element/max_element też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} min_element ^funkcja / _{» Język C++» standard C++» Algorytmy ♦} max_element ^funkcja)
Tym razem działają na ZAKRESACH i zwracają iterator (nie wartość) — dzięki temu można np. dowiedzieć się, na której pozycji jest minimum, albo je potem zmodyfikować. Przy duplikatach  zwraca pierwsze wystąpienie minimum.

std::clamp (C++17)
Zwraca  gdy ,  gdy , w przeciwnym razie . Warunek wstępny:  (w przeciwnym razie UB) — najczęstszy błąd to odwrócenie kolejności argumentów.

Kopiowanie i przenoszenie

algorytm	standard	opis
copy( f, l, dst )->it	C++98	Skopiuj zakres do dst
copy_if( f, l, dst, p1 )->it	C++11	Skopiuj tylko elementy spełniające p1
copy_n( f, n, dst )->it	C++11	Skopiuj pierwsze n elementów
copy_backward( f, l, dst_last )->it	C++98	Kopiuj od końca — bezpieczne przy nakładających się zakresach
move( f, l, dst )->it	C++11	Przenieś (move) elementy do dst
move_backward( f, l, dst_last )->it	C++11	Jak move, ale od końca

std::copy / std::copy_if / std::copy_n (copy też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} copy ^funkcja)
Zwracają iterator na koniec zapisanego fragmentu w .  przy  nic nie robi i zwraca  bez zmian — nie sprawdza, czy w źródle rzeczywiście jest  elementów (to odpowiedzialność wołającego).

std::copy_backward (też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} copy_backward ^funkcja)
Kopiuje elementy zaczynając od końca zakresu ( trafia na , itd.) — dzięki temu, w odróżnieniu od zwykłego , jest bezpieczne, gdy zakres docelowy NAKŁADA się na źródłowy, o ile  nie wypada między  a  (włącznie z ). To dokładnie ta sztuczka, której implementacje kontenerów używają np. przy  w środku wektora — trzeba "przesunąć" ogon w prawo, żeby zrobić miejsce, a robienie tego od przodu nadpisałoby dane, zanim zdążysz je przeczytać.

std::move (algorytm) / std::move_backward (C++11)
Odpowiedniki /, które zamiast kopiować — przenoszą (każdy element jest efektywnie "wynoszony" przez move-assignment, po czym w źródle pozostaje w poprawnym, ale nieokreślonym stanie).

Podmiana elementów (swap)

algorytm	standard	opis
swap( a, b )	C++98 (nagłówek <utility>)	Zamień miejscami dwie wartości
iter_swap( it1, it2 )	C++98	Zamień wartości pod dwoma iteratorami
swap_ranges( f1, l1, f2 )->it	C++98	Zamień miejscami dwa zakresy element po elemencie

std::swap / std::iter_swap / std::swap_ranges (swap/iter_swap też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} swap ^{szablon funkcji} / _{» Język C++» standard C++» Algorytmy ♦} iter_swap ^funkcja)
przyjmuje iteratory (niekoniecznie tego samego typu — mogą to być iteratory dwóch różnych kontenerów, o ile przechowują ten sam typ wartości) i pod spodem woła  na wskazywanych wartościach.  to po prostu  powtórzony dla całego zakresu.

Generowanie i wypełnianie

algorytm	standard	opis
fill( f, l, value )	C++98	Wypełnij cały zakres wartością value
fill_n( f, n, value )->it	C++98	Wypełnij n elementów
generate( f, l, gen )	C++98	Wypełnij wynikami kolejnych wywołań gen()
generate_n( f, n, gen )->it	C++98	Jak wyżej, dla n elementów

std::fill / std::fill_n (też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} fill ^funkcja / _{» Język C++» standard C++» Algorytmy ♦} fill_n ^funkcja)
Proste przypisanie tej samej wartości do każdego elementu zakresu (lub pierwszych  elementów).

std::generate / std::generate_n
jest wołane BEZ argumentów dla każdej pozycji (w odróżnieniu od , gdzie funkcja dostaje elementy wejściowe) — typowe zastosowanie to generator liczb losowych albo licznik ze stanem w lambdzie (np. , choć do tego konkretnego przypadku lepiej pasuje  z , patrz niżej).

Transformacja i zastępowanie

algorytm	standard	opis
transform( f, l, dst, g1 )->it	C++98	Przekształć elementy funkcją g1 do dst
transform( f1, l1, f2, dst, g2 )->it	C++98	Jak wyżej, ale g2 bierze po jednym elemencie z dwóch zakresów
replace( f, l, old, new )	C++98	Zamień wszystkie old na new
replace_if( f, l, p1, new )	C++98	Zamień spełniające p1 na new
replace_copy( f, l, dst, old, new )->it	C++98	Jak replace, wynik w dst
replace_copy_if( f, l, dst, p1, new )->it	C++98	Jak replace_if, wynik w dst

std::transform
Wersja jednoargumentowa przekształca każdy element zakresu funkcją ; wersja dwuargumentowa bierze po jednym elemencie z dwóch zakresów naraz (np. do dodawania dwóch wektorów element po elemencie).  może być równe  (transformacja w miejscu) — to bezpieczne i częste.

std::replace / std::replace_if (też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} replace ^funkcja / _{» Język C++» standard C++» Algorytmy ♦} replace_if ^funkcja)
Modyfikują zakres w miejscu — każde wystąpienie  (lub każdy element spełniający ) zostaje nadpisane przez .

std::replace_copy / std::replace_copy_if
Nieniszczące odpowiedniki powyższych — źródło zostaje bez zmian, wynik (z podmienionymi wartościami) trafia do . To ten sam wzorzec "wersja w miejscu / wersja _copy", który zobaczysz jeszcze przy  i  poniżej.

Usuwanie i unikalność

algorytm	standard	opis
remove( f, l, value )->it	C++98	Przesuń elementy różne od value na początek — WYMAGA erase!
remove_if( f, l, p1 )->it	C++98	Jak wyżej, dla predykatu
remove_copy( f, l, dst, value )->it	C++98	Skopiuj elementy różne od value (nie modyfikuje źródła)
remove_copy_if( f, l, dst, p1 )->it	C++98	Jak wyżej, dla predykatu
unique( f, l, c2 ? )->it	C++98	Usuń SĄSIADUJĄCE duplikaty — WYMAGA erase i (zwykle) wcześniejszego sortowania!
unique_copy( f, l, dst, c2 ? )->it	C++98	Jak wyżej, nie modyfikuje źródła

std::remove / std::remove_if

std::remove_copy / std::remove_copy_if
Nieniszczący wariant — źródło zostaje bez zmian, do  trafiają tylko elementy, które PRZESZŁYBY przez  (czyli różne od  / niespełniające ). Tu nie ma pułapki z poprzedniego punktu —  to zwykły iterator wyjściowy, więc "usuwanie" jest tu dosłowne (po prostu nie kopiujemy niechcianych elementów).

std::unique / std::unique_copy
Usuwa (a precyzyjniej — tak jak , tylko PRZESUWA i zwraca nowy koniec, więc znów potrzeba ) kolejne, SĄSIADUJĄCE ze sobą duplikaty, zostawiając pierwszy element z każdej serii.

Zmiana kolejności

algorytm	standard	opis
reverse( f, l )	C++98	Odwróć kolejność elementów w miejscu
reverse_copy( f, l, dst )->it	C++98	Jak wyżej, wynik w dst
rotate( f, n_first, l )->it	C++98	Obróć — n_first staje się nowym początkiem
rotate_copy( f, n_first, l, dst )->it	C++98	Jak wyżej, wynik w dst
shift_left( f, l, n )->it	C++20	Przesuń elementy o n w lewo (zwalniając miejsce na końcu)
shift_right( f, l, n )->it	C++20	Przesuń elementy o n w prawo (zwalniając miejsce na początku)
shuffle( f, l, urng )	C++11	Losowe przetasowanie z generatorem liczb losowych

std::reverse / std::reverse_copy (też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} reverse ^funkcja / _{» Język C++» standard C++» Algorytmy ♦} reverse_copy ^funkcja)
odwraca kolejność elementów w miejscu — zamienia  z , potem  z , i tak dalej, aż pozycje się miną lub zrównają w środku zakresu (stąd wymóg  — trzeba umieć iść też "do tyłu").  nie rusza źródła — zapisuje odwróconą kolejność elementów pod  i, jak większość algorytmów z przyrostkiem , zwraca iterator na koniec zapisanego (odwróconego) zakresu w miejscu docelowym, czyli .

std::rotate / std::rotate_copy
Element wskazywany przez  staje się nowym pierwszym elementem zakresu, dotychczasowy  "zawija się" na koniec. Zwraca iterator odpowiadający pozycji, na którą trafił dawny  (czyli ). Działa już na zwykłym  (nie potrzeba nawet iteratora dwukierunkowego) — od C++11 gwarantowane jest dokładnie N zamian.

std::shift_left / std::shift_right (C++20)
Przesuwają elementy o  pozycji (odpowiednio w lewo/w prawo) za pomocą move-przypisań — miejsce zwolnione po przesunięciu zawiera elementy w nieokreślonym (ale poprawnym) stanie. Gdy  lub , zakres pozostaje bez zmian; w pozostałych przypadkach  zwraca  (nowy koniec "przesuniętej" treści), a  —  jako nowy początek.

std::shuffle (C++11)
Losowo tasuje zakres, korzystając z przekazanego generatora liczb losowych spełniającego wymogi  (np. ). Zastąpił usunięty w C++17  (który albo korzystał z globalnego, słabej jakości generatora, albo z domyślnie skonstruowanego — trudno było o powtarzalność i dobrą jakość losowości). Wymaga  (algorytm Fishera-Yatesa potrzebuje swobodnego dostępu).

Próbkowanie

std::sample (C++17)
Losuje  elementów bez powtórzeń z zakresu od  do  (a dokładniej: , gdy zakres jest krótszy niż ) i zapisuje je do , zachowując ich względną kolejność z zakresu źródłowego. Różni się od  tym, że nie tasuje całego zakresu, tylko wybiera podzbiór — klasyczne zastosowanie: reprezentatywna próbka z dużego zbioru danych bez konieczności jego kopiowania/tasowania w całości. Dla iteratorów wejściowych innych niż  używany jest algorytm zbiornikowy (reservoir sampling) — dzięki temu działa nawet, gdy nie znamy z góry rozmiaru populacji (np. strumień danych).

Permutacje

Permutacja zakresu to dowolne inne ustawienie (przestawienie) tych samych elementów w innej kolejności — zakres N-elementowy ma dokładnie N! permutacji. Permutacje można uporządkować liniowo leksykograficznie, czyli tak, jak porządkuje się słowa w słowniku: porównując kolejne elementy, aż do pierwszej różnicy (dokładnie to samo porównanie, którego formalnie dokonuje , opisany w dalszej części artykułu). Poniższe trzy algorytmy operują właśnie na tym liniowym porządku.

algorytm	standard	opis
next_permutation( f, l, c2 ? )->bool	C++98	Przekształć w następną permutację leksykograficzną
prev_permutation( f, l, c2 ? )->bool	C++98	Jak wyżej, permutacja poprzednia
is_permutation( f1, l1, f2, c2 ? )->bool	C++11	Czy zakres 1 jest permutacją zakresu 2

std::next_permutation / std::prev_permutation
Przekształcają zakres w miejsce w kolejną (lub poprzednią) permutację w porządku leksykograficznym i zwracają  — a gdy podany zakres jest już permutacją ostatnią (odpowiednio pierwszą), "zawijają" go do permutacji pierwszej (ostatniej) i zwracają . Dzięki temu klasyczna pętla "wypisz wszystkie permutacje" wygląda tak:

std::is_permutation (C++11)
Sprawdza, czy oba zakresy zawierają te same elementy z tymi samymi krotnościami, niekoniecznie w tej samej kolejności (czyli: czy jeden jest permutacją drugiego). W ogólnym przypadku wymaga to porównań rzędu O(N²) (dla dowolnego  i dowolnego predykatu równości), ale implementacje mogą przyspieszyć dla typów spełniających dodatkowe wymagania.

Porównywanie leksykograficzne

algorytm	standard	opis
lexicographical_compare( f1, l1, f2, l2, c2 ? )->bool	C++98	Czy zakres 1 jest leksykograficznie mniejszy od zakresu 2
lexicographical_compare_three_way( f1, l1, f2, l2, c2 ? )->auto	C++20	Trójstronne porównanie leksykograficzne (operator <=>)

std::lexicographical_compare
Porównuje dwa zakresy tak, jak porównuje się słowa w słowniku: element po elemencie, aż do pierwszej różnicy (a jeśli jeden zakres jest prefiksem drugiego — krótszy jest "mniejszy"). Zwraca , gdy pierwszy zakres jest leksykograficznie mniejszy od drugiego. To właśnie ten algorytm stoi pod spodem  dla ,  i innych kontenerów sekwencyjnych. Wersja z  pozwala podać własne kryterium porównania pojedynczych elementów (np. porównanie ignorujące wielkość liter) zamiast domyślnego .

std::lexicographical_compare_three_way (C++20)
Odpowiednik powyższego dla operatora trójstronnego porównania  (spaceship operator) — zamiast  zwraca kategorię porządkowania (np. ), jednym przebiegiem rozstrzygając "mniejszy / równy / większy", zamiast — jak dawniej bywało — wołać  dwukrotnie (raz dla , raz dla ) żeby dowiedzieć się wszystkich trzech możliwości.

Algorytmy numeryczne (nagłówek <numeric>)

Osobny nagłówek, ale koncepcyjnie to dalej algorytmy uogólnione — operują na zakresach przez iteratory tak samo, jak wszystko powyżej.

algorytm	standard	opis
iota( f, l, value )	C++11	Wypełnij rosnącą sekwencją value, value+1, value+2, ...
accumulate( f, l, init, g2 ? )->T	C++98	Fold w GWARANTOWANEJ kolejności lewo-do-prawa
reduce( f, l, init ?, g2 ? )->T	C++17	Jak accumulate, ale kolejność NIEOKREŚLONA (bezpieczne dla par.)
inner_product( f1, l1, f2, init, g2 ?, g2 ? )->T	C++98	Iloczyn skalarny dwóch zakresów
transform_reduce( f1, l1, f2, init, ... )->T	C++17	Map-reduce jednym wywołaniem, kolejność nieokreślona
partial_sum( f, l, dst, g2 ? )->it	C++98	Suma częściowa (prefix-sum) — i-ty = suma(0..i)
adjacent_difference( f, l, dst, g2 ? )->it	C++98	Różnice sąsiednich elementów (odwrotność partial_sum)
inclusive_scan( f, l, dst, g2 ?, init ? )->it	C++17	Jak partial_sum, kolejność nieokreślona (par.)
exclusive_scan( f, l, dst, init, g2 ? )->it	C++17	Jak wyżej, ale i-ty wynik BEZ i-tego elementu
transform_inclusive_scan( ... )->it	C++17	transform + inclusive_scan
transform_exclusive_scan( ... )->it	C++17	transform + exclusive_scan

std::iota (C++11)

Wypełnia zakres kolejnymi wartościami zaczynając od , zwiększając je przez  po każdym zapisie. Najczęstsze zastosowanie: szybkie wygenerowanie wektora indeksów .

std::accumulate / std::reduce (C++17)
to klasyczny fold: domyślnie sumuje ( dla kolejnych ), z  pozwala zastąpić dodawanie dowolną operacją — GWARANTUJE kolejność lewo-do-prawa, więc bezpiecznie użyjesz go np. do konkatenacji stringów albo mnożenia macierzy (gdzie kolejność ma znaczenie).

std::inner_product / std::transform_reduce (C++17)
domyślnie liczy iloczyn skalarny:  + Σ, z gwarantowaną kolejnością lewo-do-prawa (jak ).  to jego "nieuporządkowany", równoległo-przyjazny odpowiednik (jak  jest dla ) — dodatkowo ma wersję jednozakresową, łączącą "zmapuj funkcją, potem zredukuj" w jednym wywołaniu, bez tworzenia tymczasowego zakresu pośredniego.

std::partial_sum / std::adjacent_difference
: -ty element wyniku to suma  (suma częściowa/prefiksowa; z  — dowolna inna operacja zamiast dodawania).  robi w pewnym sensie operację odwrotną: , a dla : . Zastosowanie  po  (z tymi samymi operacjami odwrotnymi) odtwarza oryginalny zakres.

std::inclusive_scan / std::exclusive_scan (C++17)
Nieuporządkowane (równoległo-przyjazne) odpowiedniki  — wymagają operacji łącznej z tego samego powodu, co .

std::transform_inclusive_scan / std::transform_exclusive_scan (C++17)
Łączą  (zmapuj, potem zredukuj) z ideą skanu prefiksowego: najpierw stosują podaną transformację jednoargumentową do każdego elementu, potem liczą / na wynikach — bez materializowania zakresu pośredniego. Sygnatury są rozbudowane (kilka przeciążeń różniących się kolejnością/obecnością  i operacji), więc po dokładne parametry warto zajrzeć wprost do dokumentacji.

Funkcje z języka C

std::qsort / std::bsearch
Odziedziczone wprost z C (nagłówek ) — działają na surowej pamięci (), z ręcznie podanym rozmiarem pojedynczego elementu i wskaźnikiem na funkcję porównującą (zwracającą : ujemny/zero/dodatni, analogicznie do C-owego ).

Scalanie (merge)

algorytm	standard	opis
merge( f1, l1, f2, l2, dst )->it	C++98	Scal dwa posortowane zakresy do dst (wynik posortowany)
inplace_merge( f, mid, l )	C++98	Scal dwie posortowane połowy TEGO SAMEGO zakresu w miejscu

std::merge / std::inplace_merge (inplace_merge też w dokumentacji: _{» Język C++» standard C++» Algorytmy ♦} inplace_merge ^{szablon funkcji})
scala dwa JUŻ posortowane zakresy źródłowe do trzeciego, docelowego miejsca — jest stabilny (przy remisie pierwszeństwo ma element z pierwszego zakresu).  robi dokładnie to samo, ale dla dwóch sąsiadujących, posortowanych podzakresów TEGO SAMEGO zakresu (od  do  oraz od  do ), scalając je w miejscu w jeden posortowany zakres.

Operacje na pamięci nieinicjalizowanej

W odróżnieniu od scalania (wyżej) — po te algorytmy w typowym kodzie aplikacyjnym raczej nie sięgniesz. To narzędzia dla osób piszących WŁASNE kontenery. Są potrzebne, bo zwykłe / zakładają, że pod docelowym adresem już ISTNIEJE żywy obiekt (bo wykonują przypisanie, ) — użycie ich na surowej, niezainicjalizowanej pamięci (np. świeżo zaalokowanej przez , zanim jakikolwiek konstruktor tam zadziałał) to niezdefiniowane zachowanie. Algorytmy z tej grupy zamiast przypisania używają placement-new (konstruują obiekt "od zera" pod wskazanym adresem).

algorytm	standard	opis
uninitialized_copy( f, l, dst )->it	C++98	Kopiuj-konstruuj w surową (niezainicjalizowaną) pamięć
uninitialized_fill( f, l, value )	C++98	Jak wyżej, wypełniając jedną wartością
uninitialized_move( f, l, dst )->it	C++17	Przenieś-konstruuj w surową pamięć
uninitialized_default_construct( f, l )	C++17	Domyślnie skonstruuj w surowej pamięci (bez zerowania skalarów!)
uninitialized_value_construct( f, l )	C++17	Jak wyżej, ale z inicjalizacją wartością (zerowanie skalarów)
destroy( f, l ) / destroy_n / destroy_at	C++17	Wywołaj destruktor bez zwalniania pamięci
construct_at( p, args ... )->T *	C++20	Placement-new pojedynczego obiektu, przyjazny constexpr

Specjalizowane algorytmy z
Grupę dopełniają warianty  oraz przenoszące / (C++17). / pozwalają explicite wywołać destruktor/konstruktor bez zwalniania czy alokowania pamięci — to właśnie tymi cegiełkami zbudowane są od środka  i podobne kontenery.

Co nowego dla algorytmów: C++20, C++23, C++26

Powyżej, przy okazji poszczególnych algorytmów, zaznaczałem standard, w którym każdy z nich się pojawił. Poniżej krótkie, celowo zwięzłe zestawienie nowości z ostatnich trzech standardów, które NIE mają swojego klasycznego odpowiednika opisanego wyżej (bo są dostępne tylko jako /) albo dotyczą wszystkich algorytmów naraz. Pełny, dogłębny opis mechanizmu zakresów (w tym wszystkich nowych widoków/views) zostawiam oddzielnemu artykułowi — tu tylko tyle, ile potrzeba, by zorientować się "co nowego" pod kątem samych algorytmów.

C++20

Największa zmiana to oczywiście całe / (zakresowe wersje niemal wszystkich algorytmów z tego artykułu, wraz z projekcjami — możliwością posortowania np. po polu struktury bez pisania lambdy) — opisane w artykule o zakresach. Z rzeczy klasycznych (nie-zakresowych), o których już była mowa wyżej: /,  oraz polityka wykonania .

C++23

• std::ranges::contains
  /
  contains_subrange
   — czy zakres zawiera daną wartość / podzakres (bez klasycznego odpowiednika — najbliżej klasyce jest
  std::find
   + porównanie z
  last
  ).
• std::ranges::starts_with
  /
  ends_with
   — czy zakres zaczyna/kończy się danym podzakresem.
• std::ranges::fold_left
  /
  fold_left_first
  /
  fold_right
  /
  fold_right_last
  — zakresowy odpowiednik
  accumulate
   (z gwarantowaną kolejnością — brak "nieuporządkowanego" odpowiednika
  reduce
   w wersji zakresowej).
• std::ranges::find_last
  /
  find_last_if
   /
  find_last_if_not
   — odpowiedniki
  find
  /
  find_if
  /
  find_if_not
  szukające OSTATNIEGO, nie pierwszego, dopasowania (bez klasycznego odpowiednika, poza ręcznym użyciem odwróconych iteratorów).
• std::ranges::to < Container >()
  — konwersja dowolnego zakresu (w tym "leniwego" widoku) na konkretny kontener, np.
  auto v = r | std::views::filter( pred ) | std::ranges::to < std::vector >();
• Nowe widoki — m.in.
  views::zip
  ,
  views::adjacent
  ,
  views::chunk
  ,
  views::slide
  ,
  views::join_with
  ,
  views::stride
  ,
  views::cartesian_product
   — szczegóły w artykule o zakresach.

C++26

• Równoległe algorytmy zakresowe  — dotąd (C++17) polityki wykonania (
  std::execution::par
  i pozostałe, patrz wyżej) działały tylko na algorytmach klasycznych,
  std::ranges::
   (od C++20) ich nie miało. C++26 to nadrabia — algorytmy zakresowe też przyjmują teraz politykę wykonania jako pierwszy argument, np.
  std::ranges::sort( std::execution::par, v );
  . Wszystkie zastrzeżenia z sekcji o pułapkach execution policy (wyżej) dotyczą tego również.
• std::views::concat
  — łączy dowolną liczbę zakresów (niekoniecznie tego samego typu) w jeden widok, np.
  views::concat( v1, v2, v3 )
   iteruje kolejno po wszystkich trzech bez fizycznego kopiowania czegokolwiek do nowego kontenera.
• std::views::indices
  —
  views::indices( n )
   generuje
  { 0, 1, ..., n - 1 }
   z typem elementu dopasowanym do typu
  n
  . Rozwiązuje irytujący problem
  views::iota( 0, r.size() )
  , które nie kompiluje się wprost (bo
  int
   i
  size_t
   to różne typy) — teraz wystarczy
  views::indices( r.size() )
  .
• std::views::cache_latest
  — buforuje ostatnio wyliczoną wartość widoku, żeby przy łańcuchach typu
  filter | transform
   nie przeliczać tej samej transformacji za każdym razem, gdy jest ona odczytywana więcej niż raz na jedną iterację (typowy koszt "leniwych" widoków, o którym jest mowa w artykule o zakresach).
• std::views::as_input
  — wymusza potraktowanie dowolnego zakresu jako
  input_range
   (jednorazowego, jednokierunkowego), co bywa potrzebne, gdy jakiś algorytm/adapter celowo ma działać na najmniej wymagającej kategorii zakresu.
• std::ranges::generate_random
  (nagłówek
  < random >
  ) — opisane już przy
  generate
   wyżej.
• std::ranges::reserve_hint
  /
  approximately_sized_range
   — dla zakresów, których dokładnego rozmiaru nie da się tanio policzyć (np. niektóre widoki), ale da się podać jego przybliżenie — przydatne np. przy
  reserve()
   na docelowym kontenerze przed
  ranges::to
  .
• Constexpr
  stable_sort
   — dołącza do
  sort
  , który constexpr był już wcześniej; podobnie cała grupa specjalizowanych algorytmów z
  < memory >
   (opisana wyżej) staje się w pełni constexpr.
• Inicjalizacja listą dla algorytmów — drobna, ale wygodna zmiana: więcej miejsc pozwala teraz podać literał w nawiasach klamrowych tam, gdzie wcześniej trzeba było jawnie podawać typ.

Dodatek: usunięte algorytmy

Biblioteka standardowa bardzo dba o kompatybilność wsteczną — usunięcia zdarzają się rzadko. Z całego / do tej pory usunięto tak naprawdę jeden algorytm:  — oznaczony jako przestarzały (deprecated) w C++14, usunięty w C++17. Powód usunięcia: jego wersja bez jawnie podanego generatora opierała się zwykle na  i globalnym stanie losowości słabej jakości — trudno było o powtarzalność i dobrą jakość losowania. Zastępuje go opisany wyżej , wymagający jawnego podania generatora spełniającego .

Podsumowanie

Po przeczytaniu tego artykułu masz w ręku kompletną ściągę po algorytmach standardowych C++ — z tabelkami cheatsheet, do których możesz wracać bez czytania całości od nowa. Razem to 105 algorytmów (nie licząc wariantów , które doczekały się osobnego artykułu) — od  z C++98 po  z C++26.

Ważniejsza od samej listy jest jednak umiejętność, którą przy okazji nabyłeś: wiesz już, jak czytać taką dokumentację i jak się uczyć kolejnych algorytmów samodzielnie, na co zwracać uwagę. Znasz kategorie (niemodyfikujące, podział danych, sortowanie, operacje na zbiorach...), wiesz, co mówi sygnatura, złożoność i wymagana kategoria iteratora, i wiesz, gdzie sprawdzić resztę — cppreference.com aktualizuje się wraz z każdym nowym standardem, więc gdy pojawi się C++29 (czy jak go tam ostatecznie nazwą), ten sam sposób czytania dokumentacji zadziała bez żadnych zmian.

Warto też pamiętać, że biblioteka standardowa to nie koniec świata algorytmów w C++. Boost.Algorithm to swego rodzaju "poczekalnia" do standardu — sporo algorytmów, które nigdy (albo jeszcze) nie trafiły do , a bywają przydatne; podobnie jak wiele innych bibliotek Boost w przeszłości, część z nich może z czasem stać się podstawą kolejnych propozycji do standardu. Osobną, wartą uwagi kategorią są algorytmy tekstowe — o pracy z tekstem przy użyciu dostępnych narzędzi w C++ napisałem osobny artykuł.

Autor artykułu

Artykuł powstał we IX 2026, jest aktualny ze standardem C++26.

Autor	Zakres zmian	Afiliacja
Bazior Grzegorz	Utworzenie artykułu	Pracownik AGH w Krakowie