STL en C++: qué es y cómo utilizarlo

STL en C++: qué es y cómo utilizarlo

Una de las principales dificultades del lenguaje C es la implementación de contenedores (vectores, listas enlazadas, conjuntos ordenados). En este artículo hacemos un recorrido por las clases de la librería STL (standard template library) para evitar errores y manipular fácilmente los contenedores.

¿Cuáles son las principales clases de la STL?

Es muy importante elegir una clase de la STL adecuada. Ciertas estructuras son más eficaces que otras para acceder a la memoria o en términos de reasignación de memoria. El desafío en esta parte consiste en analizar las ventajas y desventajas de cada una de ellas.

Es necesario tener algunas nociones previas. Sea n el tamaño de un contenedor, un algoritmo es llamado lineal (en O(n)) si su tiempo de cálculo es proporcional a n. De la misma forma, un algoritmo puede ser instantáneo (O(1)), logarítmico O(log(n)), polinomial O(n^k), exponencial O(e(n)), etc.

A continuación, una lista 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 interesamos principalmente por la dificultad de acceso (búsqueda) a un dato almacenado en un contenedor y a la dificultad para insertar un dato.

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

std::pair<T1,T2>

Un par es una estructura que contiene dos elementos de distintos 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 último 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 al 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 de reasignar 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. De lo contrario se producirá 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 del tiempo de cálculo. Así, cuando el tamaño de un vector es conocido de antemano, hay que crearlo directamente con dicho 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.Es necesario parar este orden como parámetro template (un funtor) previamente. 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: Eliminar o agregar un elemento en un std::set vuelve inválidos sus iteradores. No se debe modificar un std::set en un bucle for basado en sus iteradores.

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

Map permite asociar una contraseña a un dato.

Toma al menos dos parámetros template:

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

Al igual que std::set, el tipo K debe de ser ordenado (puede ser pasado como tercer parámetro template, std::less<K> por defecto) y, el tipo T solo impone tener un constructor vacío.

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: Eliminar o agregar un elemento en un std::map vuelve inválidos sus iteradores. No se debe modificar un std::map en una bucle for basada en sus iteradores.

El hecho de acceder a una clave con el operador [] inserta esta clave (con el dato T()) en el map. Por ello, el operador [] no está adaptado para verificar si una clave está presente en el map. Para ello 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.</bold>

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;
}

¿Qué son 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 a la noción de puntero, pero no es una dirección. A continuación veremos cuatro iteradores clásicos de la STL.

Estos son definidos para todas las clases de la STL mencionadas anteriormente.

iterator y const_iterator

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

En general, cuando se debe elegir entre iterator y const_iterator son preferibles los const_iterators. Estos hacen la sección de código 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 a justo después del último elemento
  • ++: Permite incrementar el iterador pasándolo 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

reverse_iterator y const_reverse_iterator son similares a iterator y const_iterator pero el recorrido se hace en el sentido opuesto.

Utilizamos:

  • rbegin(): Devuelve un iterador que apunta al ú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

¿Qué algoritmos podemos utilizar?

Debemos recordar algunos métodos prácticos que hemos visto cómo 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, etc.

Lenguajes