PDF de programación - Librería estándar de plantillas (STL)

La librera estÆndar

Librera estÆndar
de plantillas (STL)

Juan Hernando Vieites



La librera estÆndar

Un pequeæo ejemplo: Un programa que lee una lista de nœmeros de la entrada

estÆndar y los imprime ordenados:
#include <vector>
#include <iterator>
#include <algorithm>
#include <iostream>
int main(int argc, char *argv[])
{
using namespace std;
vector<int> v;
istream_iterator<int> entrada(cin);
istream_iterator<int> fin;
copy(entrada, fin, back_insert_iterator<vector<int> >(v));
sort(v.begin(), v.end());
copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
std::cout << std::endl;
}



La librera estÆndar de plantillas de C++ (Standard Template Library,

STL) es un conjunto de clases y funciones genØricas.
Los componentes de la STL se agrupan en 5 clases:

Contenedores
Iteradores
Algoritmos
Objetos funcin (functors)
Objetos para manejo de memoria

La filosofa de diseæo principal de la STL es proporcionar utilidades

lo mÆs genØricas posibles, por esto, todos los componentes son
clases y funciones de plantilla



Contenedores

Un contenedor es un objeto que puede almacenar otros objetos.
Para que un objeto pueda ser contenido se le suponen algunas
propiedades dependiendo del tipo de contenedor. En general y
simplificando, basta con que:
Se pueda crear con un constructor por defecto (sin argumentos)
Se pueda copiar
Y se pueda asignar

Todos los tipos primitivos (int, char, float, double, ), los punteros y

la clase std::string pueden usarse en contenedores.

Los streams no se pueden copiar, por eso no se pueden usar

directamente.



Tipos de iteradores

Iteradores de entrada

Los iteradores se clasifican en 5 grupos dependiendo del tipo

de operaciones que soportan
Iteradores de entrada
Iteradores de salida

Iteradores hacia delante

Iteradores bidireccionales
Iteradores aleatorios

Todos los iteradores soportan construccin por defecto, por
copia, asignacin y comparacin. La comparacin entre dos
iteradores es cierta s y slo si apuntan al mismo elemento.



Iteradores de salida

En iterador de salida es un iterador que se puede usar para

modificar el valor del elemento al que apunta e incrementarlo para
pasar al siguiente elemento de la coleccin.

Siendo i un iterador de tipo X, y t un objeto del tipo apuntado, las

operaciones que soporta son:
Asignacin al elemento apuntado: *i = t
Preincremento: ++i
Postincremento: i++
Modificacin del elemento apuntado con postincremento: *i++ = t
Como antes, ninguna de las operaciones anteriores se puede
efecturar con el iterador de fin. Usar *i para leer el contenido
apuntado no estÆ definido.



En iterador de entrada es un iterador que se puede usar para

acceder al valor del elemento al que apunta y para incrementarlo
para pasar al siguiente elemento de la coleccin.

Siendo i un iterador de tipo X, las operaciones que soporta (ademÆs

de las mencionadas antes) son:
Acceso al elemento apuntado: *i
Preincremento: ++i
Postincremento: i++
Acceso al elemento apuntado con postincremento: *i++
Ninguna de las operaciones anteriores se puede efectuar con un
iterador que apunta a la posicin especial de fin (el resultado puede
ser cualquier cosa, desde valores indefinidos a una violacin de
segmento).



Iteradores hacia delante

Un iterador hacia delante es un iterador de entrada y salida a la

vez. Este es el tipo bÆsico de iterador que se utiliza en la
mayora de los casos.

Soporta tanto las operaciones del iterador de entrada como el

de salida.

Los iteradores hacia delante pueden ser a su vez inmutables o

modificables.
Modificables: los habituales, sin restricciones adicionales

Inmutables: el objeto apuntado es constante, por lo que no

se puede modificar.



Iteradores bidireccionales

Iteradores aleatorios

Los iteradores bidireccionales son iteradores hacia delante que

ademÆs soportan las operaciones siguientes:
Predecremento: --i
Postdecremento: i--

Estas operaciones s se pueden efectuar sobre el iterador de

posicin de fin siempre y cuando haya un elemento anterior, es
decir, que el iterador no apunte al principio de la coleccin o la
coleccin este vaca.



