Algoritmy

  • Článek

Algoritmy jsou základní součástí standardní knihovny jazyka C++. Algoritmy nefungují se samotnými kontejnery, ale spíše s iterátory. Proto stejný algoritmus může používat většina, pokud ne všechny kontejnery standardní knihovny C++. Tato část popisuje konvence a terminologii algoritmů standardní knihovny C++.

Poznámky

Popisy šablon funkcí algoritmu využívají několik zkrácených frází:

  • Fráze "v oblasti [A, B)" znamená sekvenci nulových nebo více diskrétních hodnot začínajících písmenem A až do A, ale ne včetně B. Rozsah je platný pouze v případě, že je B dostupný z A, můžete A uložit do objektu N (N = A), zvýšit objekt nulou nebo vícekrát (++N) a nechat objekt porovnat rovna B po konečném počtu přírůstků (N == B).

  • Fráze "každý N v oblasti [A, B)" znamená, že N začíná hodnotou A a je vyšší nula nebo vícekrát, dokud se nerovná hodnotě B. Případ N == B není v rozsahu.

  • Fráze "nejnižší hodnota N v oblasti [A, B) tak, aby X" znamená, že podmínka X je určena pro každý N v oblasti [A, B) až do splnění podmínky X .

  • Fráze "nejvyšší hodnota N v oblasti [A, B) tak, aby X" znamená, že X je určen pro každý N v oblasti [A, B). Funkce ukládá do K kopii N pokaždé, když je splněna podmínka X. Pokud dojde k nějakému takovému úložišti, nahradí funkce konečnou hodnotu N, která se rovná B, hodnotou K. U iterátoru s obousměrným nebo náhodným přístupem ale může také znamenat, že N začíná nejvyšší hodnotou v rozsahu a je dekrementován v rozsahu, dokud není splněna podmínka X .

  • Výrazy, jako je X - Y, kde X a Y mohou být iterátory jiné než iterátory náhodného přístupu, jsou určeny v matematickém smyslu. Funkce nemusí nutně vyhodnotit operátor - , pokud musí takovou hodnotu určit. Totéž platí i pro výrazy, jako je X + N a X - N, kde N je celočíselnou typ.

Několik algoritmů využívá predikát, který provádí párové porovnání, například s operator==, k dosažení výsledku bool . Predikát operator==nebo jakákoli náhrada za ni nesmí měnit žádný z jeho operandů. Musí mít stejný bool výsledek při každém vyhodnocení a musí přinést stejný výsledek, pokud je kopie jednoho operandu nahrazena operandem.

Několik algoritmů využívá predikát, který musí na dvojicích prvků ze sekvence uložit striktní slabé řazení. Pro predikát pred(X, Y):

  • Striktní znamená, že pred(X, X) je false.

  • Slabá znamená, že X a Y mají ekvivalentní řazení, pokud !pred(X, Y) & !pred(Y, X) (X == Y nemusí být definováno).

  • Řazení znamená, že pred(X; Y) & pred(Y, Z) znamená pred(X, Z).

Některé z těchto algoritmů implicitně používají predikát X<Y. Další predikáty, které obvykle splňují striktní slabý požadavek řazení, jsou X>Y, less(X, Y) a greater(X, Y). Všimněte si však, že predikáty, jako je X<= Y a X>= Y, nevyhovují tomuto požadavku.

Posloupnost prvků určených iterátory v oblasti [First, ) je posloupnost seřazená operátorem<, pokud, pro každý N v rozsahu [0, LastFirst - ) a pro každý M v oblasti (N, LastFirst - ) predikát !( Last *(First + M) < *(First + N)) je true. (Všimněte si, že prvky jsou seřazené vzestupně.) Predikát operator<nebo jakákoli náhrada za ni nesmí měnit žádný z jeho operandů. Musí mít stejný bool výsledek při každém vyhodnocení a musí přinést stejný výsledek, pokud je kopie jednoho operandu nahrazena operandem. Kromě toho musí na operandy, které porovnává, uložit striktní slabé pořadí.

Posloupnost prvků určených iterátory v rozsahu [First, ) je halda seřazená operator< podle toho, zda pro každý N v rozsahu [1, Last - First) predikát !( Last *První< *(First + N)) je true. (První prvek je největší.) Jeho vnitřní struktura je jinak známa pouze funkcím make_heapšablony , pop_heapa push_heap. Stejně jako u seřazené sekvence nesmí predikát operator<nebo jakákoli náhrada za něj měnit ani jeden z jeho operandů a musí na operandy, které porovnává, uložit striktní slabé pořadí. Musí mít stejný bool výsledek při každém vyhodnocení a musí přinést stejný výsledek, pokud je kopie jednoho operandu nahrazena operandem.

Algoritmy standardní knihovny jazyka C++ jsou umístěny v souborech <algorithm> hlaviček a <numeric> v nich.

Viz také

Standardní knihovna C++ – referenční dokumentace
Bezpečný přístup z více vláken ve standardní knihovně C++