Stl Espa Ol

Gu´ıa de programaci´on C++ STL
Omer Gim´enez
10 de junio de 2009

Introducci´
on
La STL (Standard Template Library) es una librer´ıa est´
andard de estructuras de datos y algoritmos
que forma parte del est´
andard 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 fundamentalde 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´
on, 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, unopuede usar gran parte de la potencia que ofrece la STL de un modo
escandalosamente f´acil. Mi intenci´
on al hacer estos apuntes es intentar resumir en unas pocas p´aginas
aquellas partes de la STL que, en mi opini´on, pueden resultar de m´as utilidad para aquellas personas
que se est´en preparando para participar en concursos de programaci´on, como la OIE (Olimpiada
Inform´
atica Espa˜
nola) o elACM-ICPC (International Collegiate Programming Contest).
Por u
´ltimo, s´
olo me queda indicar que si alg´
un lector detecta errores (de cualquier tipo) en estos
apuntes, le rogar´ıa que se pusiera en contacto conmigo para que pudiera corregirlos.

Omer Gim´enez
omer.gimenez@gmail.com

1

Cap´ıtulo 1

Vectores y matrices: vector
Un vector (o tabla, o array) es la estructura de datos m´as b´asica: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˜
nadas la l´ınea #include al principio de tu c´odigo.
¡Cuidado! En un vector v de n elementos, v[n] no existe, y el elemento v[0] existe siempre
que el vector nosea vac´ıo, o sea, que n > 0. Un programa nunca debe leer (ni, por supuesto,
escribir) posiciones no existentes de un vector: en funci´on del sistema operativo y de la posici´on
de memoria que se intente leer, puede pasar que el programa contin´
ue, o interrumpirse debido a
un fallo de segmentaci´
on.

Avanzado. Un fallo de segmentaci´
on es el error que da el sistema operativo cuando detecta que
elprograma est´
a intentando acceder a memoria que no le corresponde. Ser´ıa ideal que siempre
que un programa accediera a una posici´on 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. Existendistintas t´ecnicas para detectar este tipo de errores (por ejemplo, Valgrind)
pero, con diferencia, lo m´as u
´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 ´este se debe especificar en el momento de
crearlo: un vector es un vector cuyoselementos son de tipo T. El tama˜
no del vector (es decir, el
n´
umero de elementos de tipo T que contiene) tambi´en se especifica en el momento de su creaci´on; de
otro modo, el vector empieza vac´ıo. Veamos un ejemplo.

//vector de 3 coordenadas enteras
vector v(3);
vector vst(10); //vector de 10 strings
vector w;
//vector de booleanos, vacio
A diferencia de los arraystradicionales del C, los vectores puede cambiar de tama˜
no durante la
ejecuci´
on del programa. M´as 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´
olo que
m´as sencillos, puesto que...

Leer documento completo

Regístrate para leer el documento completo.