Algoritmos

Los algoritmos son una parte fundamental de la biblioteca estándar de C++. Los algoritmos no funcionan con los contenedores en sí, 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

La descripción de las funciones de plantilla de algoritmo emplea varias frases de forma abreviada:

• La frase "en el intervalo [A, B)" significa la secuencia de cero o más valores discretos a partir de A hasta , pero sin incluir B. Un intervalo solo es válido si se puede acceder a B desde A; puede almacenar A en un objeto N (NA), incrementar el objeto cero o más veces (++ N ) y hacer que el objeto se compare igual a B después de un número finito de incrementos (NB).

• La frase "cada N en el 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 NB 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) tal que X" significa que X se comprueba para cada N del intervalo [A, B). La función almacena en K una copia de N cada vez que se cumple la condición X. Si se produce este tipo de almacén, 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 bidireccional o aleatorio, también puede significar que N comienza con el valor más alto del intervalo y se disminuye sobre el intervalo hasta que se cumple la condición X.

• Las expresiones como XY, 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 XN y XN, 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 resultado bool cada vez que se evalúa y debe producir el mismo resultado si una copia de cualquiera de los operandos se sustituye 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):

• Strict significa que pred(X, X) es false.

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

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

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

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

Una secuencia de elementos designada por los iteradores en el intervalo [ , ) es un montón ordenado por si, para cada N del intervalo FirstLastoperator< [1, ) First el Last - First predicado !( *Last lugar < *( First + operator<)) es true. (El primer elemento es el mayor). De lo contrario, su estructura interna solo se conoce para las funciones de plantilla make_heappop_heap , y push_heap . Al igual que con una secuencia ordenada, la función de predicado , o cualquier reemplazo para ella, no debe modificar ninguno de sus operandos y debe imponer una ordenación débil estricta en los operandos que operator< compara. Debe producir el mismo resultado bool cada vez que se evalúa y debe producir el mismo resultado si una copia de cualquiera de los operandos se sustituye por el operando.

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

Vea también

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