stl

Tema 3

TDAs contenedores bsicos

Objetivos GeneralesEntender el concepto de contenedor Conocer los principales tipos de contenedores bsicos Resolver problemas usando contenedores Entender el concepto de iterador y ser capaz de usarlos.

TDAs Contenedores Bsicos

2

Introduccin a los contenedoresContenedor: Embalaje metlico grande y recuperable, de tipos y dimensiones normalizados internacionalmente y con dispositivos para facilitar su manejo. (Diccionario RAE)TDAs Contenedores Bsicos 3

Introduccin a los contenedoresUn contenedor es una coleccin de objetos dotado de un conjunto de mtodos para gestionarlos (acceder a ellos, eliminarlos, aadir nuevos objetos, etc.). Los contenedores se pueden clasificar segn distintos criterios, pero la fundamental es la forma de organizacin: Lineal, jerrquica, interconexin totalTDAs Contenedores Bsicos 4

Introduccin a los contenedoresTambin se diferencia por las formas de acceder a los componentes: secuencial directa por clave (tambin conocidos como asociativos)


5

Contenedores secuencialesOrganizan los datos en orden lineal:primer elemento, segundo, ...

Adems, quedan identificados por la posicin que ocupan en el contenedor.Vector dinmico (vector) Lista (list) Pila (stack) Cola (queue)TDAs Contenedores Bsicos 6

Contenedores directosGarantizan acceso a cualquier componente en tiempo constante:Vector dinmico (vector)


7

Contenedores asociativosGestionan los datos mediante claves que los identifican (por ejemplo, DNI) y permiten su recuperacin eficiente a partir de ellas.Conjunto (set) Bolsa (multiset) Diccionario (map)


8

El contenedor Pila (stack)Estructura de datos, representada como una sucesin de objetos, que limita la forma en que stos elementos se aaden a ella, as como la manera de abandonarla. Concretamente, una pila slo permite introducir y borrar elementos por un extremo de la secuencia, denominado tope (top) (Secuencias LIFO).TDAs Contenedores Bsicos 9

El contenedor Cola (queue)Contenedor, representado como una sucesin de objetos que limita la forma en que stos se aaden a ella, al igual la manera de abandonarla. As, una cola slo permite introducir objetos por un extremo de la sucesin, final, y la recuperacin por el opuesto, frente. Los elementos se ubican en estricto orden de llegada. (Secuencia FIFO).TDAs Contenedores Bsicos 10

El contenedor Cola con Prioridad (priority_queue)Tipo especial de cola en la que se siguen cumpliendo las restricciones en cuanto a los lugares por donde se realiza la insercin y acceso de los elementos. Pero en este caso los elementos no se disponen segn su orden de llegada, sino de acuerdo a algn tipo de prioridad.


11

El contenedor Conjunto (set)Coleccin de valores que no se repiten y que permite conocer de manera eficiente si un valor est contenido o no en el conjunto.


12

El contenedor Bolsa (multiset)Anlogo a un conjunto, pero permitiendo valores repetidos.


13

El contenedor Diccionario (map)Estructura de almacenamiento que implementa una relacin ``clave-valor''. Permite almacenar valores identificados por claves nicas, y recuperarlos previamente mediante stas.


14

El contenedor Vector Dinmico (vector)Generalizacin de un vector o array que almacena una coleccin de elementos del mismo tipo. Los elementos se acceden de manera directa por medio de un ndice, en el rango de 0 a n-1, siendo n el tamao del vector. Dicho tamao puede aumentarse o decrementarse segn las necesidades de manera dinmica.TDAs Contenedores Bsicos 15

El contenedor Lista (list)Contenedor que almacena sus elementos en forma de sucesin, permitiendo, por tanto, el acceso secuencial a ellos. Cada elemento establece quin es el siguiente de la sucesin.


16

