Introducción

Una de las dificultades del lenguaje C es la implementación de contenedores (vectores, listas enlazadas, conjuntos ordenados) genéricos, de fácil uso y eficaces. Para que estos sean genéricos por lo general estamos obligados a recurrir a punteros genéricos (void *) y a operadores de cast. Es más, cuando estos contenedores están superpuestos unos a otros (por ejemplo un conjunto de vectores) el código se hace difícil de utilizar.

Para responder a esta necesidad, la STL (standard template library) implementa un gran número de clases template describiendo contenedores genéricos para el lenguaje C++. La STL además proporciona algoritmos que permiten manipular fácilmente estos contenedores (para inicializarlos, buscar valores, etc.). La STL introduce igualmente el concepto de iterador que permite recorrer fácilmente un contenedor sin tener en cuenta la manera en que ha sido implementado.

Los conceptos desarrollados en la STL han sido extendidos por la librería boost que permite manipular estructuras de gráficos genéricos.

El objetivo de esta introducción no es hacer una inventario exhaustivo de las posibilidades que ofrece la STL, sino el de dar ejemplos de uso corriente. Puedes encontrar un artículo muy detallado de las clases de la STL en el siguiente enlace: http://www.sgi.com/tech/stl/table_of_contents.html

En lo que sigue, presentaremos las clases de la STL con parámetros templates “simples”. En la práctica es posible ver a las clases de la STL como legos que pueden ser imbricados unos dentro de otros. De este modo, podremos manipular un vector de conjunto de lista de enteros (std::vector<std::set<std::list<int> > >).

Principales clases de la STL

Es muy importante elegir una clase de la STL que esté de acuerdo con lo que se necesita. Ciertas estructuras son más eficaces que otras para acceder a memoria o en términos de reasignación de memoria cuando se hacen importantes. El desafío de esta parte consiste en presentar las ventajas y desventajas de cada una de ellas.

Previamente es necesario tener algunas nociones de dificultad. Sea n el tamaño de un contenedor. Un algoritmo es llamado lineal (en O(n)) si su tiempo de calculo es proporcional a n. Igualmente, un algoritmo puede ser instantáneo (O(1)), logarítmico O(log(n)), polinomial O(n^k), exponencial O(e(n)), etc...

Para resumir, a continuación la lista de dificultades en orden creciente de la proporción de tiempo de cálculo:

• O(1)
• O(log(n))
• O(n)
• O(n^k)
• O(e(n))

Aquí nos interesaremos principalmente a la dificultad de acceso (búsqueda) a un dato almacenado en un contenedor y a la dificultad para insertar un dato.

std::pair<T1,T2>

Un par es una estructura conteniendo dos elementos eventualmente de tipos diferentes. Ciertos algoritmos de la STL (por ejemplo find) devuelven pares (posición del elemento encontrado y un booleano que indica si ha sido encontrado).

Dificultad: inserción y acceso en O(1)

#include <pair> // en la práctica este include es sobreentendido ya que implícitamente
se hace cuando utilizamos <vector>, <set> ...
#include <iostream>
#include <string>

int main(){
  std::pair<int,std::string> p = std::make_pair(5,"pouet");
  std::cout << p.first << ' ' << p.second << std::endl;
  return 0;
}

std::list<T,...>

La clase list provee una estructura genérica de listas enlazadas pudiendo eventualmente contener repeticiones.

Dificultad

• Inserción (al inicio o fin de lista): O(1)
• Búsqueda: O(n) en general, O(1) para el primer y el ultimo eslabón

Este ejemplo muestra cómo insertar los valores 4,5,4,1 en una lista y cómo mostrar su contenido:

#include <list>
#include <iostream>

int main(){
  std::list<int> ma_lista;
  ma_lista.push_back(4);
  ma_lista.push_back(5);
  ma_lista.push_back(4);
  ma_lista.push_back(1);
  std::list<int>::const_iterator
    lit (mi_lista.begin()),
    lend(mi_lista.end());
  for(;lit!=lend;++lit) std::cout << *lit << ' ';
  std::cout << std::endl; 
  return 0;
}

