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ů:

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Algorithm (C++) na anglické Wikipedii.

↑ ISO/IEC (2003). ISO/IEC 14882:2003(E): Programovací Jazyky - C++ §25 Algorithms library [lib.algorithms] para. 1
↑ STROUSTRUP, Bjarne, 2009. Programming : principles and practice using C++. Upper Saddle River, NJ: Addison-Wesley. Dostupné online. ISBN 9780321543721. S. 729. Algoritmy ve standardní knihovna jsou deklarovány v hlavičkovém souboru <algorithm>..

Externí odkazy

C++ reference for standard algorithms

[C++03_25/1-1] ISO/IEC (2003). ISO/IEC 14882:2003(E): Programovací Jazyky - C++ §25 Algorithms library [lib.algorithms] para. 1

[2] STROUSTRUP, Bjarne, 2009. Programming : principles and practice using C++. Upper Saddle River, NJ: Addison-Wesley. Dostupné online. ISBN 9780321543721. S. 729. Algoritmy ve standardní knihovna jsou deklarovány v hlavičkovém souboru <algorithm>..

[1]

[2]