Introducción a STL

Biblioteca estándar de templates de C++
Standard Template Library (STL)







Tipos de Contenedores en STL
Iteradores en STL
STL: contenedores list, set y map
Algoritmos genéricos
Invalidación de iteradores
Iteradores y clases parametrizadas

Laboratorio
Análisis y Diseño de Algoritmos 2

STL de C++







Los componentes que provee son:
− clases decontenedores;
− iteradores para cada tipo de contenedor;
− algoritmos para manipular los datos guardados en los
contenedores.
STL hace un uso intensivo del mecanismo de parametrización.
La documentación de la STL describe cada conjunto de
requerimientos que cumplen los tipos de datos que provee a
través de lo que denomina “conceptos”.
De esta forma, partiendo de conceptos muy generales queabarcan a todos los contenedores (o todos los iteradores), los
mismos se van refinando en forma sucesiva hasta llegar a
conceptos muy especializados y que especifican a un solo tipo
de datos.
Por ejemplo: contenedor --> secuencia --> vector
Laboratorio
Análisis y Diseño de Algoritmos 2

STL: Tipos de contenedores


De todos los conceptos, los más importantes son aquellos que
dividen a loscontenedores en dos clases principales:
−

−

Secuenciales: los elementos se encuentran en un orden lineal
estricto, pudiéndose insertar y eliminar elementos de posiciones
específicas: vector, deque, list, slist
Asociativos: permiten manipular a los elementos a través de una
clave (la cual una vez almacenada no puede modificarse). La
característica más importante es que las operacionesde acceso
utilizando las claves son eficientes (O(log(n))). Los mismos a su
vez se dividen en:
 Asociativos simples: La clave es el mismo elemento que se
almacena. Esto lleva a que los elementos guardados no
puedan modificarse: set, multiset, (hash_set,
hash_multiset)
 Asociativos por pares: La clave y el elemento guardado son
objetos distintos, por lo que se pueden modificar loselementos: map, multimap, (hash_map, hash_multimap)
Laboratorio
Análisis y Diseño de Algoritmos 2

STL: Secuencias
Inserción al principio

Elem1

Inserción en una posición
intermedia

Elem2

Elem3 Elem3

Elem9

Inserción al final

Elem6

Elem5

No soporta la función de búsqueda. Si queremos consultar un elemento determinado,
debemos iterar sobre toda la colección de elementos.




Las inserciones y eliminaciones en una list tienen costo O(1).
La inserción y eliminación en el final para un vector tiene costo
O(1), el resto O(n).
La búsqueda de un elemento tiene costo O(n) (la debemos
implementar nosotros).
Laboratorio
Análisis y Diseño de Algoritmos 2

STL: Asociaciones simples
Inserción (ordenada) respecto a una comparación definida sobre el elementoKey3
Key2

Key4
Key1

Key6

Key5
Key7

Key8

Se brinda soporte para accesos eficientes a partir del valor del elemento.






Las inserciones y eliminaciones en un (multi)set tienen costo
O(log(n)).
La búsqueda de un elemento tiene costo O(log(n)) (siempre
que utilicemos el mismo criterio de comparación que se usó
para la inserción).
No se permite la modificación delos elementos guardados.
Laboratorio
Análisis y Diseño de Algoritmos 2

STL: Asociaciones por pares
Inserción (ordenada) del par [Clave,Elemento], respecto a una comparación definida
sobre la clave

Key1 Elem1

Key3 Elem3

Key2 Elem3

Key5 Elem2

Key9 Elem9

Key7 Elem5

Key6 Elem6

Se brinda soporte para accesos eficientes a los elementos a partir del valor de la clave




Las inserciones y eliminaciones en un (multi)map tienen costo
O(log(n)).
La búsqueda de un elemento tiene costo O(log(n)) (siempre
que utilicemos el mismo criterio de comparación que se usó
para la inserción).
Se permite la modificación de los elementos guardados (pero
Laboratorio
no la clave).
Análisis y Diseño de Algoritmos 2

STL – Iteradores: Interfaz general (1)
...