Disponible la nueva versión "donationware" 7.3 de OrganiZATOR
Descubre un nuevo concepto en el manejo de la información.
La mejor ayuda para sobrevivir en la moderna jungla de datos la tienes aquí.

Curso C++

[Home]  [Inicio]  [Índice]


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
  • 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 ( xxx).

    • 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 1.8-2). 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.

    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 ( 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:

    • *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:

  • 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.

  Inicio.


[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().