std::vector<T,...>

La clase vector es muy similar a la de array de C. Todos los elementos contenidos en el vector están contiguos en memoria, lo que permite acceder inmediatamente a cualquier elemento. La ventaja de vector comparada a la de array de C es su capacidad a reasignarse automáticamente en caso de que sea necesario, por ejemplo durante un push_back. Sin embargo al igual que el array clásico, el operador [] únicamente puede acceder a una casilla si ha sido asignada previamente (si no se produce un error de segmentación).

Dificultad:

• Acceso O(1)
• Inserción: O(n) al inicio del vector (pop_back), O(1) al final del vector (push_back). En los dos casos puede ocurrir una reasignación.

No hay que olvidar que una reasignación de memoria es costosa en términos de tiempo de cálculo. Así, si el tamaño de un vector es conocido de antemano, en lo posible hay que crearlo directamente con este tamaño.

Ejemplo:

#include <vector>
#include <iostream>

int main(){
  std::vector<int> mi_vector;
  mi_vector.push_back(4);
  mi_vector.push_back(2);
  mi_vector.push_back(5);
  // para recorrer un vector podemos utilizar los iteradores o los índices
  for(std::size_t i=0;i<mi_vector.size();++i) std::cout << mi_vector[i] << ' '
  std::cout << std::endl;

  std::vector<int> mi_vector(5,69); // crea el vector 69,69,69,69,69
  v[0] = 5;
  v[1] = 3;
  v[2] = 7;
  v[3] = 4;
  v[4] = 8;
  return 0;
}

std::set<T,...>

La clase set permite describir un conjunto ordenado y sin repetición de elementos. Previamente es necesario parar este orden como parámetro template (un funtor). Por defecto, el funtor std::less (basado en el operador <) es utilizado, lo que equivale a tener un conjunto de elementos clasificados del más pequeño al más grande. Concretamente, basta con implementar el operador < de una clase o una estructura de tipo T para poder definir un std::set<T>. Además, el tipo T debe disponer de un constructor vacío T().

Dificultad:

• O(log(n)) para la búsqueda e inserción. Efectivamente, la estructura std::set saca partido del orden sobre T para construir una estructura de árbol roja y negra, lo que permite la búsqueda logarítmica de un elemento

#include <set>
#include <iostream>

int main(){
  std::set<int> s; // equivale a std::set<int,std::less<int> >
  s.insert(2); // s contiene 2
  s.insert(5); // s contiene 2 5
  s.insert(2); // el repetido no es insertado
  s.insert(1); // s contiene 1 2 5
  std::set<int>::const_iterator
    sit (s.begin()),
    send(s.end());
  for(;sit!=send;++sit) std::cout << *sit << ' ';
  std::cout << std::endl;
  return 0;
}

Atención: el eliminar o agregar un elemento en un std::set vuelve invalido a sus iteradores. No se debe modificar un std::set en un bucle for basado en sus iteradores.

std::map<K,T,...>

Un map permite asociar una contraseña a un dato.

El map toma al menos dos parámetros templates:

• el tipo de la clave K
• el tipo del dato T

Al igual que std::set, el tipo K debe ser ordenado (este orden puede ser pasado como 3er parámetro template, std::less<K> par défaut) y , el tipo T solo impone tener un constructor vacio.

Dificultad:

• O(log(n)) para la búsqueda e inserción. En efecto, la estructura std::map saca partido del orden sobre T para construir una estructura de árbol rojo y negro, lo que permite una búsqueda logarítmica de un elemento.

Atención: el eliminar o agregar un elemento en un std::map vuelve invalido a sus iteradores. No se debe modificar un std::map en una bucle for basada en sus iteradores.