Abstraccin por iteracin: el concepto de iteradorSon generalizaciones de punteros: objetos que sealan a otros objetos (pero no son punteros!!). Se utilizan para iterar (moverse) sobre un rango de objetos de manera independiente del tipo de contenedor donde estn incluidos. Permitirn acceder a elementos del contenedor, modificarlos, borrarlos o insertar nuevos.TDAs Contenedores Bsicos 17

Iteradores en la STLLas clases de la STL poseen cuatro clases de iteradores dependiendo de:La forma de recorrer, o Si permite slo lecturas (L), o insertar otros nuevos o modificar ya existentes (E): iterator: hacia adelante (L, E). const_iterator: hacia adelante (L). reverse_iterator: hacia atrs (L, E). const_reverse_iterator: hacia atrs (L).TDAs Contenedores Bsicos 18

Especificacin iteradores STLEspecificaremos las operaciones de los iteradores comunes a los contenedores set, multiset, map, vector y list. Para especificar los TDAs iterator y const_iterator, utilizaremos genricamente el TDA contenedor.


19

Especificacin iteradores STL (I)Declaracin de iteradores:contenedor::iterator miIterador; contenedor::const_iterator miIteradorConst;

Ejemplo:list::iterator iterListaDouble; map::const_iterator iterDiccConst;


20

Especificacin iteradores STL (II)/** TDA iterator::iterator, *, ++, --, ==, !=, ~iterator El TDA iterator est asociado a un contenedor y seala los elementos de T contenidos en l. Permite recorrer el contenedor con posible modificacin del mismo, por lo que slo se puede usar con contenedores no constantes. Es mutable.TDAs Contenedores Bsicos 21

Especificacin iteradores STL

(III)

TDA const_iterator::const_iterator, *, ++, --, ==, !=, ~const_iterator El TDA const_iterador est asociado a un contenedor y seala los elementos de T contenidos en l. Permite recorrer el contenedor pero no modificarlo por lo que se puede usar tanto con contenedores constantes como no constantes. Es inmutable. */TDAs Contenedores Bsicos 22

Especificacin iteradores STL/** @brief Constructor primitivo. Crea un iterador nulo. */

(IV)

const_iterator();/** @brief Constructor de copia. @param i: iterador que se copia. Crea un iterador copia de i. */

const_iterator(const const_iterator & i);TDAs Contenedores Bsicos 23

Especificacin iteradores STL/**

(V)

@brief Obtener el elemento al que apunta el iterador. @pre El iterador NO est al final del recorrido. Es distinto de end(). @return elemento del contenedor en la posicin apuntado por el iterador. */ T operator*() const;


24

Especificacin iteradores STL/** @brief Operador de incremento. @pre El iterador NO est al final del recorrido. Es distinto de end(). @return Referencia al iterador receptor.

(VI)

Hace que el iterador apunte a la posicin siguiente en el contenedor y lo devuelve. */ const_iterator & operator++();


25

Especificacin iteradores STL/** @brief Operador de decremento. @pre El iterador NO est al principio del recorrido. Es distinto de begin(). @return Referencia al iterador receptor. Hace que el iterador apunte a la posicin anterior en el contenedor y lo devuelve. */ const_iterator & operator--();

(VII)


26

Especificacin iteradores STL/** @brief Comparacin de igualdad. @param i: segundo iterador en la comparacin.

(VIII)

@return true, si el receptor e 'i' tienen el mismo valor. false, en otro caso. */ bool operator==(const const_iterator & i);


27

Especificacin iteradores STL/** @brief Comparacin de desigualdad. @param i: segundo iterador en la comparacin.

(IX)

@return true, si el receptor e 'i' tienen un valor distinto. false, en otro caso. */ bool operator!=(const const_iterator & i);


28

Especificacin iteradores STLEjemplo:template

(X)

void ImprimirContenedor (const T1& contenedor) { T1::const_iterator iter; for (iter = contenedor.begin(); iter != contenedor.end(); iter++) cout

stl

Documents