Algoritmi

Gli algoritmi rappresentano una parte fondamentale della libreria standard C++. Gli algoritmi non funzionano con i contenitori stessi, ma piuttosto con gli iteratori. Di conseguenza, lo stesso algoritmo può essere usato dalla maggior parte dei contenitori della libreria standard C++, se non tutti. Questa sezione illustra le convenzioni e la terminologia degli algoritmi della libreria standard C++.

Osservazioni:

Le descrizioni dei modelli di funzione dell'algoritmo usano diverse frasi abbreviate:

• La frase "nell'intervallo [A, B)" indica la sequenza di zero o più valori discreti che iniziano con A fino a ma non compreso B. Un intervallo è valido solo se B è raggiungibile da A, è possibile archiviare A in un oggetto N (N = A), è possibile incrementare l'oggetto zero o più volte (++N) e fare in modo che l'oggetto sia uguale a B dopo un numero finito di incrementi (N == B).

• La frase "ogni N nell'intervallo [A, B)" indica che N inizia con il valore A e viene incrementato zero o più volte fino a quando non è uguale al valore B. Il caso N == B non è compreso nell'intervallo.

• L'espressione "il valore più basso di N nell'intervallo [A, B) tale che X" significa che la condizione X viene determinata per ogni N nell'intervallo [A, B) finché non viene soddisfatta la condizione X.

• La frase "il valore più alto di N nell'intervallo [A, B) in modo che X" indica che X è determinato per ogni N nell'intervallo [A, B). La funzione archivia in K una copia di N ogni volta che viene soddisfatta la condizione X . Se si verifica un archivio di questo tipo, la funzione sostituisce il valore finale di N, che è uguale a B, con il valore K. Per un iteratore bidirezionale o ad accesso casuale, tuttavia, può anche significare che N inizia con il valore più alto nell'intervallo e viene decrementato nell'intervallo fino a quando non viene soddisfatta la condizione X.

• Espressioni come X - Y, dove X e Y possono essere iteratori diversi da quelli ad accesso casuale, vengono considerate nel senso matematico. La funzione non valuta necessariamente l'operatore - se deve determinare tale valore. Lo stesso vale anche per le espressioni, ad esempio X + N e X - N, dove N è un tipo integer.

Diversi algoritmi usano un predicato che esegue un confronto a coppie, ad esempio con operator==, per restituire un risultato bool. La funzione predicativa operator==, o una funzione sostituiva, non deve modificare gli operandi. Deve restituire lo stesso bool risultato ogni volta che viene valutato e deve restituire lo stesso risultato se una copia di uno degli operandi viene sostituita per l'operando.

Diversi algoritmi usano un predicato che deve imporre un ordinamento di tipo "strict weak" alle coppie di elementi di una sequenza. Per il predicato pred(X, Y):

• Strict significa che pred(X, X) è false.

• Debole significa che X e Y hanno un ordinamento equivalente se !pred(X, Y) && !pred(Y, X) (X == Y non deve essere definito).

• L'ordinamento significa che pred(X, Y) && pred(Y, Z) implica pred(X, Z).

Alcuni di questi algoritmi usano in modo implicito il predicato X<Y. Altri predicati che soddisfano in genere il requisito di ordinamento debole rigoroso sono X>Y, less(X, Y) e greater(X, Y). Si noti, tuttavia, che i predicati come X<= Y e X>= Y non soddisfano questo requisito.

Una sequenza di elementi designati dagli iteratori nell'intervallo [First, Last) è una sequenza ordinata per operatore < se, per ogni N nell'intervallo [0, - LastFirst ) e per ogni M nell'intervallo (N, Last - First) il predicato !( *(First + M) < *(First + N)) è true. Si noti che gli elementi vengono ordinati in ordine crescente. La funzione operator<predicato , o qualsiasi sostituzione, non deve modificare uno dei relativi operandi. Deve restituire lo stesso bool risultato ogni volta che viene valutato e deve restituire lo stesso risultato se una copia di uno degli operandi viene sostituita per l'operando. Inoltre, deve imporre un ordinamento di tipo "strict weak" agli operandi che confronta.

Una sequenza di elementi designati dagli iteratori nell'intervallo [First, Last) è un heap ordinato da operator< se, per ogni N nell'intervallo [1,FirstLast - ) il predicato !( *First< *(First + N)) is true. Il primo elemento è il più grande. La struttura interna è nota solo alle funzioni make_heapdel modello , pop_heape push_heap. Come per una sequenza ordinata, la funzione operator<predicato , o qualsiasi sostituzione per essa, non deve modificare uno dei suoi operandi e deve imporre un ordinamento rigido debole sugli operandi confrontati. Deve restituire lo stesso bool risultato ogni volta che viene valutato e deve restituire lo stesso risultato se una copia di uno degli operandi viene sostituita per l'operando.

Gli algoritmi della libreria standard C++ si trovano nei <algorithm> file di intestazione e <numeric> .

Vedi anche

Informazioni di riferimento per la libreria standard C++
Thread Safety in the C++ Standard Library (Sicurezza dei thread nella libreria standard C++)