PDF de programación - Guía de programación C++ STL

Guía de programación C++ STL

Omer Giménez

10 de junio de 2009

Introducción

La STL (Standard Template Library) es una librería estándard de estructuras de datos y algoritmos
que forma parte del estándard del C++. Esto garantiza que cualquier compilador de C++ debe incluir
de serie esta librería, por lo que cualquier programador puede usarla para sus programas.

El objetivo fundamental de la STL es evitar que los programadores tengan que programarse, una
y otra vez, aquellos algoritmos o estructuras de datos fundamentales, como por ejemplo el algoritmo
de ordenación, o estructuras de datos como la cola de prioridades (heap) o el diccionario (map).

La STL es una librería compleja, y que internamente hace uso de características bastante avanzadas
del C++. Sin embargo, uno puede usar gran parte de la potencia que ofrece la STL de un modo
escandalosamente fácil. Mi intención al hacer estos apuntes es intentar resumir en unas pocas páginas
aquellas partes de la STL que, en mi opinión, pueden resultar de más utilidad para aquellas personas
que se estén preparando para participar en concursos de programación, como la OIE (Olimpiada
Informática Española) o el ACM-ICPC (International Collegiate Programming Contest).

Por último, sólo me queda indicar que si algún lector detecta errores (de cualquier tipo) en estos

apuntes, le rogaría que se pusiera en contacto conmigo para que pudiera corregirlos.

Omer Giménez
[email protected]

1

Capítulo 1

Vectores y matrices: vector<T>

Un vector (o tabla, o array) es la estructura de datos más básica: un contenedor que almacena
n elementos del mismo tipo en n posiciones consecutivas de memoria. Si el vector se llama v, los
elementos se denominan v[0], v[1], ..., v[n-1]. Para que tu programa use vectores, es necesario que
añadas la línea #include <vector> al principio de tu código.

¡Cuidado! En un vector v de n elementos, v[n] no existe, y el elemento v[0] existe siempre
que el vector no sea vacío, o sea, que n > 0. Un programa nunca debe leer (ni, por supuesto,
escribir) posiciones no existentes de un vector: en función del sistema operativo y de la posición
de memoria que se intente leer, puede pasar que el programa continúe, o interrumpirse debido a
un fallo de segmentación.

Avanzado. Un fallo de segmentación es el error que da el sistema operativo cuando detecta que
el programa está intentando acceder a memoria que no le corresponde. Sería ideal que siempre
que un programa accediera a una posición no reservada, el programa se interrumpiera con un
mensaje de error que avisara del error. Desgraciadamente, esto no siempre sucede así en C++,
ya que puede ser que accedamos fuera del vector pero dentro de la memoria que le corresponde
al programa. Existen distintas técnicas para detectar este tipo de errores (por ejemplo, Valgrind)
pero, con diferencia, lo más útil es intentar no cometer el error desde un principio. Por ello, hay
que tener un cuidado exquisito cada vez que escribamos [ ] en nuestros programas.

Todos los elementos de un vector son del mismo tipo, y éste se debe especificar en el momento de
crearlo: un vector<T> es un vector cuyos elementos son de tipo T. El tamaño del vector (es decir, el
número de elementos de tipo T que contiene) también se especifica en el momento de su creación; de
otro modo, el vector empieza vacío. Veamos un ejemplo.

vector<int> v(3);
vector<string> vst(10); //vector de 10 strings
vector<bool> w;

//vector de booleanos, vacio

//vector de 3 coordenadas enteras

A diferencia de los arrays tradicionales del C, los vectores puede cambiar de tamaño durante la
ejecución del programa. Más adelante veremos las instrucciones push_back y resize que nos permiten
hacerlo.

2

Avanzado. Los elementos de un vector se guardan en el heap de memoria libre, y no en la pila
del programa: en cierto modo, son equivalentes al uso del malloc del C o el new del C++, sólo que
más sencillos, puesto que no es necesario hacer nunca el free o el delete. Al modificar el tamaño
del vector la STL hace las operaciones necesarias (mover los elementos, reservar nueva memoria,
etc.). Como es de suponer, esto tiene un coste, por lo que es preferible evitar las instrucciones
que cambian el número de elementos de un vector.

Al crear un vector<T> se nos permite pasar un segundo parámetro, de tipo T, que indica el valor
por defecto con el cual se inicializan los elementos del vector. Si no se especifica ningún valor, como
en los ejemplos anteriores, se escoge el valor por defecto del tipo T, que es 0 para int, char, double,
etc., false para bool, o "" (cadena vacía) para string.

Para trabajar con un vector<T>, al igual que con todas las estructuras de datos que veremos
de la STL, se suelen usar los métodos que la estructura ofrece. Es fácil encontrar en la web pági-
nas que describen qué métodos usar, y qué hacen estos métodos (podéis consultar, por ejemplo,
la documentación oficial del vector<T> de la STL, aunque fácilmente encontraréis muchísimos tutori-
ales, tanto en español como en inglés, que expliquen lo mismo). Por ejemplo, cuando escribimos v[3],
en realidad estamos llamando al método T &vector<T>::operator[](int i) del vector<T> v: un
método que recibe un entero i y que devuelve (una referencia a) el valor que v contiene en la i-ésima
posición.

