Algoritmos

Los algoritmos son una parte fundamental de la biblioteca estándar de C++. Los algoritmos no funcionan con contenedores, sino con iteradores. Por lo tanto, la mayoría de los contenedores de la biblioteca estándar de C++, si no todos, pueden usar el mismo algoritmo. En esta sección se tratan las convenciones y la terminología de los algoritmos de la biblioteca estándar de C++.

Comentarios

Las descripciones de las plantillas de función de algoritmo emplean varias frases abreviadas:

• La frase "en el intervalo [A, B)" significa la secuencia de cero o más valores discretos que comienzan por A hasta pero no incluye B. Un intervalo solo es válido si B es accesible desde A, puede almacenar A en un objeto N (N = A), puede incrementar el objeto cero o más veces (++N) y hacer que el objeto compare igual a B después de un número finito de incrementos (N == B).

• La frase "cada N del intervalo [A, B)" significa que N comienza con el valor A y se incrementa cero o más veces hasta que es igual al valor B. El caso N == B no está en el intervalo.

• La frase "el valor más bajo de N en el intervalo [A, B) tal que X" significa que la condición X se comprueba para cada N del intervalo [A, B) hasta que la condición X se cumple.

• La frase "el valor más alto de N en el intervalo [A, B) de modo que X" significa que X se determina para cada N del intervalo [A, B). La función almacena en K una copia de N cada vez que la condición X se cumple. Si se produce un almacén de este tipo, la función reemplaza el valor final de N, que es igual a B, por el valor de K. Sin embargo, para un iterador de acceso aleatorio o bidireccional, también puede significar que N comienza con el valor más alto del intervalo y se disminuye en el intervalo hasta que se cumpla la condición X.

• Las expresiones como X - Y, donde X e Y pueden ser iteradores distintos de los iteradores de acceso aleatorio, se han diseñado en el sentido matemático. La función no evalúa necesariamente el operador - si debe determinar este valor. Lo mismo se aplica a expresiones como X + N y X - N, donde N es un tipo entero.

Varios algoritmos hacen uso de un predicado que realiza una comparación en pares, como con operator==, para producir un resultado bool. La función de predicado operator==, o cualquiera que la sustituya, no debe modificar ninguno de sus operandos. Debe producir el mismo bool resultado cada vez que se evalúa y debe producir el mismo resultado si se sustituye una copia de cualquiera de los operandos por el operando.

Varios algoritmos hacen uso de un predicado que debe imponer una ordenación débil estricta en pares de elementos de una secuencia. Para el predicado pred(X, Y):

• Estricta significa que pred(X, X) es falso.

• Débil significa que X e Y tienen una ordenación equivalente si !pred(X, Y) && !pred(Y, X) (X == Y no es necesario definir).

• La ordenación significa que pred(X, Y) && pred(Y, Z) implica pred(X, Z).

Algunos de estos algoritmos usan implícitamente el predicado X<Y. Otros predicados que normalmente satisfacen el requisito estricto de ordenación débil son X>Y, less(X, Y) y greater(X, Y). Sin embargo, tenga en cuenta que los predicados como X<= Y y X>= Y no cumplen este requisito.

Una secuencia de elementos designados por los iteradores del intervalo [First, Last) es una secuencia ordenada por operator< si, para cada N del intervalo [0, Last - First) y para cada M del intervalo (N, Last - First), el predicado !(*(First + M) < *(First + N)) es verdadero. (Tenga en cuenta que los elementos se ordenan en orden ascendente). La función de predicado operator<, o cualquier reemplazo para ella, no debe modificar ninguno de sus operandos. Debe producir el mismo bool resultado cada vez que se evalúa y debe producir el mismo resultado si se sustituye una copia de cualquiera de los operandos por el operando. Además, debe imponer una ordenación débil estricta en los operandos que compara.

Una secuencia de elementos designados por los iteradores del intervalo [First, Last) es una secuencia de montón ordenada por operator< si, para cada N en el intervalo [1, Last - First), el predicado (*First< *(First + N)) es verdadero. (El primer elemento es el más grande). Su estructura interna solo se conoce con las funciones de plantilla make_heap, pop_heap y push_heap. Al igual que con una secuencia ordenada, la función de predicado operator<, o cualquiera que la sustituya, no debe modificar ninguno de sus operandos, y debe imponer una ordenación débil estricta en los operandos que compara. Debe producir el mismo bool resultado cada vez que se evalúa y debe producir el mismo resultado si se sustituye una copia de cualquiera de los operandos por el operando.

Los algoritmos de la biblioteca estándar de C++ se encuentran en los archivos de encabezado <algorithm> y <numeric>.

Consulte también

Referencia de biblioteca estándar de C++
Seguridad para subprocesos en la biblioteca estándar de C++