Atención: el hecho de acceder a una clave vía el operador [] inserta esta clave (con el dato T()) en el map. Por ello, el operador [] no es adaptado para verificar si una clave está presente en el map, es necesario utilizar el método find. Además no asegura la constancia del map (a causa de las potenciales inserciones) y por lo tanto no puede ser utilizado en un const std::map.

Ejemplo:

#include <map>
#include <string>
#include <iostream>

int main(){
  std::map<std::string,unsigned> map_mis_idx;
  map_mes_idx["enero"] = 1;
  map_mes_idx["febrero"] = 2;
  //...
  std::map<std::string,unsigned>::const_iterator
    mit (map_mis_idx.begin()),
    mend(map_mis_idx.end());
  for(;mit!=mend;++mit) std::cout << mit->first << '\t' << mit->second << std::endl;
  return 0;
}

Los iteradores

En la sección precedente vimos que los iteradores permiten recorrer fácilmente una estructura de la STL. Un iterador recuerda un poco la noción de puntero, pero no es una dirección. A continuación veremos cuatro iteradores clásicos de la STL.

Estos son definido para todas las clases de la STL dichas anteriormente (entre ellas por supuesto std::pair)

iterator y const_iterator

Un iterador (y un const_iterator) permite recorrer un contenedor de inicio a fin. Un const_iterator contrariamente a un iterator, da acceso únicamente para la lectura del elemento deseado. Así, un recorrido con const_iterator no produce cambios en el contenedor. Es por ello que un contenedor “const” puede ser recorrido por const_iterators pero no por iterators.

En general, cuando se debe elegir entre iterators y const_iterators, siempre hay que preferir los const_iterators ya que estos vuelven la sección de código a la cual sirven más genérica (aplicable a los contenedores const o no const)

• begin(): devuelve un iterador que apunta al primer elemento
• end(): devuelve un iterador que apunta justo después del ultimo elemento

++: Permite incrementar el iterador haciéndolo pasar al elemento siguiente.

Ejemplo:

<< #include <list>
#include <iostream>

const std::list<int> crear_lista(){
  std::list<int> l;
  l.push_back(3);
  l.push_back(4);
  return l;
}

int main(){
  const std::list<int> mi_lista(crear_lista());
  // no compila ya que es const
  // std::list<int>::iterator
  //  lit1 (l.begin()),
  //  lend(l.end());
  //for(;lit1!=lend1;++lit1) std::cout << *lit1 << ' ';
  //std::cout << std::endl;
  std::list<int>::const_iterator
    lit2 (l.begin()),
    lend2(l.end());
  for(;lit2!=lend2;++lit2) std::cout << *lit2 << ' ';
  std::cout << std::endl; 
  return 0;
}

reverse_iterator y const_reverse_iterator

El principio de reverse_iterator y const_reverse_iterator es similar a los iterators y const_iterator pero el recorrido se hace en el sentido opuesto.

Utilizamos:

• rbegin() : devuelve un iterador que apunta hacia el último elemento
• rend() : devuelve un iterador que apunta justo antes del primer elemento
• -- : permite disminuir el reverse_iterator haciéndolo pasar al elemento precedente.

#include <set>
#include <iostream>

int main(){
  std::set<unsigned> s;
  s.insert(1); // s = {1}
  s.insert(4); // s = {1, 4}
  s.insert(3); // s = {1, 3, 4}
  std::set<unsigned>::const_reverse_iterator
    sit (s.rbegin()),
    send(s.rend());
  for(;sit!=send;++sit) std::cout << *sit << std::endl;
  return 0;
}

... muestra:

4
3
1

Los algoritmos

Si dominas el concepto de iterador, puedes ver este documento:
http://www.sgi.com/tech/stl/table_of_contents.html

Debemos recordar algunos métodos prácticos que hemos visto como find (para los std::set y std::map) para buscar un elemento, std:fill para (re)inicializar un std::vector, algoritmos de selección, de búsqueda de min o max.

PD: El artículo original fue escrito por mamiemando, contribuidor de CommentCaMarche