Los iteradores aleatorios son iteradores bidireccionales que ademÆs proporcionan
acceso aleatorio a cualquier posicin. Las siguientes operaciones con este tipo de
iteradores son vÆlidas
Suma: i += n, i + n, n + i el resultado es un iterador
Resta: i = n, i n, n i, el resultado es un iterador
Diferencia: i j, el resultado es la distancia entre i y j
Indexacin: i[n], acceder al elemento n-Øsimo desde i
Asignacin indexada: i[n] = t, modificar el elemento n-Øsimo desde j
Menor que: i < j, cierto si se puede llegar a j desde i.
X es el tipo del iterador, i y j iteradores, D es el tipo que mide la distancia entre
iteradores (normalmente un entero sin signo), n un objeto de tipo D y t un objeto del
tipo apuntado.
Incrementar un iterador mÆs allÆ de una posicin valida (es decir, por detrÆs del
comienzo o despuØs del fin) o acceder a una de esas posiciones es errneo y el
resultado es indefinico.



Operaciones con

contenedores

Operaciones con secuencias

Todos los objetos que son un modelo del concepto Contenedor poporcionan

Las secuencias son contenedores en los que los elementos estÆn almacenados en

los siguientes operaciones (X es el tipo del contenedor y a y b objetos de
ese tipo):
Constructor por defecto, de copia y asignacin.

Las copias siempre copian el contenedor origen elemento a elemento

a.begin(), a.end(): iteradores para recorrer el contenedor

a.size(): tamaæo actual del contenedor (nœmero de elementos

que contiene).

a.max_size(): mÆximo tamaæo que el contenedor puede llegar a tener.
a.empty(): lgicamente igual que a.size() == 0, pero puede ser mÆs rÆpido.

a.swap(b): intercambia dos contenedores, mÆs rÆpido que hacerlo con un objeto

temporal intermedio (c = a; a = b; b = c);

Comparaciones: a == b, a != b, a < b, a > b,

a <= b, a >= b. Comparacin elemento a elemento en el orden en
el que los iteradores recorren los contenedores.



Operaciones con secuencias

(continuacin)
Insercin: a.insert(i, t), inserta una copia de t antes de i (i puede ser a.end())
Insercin con tamaæo: a.insert(i, n, t), inserta n copias de t antes de la posicin

apuntada por i

Insercin por rango: a.insert(i, p, q), donde p y q son iteradores de entrada que
apuntan a objetos convertibles al tipo almacenado. Inserta una copia de [p, q)
antes de i.

Eliminacin: a.erase(i), elimina el elemento apuntado por i
Eliminacin de rango: a.erase(i,j), elimina todos los elementos en el rango [i,j)
Vaciado: a.clear(), elimina todos los elementos del contenedor.
Redimensionado con valor inicial: a.resize(n, t), redimensiona el contenedor

para que su tamaæo sea n. Si es necesario insertar nuevos elementos lo hace
copiando t tantas veces como haga falta

Redimensionado: a.resize(n), redimensiona el contenedor para que su

tamaæo sea n. Si hay que crear nuevos elementos utiliza su
constructor por defecto.



Clase std::vector

Un objecto vector es similar a un array de C, un contenedor de una

secuencia de objetos, almacenados lineal y contiguamente.

Su declaracin se encuentra en la cabecera <vector>
Un vector se caracteriza por el tipo de los objetos almacenados, su tamaæo

y su capacidad.
El tipo de los objetos almacenados se determina en la instanciacin de la

clase:
Por ej.

std::vector<int> v;
std::vector<std::vector<float> > matrix;

El tamaæo es el nœmero de elementos almacenados, mientras que la

capacidad es el nœmero total de elementos que puede llegar a albergar sin
tener que reservar nueva memoria.

La diferencia principal entre un vector y un array es que con el array



nosotros tenemos que manejar la memoria con new y delete, mientras que
vector la hace automÆticamente, por lo que es mÆs seguro.



orden lineal estricto, como en los arrays.

Las secuencias soportan insercin y eliminacin de elementos.
Siendo X el tipo del contenedor, a un objeto contenedor, i y j iteradores de tipo

X::iterator, t un objeto del tipo almacenado por X y n un nœmero entero (u objeto
convertible a tal), las operaciones vÆlidas para una secuencia son:
Constructor con valor inicial y tamaæo: X a(n, t), crea una secuencia de tamaæo n con

n copias del objeto t.

Constructor con tamaæo: X a(n), crea una secuencia de tamaæo n usando el

constructor por defecto del tipo almacenado

Constructor de rango: X(p, q), donde p y q son iteradores de entrada que apuntan a

objetos convertibles al tipo almacenado. Crea una secuencia copiando los elementos
en el rango [p, q).

Acceso al primer elemento: a.front() devuelve el primer elemento de la secuencia.

(continua en la siguiente transparencia)



Operaciones con secuencias

Existen dos tipos adicionales de secuencias que aæaden algunas operaciones

a las anteriores: secuencias con inserci(