Otros métodos que tiene el vector v son v.size() (devuelve el tamaño del vector), v.push_back(e)
(añade un elemento e a v, incrementando en 1 su tamaño), v.resize(n) (modifica el tamaño de v
para que pase a valer n, borrando o añadiendo elementos al final, según convenga).

Los vectores, al igual que todas los contenedores de la STL, tienen la muy útil propiedad de
actuar como variables normales y corrientes: podemos asignarlos, compararlos, copiarlos, pasarlos
como parámetro, hacer que una función los devuelva, etc. Por ejemplo, podemos escribir código como
éste:

vector<int> v(10, 3);
vector<int> w = v;
++v[0];
w.resize(0);
v = w;
bool iguales = v==w; //iguales vale true

//w es una copia de v
//v y w son ahora distintos
//ahora w esta vacio
//ahora v tambien esta vacio

Avanzado Ésta es una propiedad única que tienen los vectores de la STL (y, en general, todas
las estructuras de la STL), y que no comparten ni los arrays tradicionales de C, ni otros tipos
de vectores de otros lenguajes, como por ejemplo Java. A esta propiedad se la denomina value
semantics (semántica de valor).

En concreto, si tenemos dos vectores del mismo tipo T, podemos asignar uno al otro con el igual
=, y compararlos con el doble igual == o el símbolo de distinto !=. También podemos compararlos con
el <, >, >=, <=. Los vectores se comparan según el orden lexicográfico, que es el orden con el que se
ordenan las palabras del diccionario: se usa el primer elemento del vector para decidir qué vector va
antes; en caso de empate, se mira el segundo elemento, y así sucesivamente.

vector<char> v(2), w;
v[0] = v[1] = ’a’;
w = v;

3

w[1] = ’z’; //v == {’a’,’a’}, w == {’a’,’z’}
cout << "v<w?" << (v<w) << endl; //true

¡Cuidado! Es necesario que el tipo T sea comparable; de otro modo, no podrían compararse
los vectores. Casi todos los tipos del C++ y la STL son comparables entre sí, por lo que esto no
suele ser un problema, a menos que T sea una class o struct definida por nosotros mismos sin
un operador de comparación <.

Los programadores de C, acostumbrados a trabajar con arrays, suelen olvidarse de la facilidad con
la que los vectores pueden ser pasados como parámetros o ser devueltos por funciones, de una forma
cómoda y, generalmente, eficiente. Por ejemplo:

vector<int> lee_vector() {

int n;
cin >> n;
vector<int> v(n);
for(int i=0;i<n;++i) cin >> v[i];
return v;

}

void escribe_vector(const vector<int> &v) {

for(int i=0;i<v.size()-1;++i) {

cout << v[i] << " ";

}
if (v.size()>0) cout << v[v.size()-1];
cout << endl;

}

void pon_a_cero(vector<int> &v) {

for(int i=0;i<v.size();++i) v[i]=0;

}

¡Cuidado! Los vectores y, en general, todos los tipos de la STL, tienen lo que se llama semántica
de valor que, además de otras cosas, quiere decir que cuando pasamos un vector como parámetro
en una función, lo que se hará es copiar todos sus datos a la función que lo recibe. ¡Esto puede ser
brutalmente lento! Por lo tanto, siempre que pasamos un vector u otro contenedor de la STL por
parámetro es conveniente pasarlo como en el ejemplo anterior: const vector<T> & si no vamos
a modificar el vector, y vector<T> & si nuestra intención es modificarlo. Esto garantiza que, en
ambos casos, la función trabajará con el vector original, y no con una copia del mismo. Hay que
tener cuidado con este error, ya que puede hacer que un programa que aparentemente funciona
para casos pequeños tarde mucho más tiempo del necesario en resolver entradas grandes.

Avanzado. Parecería que las funciones que devuelven vectores también pueden sufrir este prob-
lema de copias innecesarias, por ejemplo en vector<int> v = lee_vector(). Sin embargo, en
casos como éste donde se está creando el contenedor v, el compilador detecta que la copia es
innecesaria, y hace la correspondiente optimización. Esta optimización no se haría si se hubiera
escrito vector<int> v; v=lee_vector();.

4

Otra de las ventajas de los vectores sobre los arrays clásicos es que resultan muy prácticos para
almacenar una lista de elementos el tamaño de la cual pueda ir aumentanto. Para ello, se usa el método
push_back del vector.

int main() {

string palabra;
vector<string> vs;
while (cin >> palabra) {
vs.push_back(palabra);

}
cout << "Palabras leidas: " << vs.size() << endl;

}

Ésta es una de las pocas excepciones a la regla de no cambiar a menudo el tamaño de un vector: el

código anterior es razonablemente eficiente.

Avanzado. El motivo es que la STL reserva un espacio de memoria libre después del vector,
de modo que éste pueda incrementar su tamaño sin que sea necesario pedir nueva