Algorithm (C++)

Hlavičkový soubor <algorithm> ze standardní knihovny C++ deklaruje různé funkce, které provádějí algoritmické operace na kontejnerech a posloupnostech reprezentovaných iterátory.^[1][2] Několik málo algoritmů je také v hlavičkovém souboru <numeric>. Všechny algoritmy jsou ve jmenném prostoru std.

Politiky provádění

Jazyk C++ umožňuje stanovit politiku provádění (též zásady provádění, anglicky execution policy), která umožňuje paralelní provádění algoritmů (pomocí vláken nebo instrukcí SIMD).

Existují čtyři různé politiky provádění s různou sémantikou určující, v jakém pořadí lze přistupovat k prvkům:

• sequenced_policy – provádění algoritmu musí probíhat ve stejném vlákně, jaké funkci volá, a přístup k prvkům musí být podle jejich pořadí; je to ekvivalentní volání funkce bez politiky provádění
• parallel_policy – provádění algoritmu může probíhat ve více vláknech, ale v rámci každého vlákna musí být přístup k prvkům prováděn postupně (tj. přístupy k prvkům se nesmí provádět současně)
• parallel_unsequenced_policy – provádění algoritmu může probíhat ve více vláknech, a přístupy k prvkům nemusí být v rámci jednoho vlákna prováděné podle jejich pořadí
• unsequenced_policy – provádění algoritmu musí probíhat v tom vlákně, které funkci volá, ale přístup k prvkům nemusí zachovávat jejich pořadí

Při používání politik, které mohou vést k provádění v různých vláknech, musí programátor zajistit, aby operace prováděné funkcemi byly vláknově bezpečné,

Rozsahy

V C++20 byly přidány algoritmy, které místo dvojic iterátorů pracují s rozsahy. Tyto funkce umožňují použít dvojici iterátor-zarážka a jsou definovány ve jmenném prostoru ranges. Tyto algoritmy nevyžadují, aby oba iterátory byly téhož typu a umožňují interoperabilitu s objekty deklarovanými v hlavičkovém souboru <ranges>, aniž by bylo nutné iterátory ručně extrahovat.

Operace s posloupnostmi bez jejich změny

Kontrola predikátů

Zjišťují, zda je zadaný predikát pravdivý pro nějakou část objektů v rozsahu, případně vrací počet objektů, pro které je predikát pravdivý:

• all_of – zadaný predikát je pravdivý pro všechny prvky v rozsahu
• any_of – zadaný predikát je pravdivý alespoň pro jeden prvek v rozsahu
• none_of – zadaný predikát není pravdivý pro žádný prvek v rozsahu
• count – vrátí, kolikrát je zadaný prvek obsažen v rozsahu
• count_if – vrací počet prvků v rozsahu, pro které je zadaný predikát pravdivý
• contains – zjišťuje, zda je zadaný prvek obsažen v rozsahu

Algoritmy porovnání

Porovná zda dva rozsahy mají určitou vlastnost:

• mismatch – najde první prvek, kterým se dva rozsahy liší
• equal – porovná, zda všechny prvky rozsahů jsou stejné
• lexicographical_compare – vrátí true, pokud první rozsah je lexikograficky před druhým
• contains_subrange – vrátí logickou hodnotu, zda druhý zadaný rozsah je obsažen v prvním zadaném rozsahu
• starts_with
• ends_with
• is_permutation

Vyhledávací algoritmy

Najde v rozsahu první nebo poslední pozici, kde následující prvky vyhovují určitému predikátu

• find
• find_if
• find_if_not
• find_last
• find_last_if
• find_last_if_not
• find_end
• find_first_of
• adjacent_find
• search
• search_n
• partition_point

Binární vyhledávací algoritmy

Poskytuje operace binárního vyhledávání pro rozsahy. Pro rozsahy, které nejsou setříděné, je výsledek nedefinovaný.

• binary_search
• upper_bound
• lower_bound
• equal_range

Algoritmy pro vyhledání minima/maxima

Vyhledá v rozsahu nejmenší nebo největší prvek podle zadaného predikátu porovnání:

• max_element
• min_element
• minmax_element

Algoritmy pro kontrolu vlastností

Kontrolují, zda má celý rozsah určitou vlastnost:

• is_partitioned
• is_sorted
• is_heap

Operace s posloupnostmi, které je mění

Kopírování

Přenáší prvky z jednoho rozsahu do jiného

• copy
• copy_if
• copy_backward
• move
• move_backward
• reverse_copy
• rotate_copy
• unique_copy
• sample

Partitioning algoritmy

Přemísťuje prvky v rozsahu na místě tak, aby rozsah byl členěn podle určité vlastnosti:

• unique
• remove
• remove_if
• partition
• partition_copy
• stable_partition

Třídicí algoritmy

Setřídí nebo částečně setřídí rozsah na místě:

• sort
• partial sort
• stable_sort
• nth_element

Vytváření rozsahů

Vytvoří daný rozsah bez čtení hodnot v něm obsažených:

• fill
• generate
• iota

Transformační algoritmy

Transformuje každý prvek daného rozsahu na místě:

• for_each
• transform
• replace
• replace_if
• clamp

Algoritmy pro přerovnání

Mění pořadí prvků v rozsahu na místě:

• shuffle
• shift_left
• shift_right
• reverse
• rotate

Heap algoritmy

Poskytuje algoritmy pro práci s binární haldou – její vytvoření, vkládání prvků, a odstraňování prvků:

• make_heap
• push_heap
• pop_heap
• sort_heap