Algoritmy

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

Poznámky

Popisy funkcí šablon algoritmů používají několik zkrácených frází:

• Fráze "v rozsahu [A, B)" znamená posloupnost nula nebo více diskrétních hodnot začínající od A až po , ale bez B. Rozsah je platný pouze v případě, že je B dosažitelné z A; můžete uložit A v objektu N (NA ), zvýšit objekt nulakrát nebo vícekrát (++N) a mít objekt porovnán s B po konečném počtu přírůstků (NB).

• Fráze "each N in the range [A, B)" znamená, že N začíná hodnotou A a je narůstá nulakrát nebo vícekrát, dokud se nerovná hodnotě B. Případ NB není v rozsahu.

• Fráze "nejnižší hodnota N v rozsahu [A, B) tak, aby X" znamená, že podmínka X se určí pro každé N v rozsahu [A, B), dokud není splněna podmínka X.

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

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

K výsledku používá několik algoritmů predikát, který provádí párové porovnání, například s . operator==bool Predikátová funkce nebo jakákoli náhrada za funkci nesmí měnit operator== žádný z jejích operandů. Při každém vyhodnocení musí vést stejný výsledek, a pokud je kopie jednoho operandu nahrazena operandem, musí být výsledkem bool stejného výsledku.

Několik algoritmů využívá predikát, který musí zavést striktní slabé řazení u párů prvků ze sekvence. Predikát predikátu(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) (XY není potřeba definovat).

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

Některé z těchto algoritmů implicitně používají predikát XY. Další predikáty, které obvykle splňují striktní slabé požadavky řazení, jsou XY , (X,Y) a (X, Y). Mějte ale na vědomí, že predikáty jako X= Y a X = Y tento požadavek nesplňuje.

Sekvence prvků určených iterátory v rozsahu [ , ) je sekvence seřazená podle operátoru, pokud je pro každé N v rozsahu [0, ) a pro každý M v rozsahu First ( N Last , ) <FirstLast - FirstLast<Last - First predikát !( *( First + Last) < *( First + - )) je pravdivé. (Všimněte si, že prvky jsou seřazené vzestupně.) Predikátová funkce nebo jakákoli náhrada za funkci nesmí měnit operator< žádný z jejích operandů. Při každém vyhodnocení musí vést stejný výsledek, a pokud je kopie jednoho operandu nahrazena operandem, musí být výsledkem bool stejného výsledku. Kromě toho musí zavést striktní slabé řazení operandů, které porovnává.

Posloupnost prvků určených iterátory v rozsahu [ , ) je halda seřazená podle , pokud predikát pro každé N v rozsahu FirstLastoperator< [1, ) je FirstLast - First !( *Last< *( First + operator<)) je pravdivé. (První prvek je největší.) Jeho vnitřní struktura je jinak známá pouze funkcím šablony make_heappop_heap , a push_heap . Stejně jako u seřazené sekvence nesmí predikátová funkce ani jakékoli nahrazování změnit žádný ze svých operandů a musí zavést striktní slabé řazení operator< na operandy, které porovnává. Při každém vyhodnocení musí vést stejný výsledek, a pokud je kopie jednoho operandu nahrazena operandem, musí být výsledkem bool stejného výsledku.

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

Viz také

Referenční dokumentace standardní knihovny C++
Bezpečnost vláken ve standardní knihovně C++