ALGORITMOS
Combinando la utilización de
templates y un estilo específico para denotar tipos y variables, la STL ofrece
una serie de funciones que representan operaciones comunes, y cuyo objetivo es
"parametrizar" las operaciones en que estas funciones se ven
involucradas de modo que su lectura, comprensión y mantenimiento, sean más
fáciles de realizar.
Un ejemplo es la función copy, la cual simplemente
copia variables desde un lugar a otro. Más estrictamente, copia los contenidos
cuyas ubicaciones están delimitadas por dos iteradores, al espacio indicado por
un tercer iterador. La sintaxis es:
copy (inicio_origen, fin_origen, inicio_destino);
De este modo, todos los datos que están entre inicio_origen y
fin_origen, excluyendo el dato ubicado en este último, son copiados a un lugar
descrito o apuntado por inicio_destino.
Un algoritmo muy importante que viene implementado en la biblioteca
STL, es el sort. El algoritmo sort, ordena cualquier tipo de contenedor,
siempre y cuando se le pasen como argumentos, desde donde y hasta donde se
quiere ordenarlo.
#include <vector>
#include <deque>
#include <algorithm>
int main() {
vector<int> intVector;
intVector.push_back(60);
intVector.push_back(12);
intVector.push_back(54); //para este momento, el vector tiene 60,12,54
sort(intVector.begin(), intVector.end()); //listo, arreglo ordenado, ahora tiene 12,54,60
/*Notar que si en vez de un vector, fuese una deque, se ordenaria de la misma manera. */
}
Entre las funciones más conocidas están swap (variable1, variable2), que
simplemente intercambia los valores de variable1 y variable2; max (variable1, variable2) y su símil min (variable1, variable2), que
retornan el máximo o mínimo entre dos valores; find (inicio, fin, valor) que busca valor en el espacio de variables
entre inicio y fin; etcétera.
Los algoritmos son muy variados, algunos incluso tienen versiones
específicas para operar con ciertos iteradores o contenedores, y proveen un
nivel de abstracción extra que permite obtener un código más
"limpio", que "describe" lo que se está haciendo, en vez de
hacerlo paso a paso explícitamente.
Hemos señalado 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 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.
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; este tipo de argumentos se denomina un predicado si devuelven un booleano o un entero (que puede reducirse a un booleano. Estos argumentos son generalmente utilizados para señalar una condición o
realizar cierta computación adicional determinada por el usuario .
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<.
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
En esta sección se
incluyen algoritmos como count o search que no modifican el iterador ni los elementos de los contenedores
asociados.
Ø for_each()
Ø find()
Ø find_if()
Ø find_end()
Ø find_first_of()
Ø adyacent_find()
Ø count()
Ø count_if()
Ø mismatch()
Ø equal()
Ø search()
Ø search_n()
- Operaciones modificativas
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.
Ø 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.
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 . En el caso de accesos secuenciales le número de pasos tiende a ser
lineal.
§ lower_bound()
§ upper_bound()
§ equal_range()
§ binary_search()
Ø Composición
("Merge")
§ merge()
§ inplace_merge()
Ø Operaciones de
comprobación
Comprobar si un
conjunto es un subconjunto de otro.
§ includes()
Operaciones de álgebra
de conjuntos (solo pueden ser realizadas sobre contenedores ordenados).
§ set_union()
§ set_intersection()
§ set_difference()
§ set_symmetric_difference()
Ø Operaciones de montón
No tienen ninguna
relación con el espacio de almacenamiento persistente del mismo nombre . 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:
Ø *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.
Estas propiedades
hacen a estas estructuras muy adecuadas para manejar colas
§ 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()
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:
) 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.
(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.
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.
