5.1.3 Algoritmos
§1 Sinopsis
Hemos señalado ( 5.1)
que los contenedores pueden ser considerados como estructuras de datos y que los algoritmos
son como operadores que actúan sobre los elementos de estas estructuras. Hemos señalado también que en la STL los algoritmos
adoptan la forma de funciones que incluyen iteradores entre sus argumentos, lo que les permite manipular los elementos de
los contenedores subyacentes. En el contexto de la STL, un algoritmo genérico es un algoritmo
(
1.2.1) que no
pertenece a ningún tipo particular de contenedor; obtiene información sobre la forma de manipular los tipos que usa a través del
análisis de los argumentos que se le pasan.
La STL ofrece un conjunto de algoritmos que puede evitarnos tener que escribir los detalles de ciertas manipulaciones de datos que se repiten una y otra vez (por ejemplo rutinas de ordenación). Generalmente están contenidos en la cabecera <algorithm> y generalmente conducen a un código increíblemente rápido y compacto, en sustitución de lo que serían varias páginas de código si tuviésemos que escribirlo por nuestros propios medios partiendo de cero.
Como en el caso de los iteradores, los algoritmos de la STL utilizan una interfaz homogénea cualquiera que sea el tipo de objeto (contenedor) sobre el que se apliquen. Esto permite que los conocimientos obtenidos del estudio de uno de ellos puedan ser extendidos a los demás y que su dominio no sea tan difícil como lo sería de no mantenerse este isomorfismo.
Nota: los algoritmos no están supeditados a operar exclusivamente sobre las estructuras de datos (contenedores) definidas en la STL. También pueden operar sobre clases definidas por el usuario, a condición de que estas proporcionen punteros que satisfagan las premisas exigidas por los algoritmos a sus argumentos.
§2 Formas
Un concepto de vital importancia para entender la mecánica de la STL es que los algoritmos no
operan sobre los contenedores, sino sobre sus elementos.
De forma que en ningún caso alteran la estructura de datos como tal, sino los
elementos que la componen, o su orden interno. En ocasiones pueden copiar
total o parcialmente el contenido de un contenedor en otro.
En ciertos casos, los algoritmos que alteran el contenido del contenedor se presentan en dos versiones denominadas "in-situ" ("In-place") y de copia. La primera altera el contenido del original, la segunda produce una copia con el contenido modificado [2]. Estas últimas se distinguen por que presentan la terminación _copy en el nombre del algoritmo. Por ejemplo, replace() y replace_copy().
En ocasiones los algoritmos aceptan una función o un objeto-función como
argumento ( 5.1.3a1);
este tipo de argumentos se denomina un predicado si devuelven un booleano o un entero (que puede reducirse a un booleano
3.2.1b). Estos argumentos son
generalmente utilizados para señalar una condición o realizar cierta computación adicional determinada por el usuario
(
5.1.3a).
Los algoritmos de ordenación y similares se presentan en dos versiones: una acepta como argumento un objeto-función, la otra utiliza para las comparaciones la función-operador operator<.
§3 Clasificación
Aunque los sistemas de clasificación son siempre artificiosos, máxime cuando se trata de este tipo de entidades, seguiremos aquí la pauta de la mayoría de libros sobre la STL ofreciendo una clasificación de los más de 60 algoritmos ofrecidos por la Librería Estándar. La que sigue es la utilizada en el Estándar que los agrupa en tres grandes grupos y algunos subgrupos:
- Operaciones no-modificativas
- for_each()
- find()
- find_if()
- find_end()
- find_first_of()
- adyacent_find()
- count()
- count_if()
- mismatch()
- equal()
- search()
- search_n()
- Operaciones modificativas
copy()
swap()
transform()
replace()
fill()
generate()
remove()
unique()
reverse()
rotate()
random_shuffle()
partition()
- Operaciones de ordenación y similares
- Ordenación
- sort()
- stable_sort()
- partial_sort()
- partial_sort_copy()
- Elemento enésimo
- nth_element()
- Búsqueda binaria.
- lower_bound()
- upper_bound()
- equal_range()
- binary_search()
- Composición ("Merge")
- merge()
- inplace_merge()
- Operaciones de comprobación
- set_union()
- set_intersection()
- set_difference()
- set_symmetric_difference()
- Operaciones de montón
- *a es el mayor elemento del rango.
- *a puede ser eliminado del conjunto mediante una operación pop_head(), también puede ser colocado un nuevo elemento en esta posición mediante una operación push_head() en un tiempo que está en relación logarítmoca con el número de elementos en el montón.
- push_heap()
- pop_heap()
- make_heap()
- sort_heap()
- Mínimos y máximos
- min()
- max()
- min_element()
- max_element()
- Comparaciones lexicográficas
- lexicographical_compare()
- Generadores de permutaciones
- next_permutation()
- prev_permutation()
En esta sección se incluyen algoritmos como count o search que no modifican el iterador ni los elementos de los contenedores asociados.
En esta sección se incluyen algoritmos que realizan modificaciones en el iterador y/o en los elementos de los contenedores
asociados. Comprende doce funciones genéricas que se presentan en varias versiones
( xxx).
En esta sección se incluyen algoritmos que realizan búsquedas binarias, lo que supone que la búsqueda se realiza sobre
estructuras de datos (contenedores) ordenados según cierto criterio. Trabajan con iteradores aleatorios y secuenciales, aunque
son especialmente adecuadas para los primeros, ya que para cualquier búsqueda, realizan un número logarítmico de pasos por la
estructura (ver árboles binarios
1.8-2). En el caso de accesos secuenciales le número de pasos tiende a ser lineal.
Comprobar si un conjunto es un subconjunto de otro.
Operaciones de álgebra de conjuntos (solo pueden ser realizadas sobre contenedores ordenados).
No tienen ninguna relación con el espacio de almacenamiento persistente del mismo nombre
( 1.3.2). Un montón ("Heap")
es también un tipo especial de organización de datos entre dos límites; en estos casos ambos límites están definidos por dos
iteradores a y b, con las siguientes propiedades:
Estas propiedades hacen a estas estructuras muy adecuadas para manejar colas
Además de las anteriores, el Estándar C++ define un par de
algoritmos para sustituir a dos utilidades del mismo nombre existentes en la
primitiva librería C Estándar. Son las funciones bsearch() y qsort().
Por supuesto pueden plantearse muchas otras clasificaciones para los algoritmos según el
criterio que se considere más relevante. Sin embargo, los criterios de clasificación más
significativos (que coinciden aproximadamente con los utilizados por el Estándar
) son los siguientes:
- Si el algoritmo es o no modificativo, en el sentido de alterar el contenido del contenedor.
- El tipo de iterador que acepta como argumento
- Si el algoritmo exige actuar sobre un contenedor previamente ordenado, o puede actuar sobre contenedores sin ordenar.
Nota: un algoritmo puede exigir ciertas condiciones adicionales para que pueda ser
utilizado sobre un contenedor. Por ejemplo, la mayoría de algoritmos de
modificación de estructuras ordenadas
(cuyos nombres comienzan por set_) requieren un contenedor ordenado, y
además, que el criterio utilizado en la ordenación coincida con el de la
función y objeto utilizado por el algoritmo.
§4 Complejidad
La librería Estándar es singular en el sentido que la norma señala lo que se denomina complejidad de cada algoritmo. En la descripción que acompaña a cada algoritmo en el documento oficial hay un apartado ("Complexity") en el que pueden encontrarse expresiones del siguiente tenor [1]:
Complexity: Exactly ( last first)/2 swaps.
Complexity: At most ( last first)* log( last first) swaps.
Complexity: Approximately N log N (where N == last first)
Complexity: It does at most N(log N)2 (where N == last first) comparisons; if enough extra memory is available, it is N log N.
Lo que se pretende indicar es el grado de eficacia que puede esperarse del
algoritmo en el peor de los casos, y operando sobre un
número suficientemente grande de elementos de un contenedor. Su
singularidad reside en que hasta ahora no había sido usual que ningún
fabricante de algoritmos garantizara su rendimiento de ningún modo. Su
importancia estriba en que esta indicación puede ser de gran ayuda a la hora
de decidir la utilización de un algoritmo u otro; e indirectamente sobre el
tipo de contenedor a utilizar.
La complejidad señala el tiempo que emplea el algoritmo en realizar la computación correspondiente sobre un contenedor. Naturalmente esto depende del número de elementos de la serie sobre la que se ejecuta. En unos casos es constante (independiente del número de elementos); en otros casos es lineal (una función constante del número de elementos); finalmente en ciertos casos es una función de otro tipo, que crece exponencialmente con el tamaño del contenedor asociado.
Es importante no perder de vista las condiciones para las que se garantiza la eficacia, que se refieren a operación sobre un número suficientemente grande de elementos, y que el valor mostrado corresponde al peor escenario posible. Es frecuente que en condiciones reales, con número no excesivamente pequeños de elementos, el rendimiento de los algoritmos de la STL sea muy superior al indicado, por lo que si diseñamos aplicaciones medianamente importantes se recomienda realizar pruebas comparativas con ficheros representativos de las condiciones reales.
En ocasiones es frecuente también encontrar referencias a la complejidad amortizada que se refiere al tiempo de realizar una operación sobre N elementos dividido por el número de ellos. Viene a ser una indicación del tiempo medio que se emplea en la operación del algoritmo sobre un miembro de un contenedor.
[1] Hemos respectado la redacción original inglesa porque su interpretación es muy sencilla.
[2] El Estándar señala que la decisión de incluir o no la versión copia se basa en consideraciones de rendimiento. Cuando el costo de la operación realizada por el algoritmo prevalece sobre el de realizar la copia, esta última no se realiza. Por ejemplo, no existe una versión sort_copy() porque el coste de la ordenación es mucho más significativo que el de la copia. Además, en caso necesario siempre puede realizarse una copia seguida de un sort().