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 directame nte 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;
}
Te esperamos en la segunda parte del artículo en donde hablaremos mas acerca de estos temas, los cuales hoy en día son de vital importancia en el mundo de la tecnología.
