1. Educación

STL: Standard
Template Library
Estructuras de Datos
Andrea Rueda
Pontificia Universidad Javeriana
Departamento de Ingeniería de Sistemas
Ocho reinas
●
Elementos clave de la solución:
–
Ubicar las reinas
Permutación de 0 a 7, fuerza bruta (todas)
–
Verificar conflictos
Misma fila, misma columna, mismas diagonales
–
Imprimir solución encontrada
Siguiendo el formato exigido ('Q' y '*')
Ejemplos: página web del curso
Consideraciones de diseño
●
Programas = Algoritmos + Datos
(ecuación de Wirth)
https://web.archive.org/web/20130207170133/http://w
ww.inf.ethz.ch/personal/wirth/books/AlgorithmE0/
●
Diseño de TADs:
–
Identificar el comportamiento del objeto en el mundo
real (interfaz/verbos)
–
Identificar el conjunto mínimo de datos para
representar esa información (estado/sustantivos)
–
TAD = Interfaz + Estado
Consideraciones de diseño
●
Diseño de TADs:
TAD nombre
Conjunto mínimo de datos:
nombre valor (variable), tipo de dato, descripción
...
Comportamiento (operaciones) del objeto:
nombre operación (argumentos), descripción
funcional
...
Atención!
●
Recordatorio:
El diseño descrito anteriormente será exigido
en todas las actividades del curso (talleres,
parciales, proyecto, quices) de aquí en
adelante, durante todo el semestre
Quiz
●
●
¿Qué significa la sigla STL?
¿Cuáles son los cuatro componentes básicos
de la STL?
a) Ciclos, condicionales, estructuras y funciones
b) Contenedores, algoritmos, funcionales e iteradores
c) Puntos, aristas, caras y volúmenes
d) Listas, pilas, colas y montículos (heap)
Programación genérica
Programación genérica
a = b + c;
En C++, ¿qué problemas tiene la línea
anterior?
Programación genérica
int b = 5;
int c = 6;
int a = b + c;
float b = 5.67;
float c = 6.923;
float a = b + c;
Programación genérica
int suma( int a, int b )
{ return( a + b ); }
float suma( float a, float b )
{ return( a + b ); }
Programación genérica
●
Generalización → adaptabilidad, flexibilidad
template< class identificador >
declaracion_funcion;
template< typename identificador >
declaracion_funcion;
Programación genérica
●
Plantilla con un solo tipo de dato
template< class T >
T suma( const T& a, const T& b )
{ return( a + b ); }
int a = suma<int>(5, 7);
double b = suma<double>(6.4, 1.7);
Programación genérica
●
Plantilla con dos tipos diferentes de dato
template< class T, class U >
T suma( const T& a, const U& b )
{ return( a + b ); }
int i, j=25;
long l=4567;
i = suma<int,long> (j,l);
Programación genérica
●
Plantilla para clases
template< class T >
class vec_par {
T valores [2];
public:
vec_par (T uno, T dos)
{ valores[0] = uno;
valores[1] = dos; }
T minimo ();
};
Programación genérica
●
Plantilla para clases
template< class T >
T vec_par<T>::minimo () {
T resultado;
if (valores[0]<valores[1])
resultado = valores[0];
else
resultado = valores[1];
return resultado;
}
Programación genérica
●
Plantilla para clases
vec_par<int> obj_i (115,36);
int res;
res = obj_i.minimo();
vec_par<float> obj_f (32.56,76.98);
float res2;
res2 = obj_f.minimo();
Programación genérica
Organización de las plantillas
●
Encabezado (.h)
●
Incluir archivo de código (.hxx)
●
ESTOS DOS ARCHIVOS NO SE COMPILAN.
–
Se usan en un archivo compilable (.cxx, .cpp, .c++)
donde se INSTANCIAN las clases genéricas.
STL
Standard Template Library
STL (Standard Template Library)
●
●
●
¡Librería con “muchas cosas” genéricas!
Provee un conjunto de clases comunes, usables
con cualquier tipo de dato y con operaciones
elementales
Tres componentes:
●
Contenedores (containers)
●
Algoritmos (algorithms)
●
Iteradores (iterators)
www.bogotobogo.com/cplu
splus/stl_vector_list.php
http://www.sgi.com/tech/stl
STL (Standard Template Library)
Componentes:
●
●
●
Contenedores: clases predefinidas para
almacenamiento de datos
Algoritmos: operaciones básicas como
búsqueda y ordenamiento
Iteradores: permiten recorrer los datos en los
contenedores (similar a apuntadores)
http://www.sgi.com/tech/stl
STL (Standard Template Library)
¿Cómo se conectan estos conceptos?
www.bogotobogo.com/cplusplus/stl3_iterators.php
http://www.sgi.com/tech/stl
Contenedores STL
●
Contenedores secuenciales estándar
●
De acceso aleatorio
- vector: Arreglos dinámicos
(std::vector ↔ #include <vector>)
- deque: Cola de doble cabeza, inserción/eliminación
en cabeza y cola
(std::deque ↔ #include <deque>)
●
De acceso iterativo
- list: Doblemente encadenada
(std::list ↔ #include <list>)
Contenedores STL
●
Contenedores como interfaz (container adaptors)
- queue: cola, primero que entra, primero que sale
(std::queue ↔ #include <queue>)
- stack: pila, último que entra, primero que sale
(std::stack ↔ #include <stack>)
- priority_queue: cola de prioridad
(std::priority_queue ↔ #include <queue>)
Contenedores STL
●
Contenedores asociativos
- set: conjunto matemático, operaciones de unión,
intersección, diferencia; requiere función de
comparación
(std::set ↔ #include <set>)
- map: arreglo asociativo, provee mapeo de un dato
(clave) a otro (valor); requiere función de
comparación para la clave
(std::map ↔ #include <map>)
Iteradores STL
●
Objeto que puede iterar entre un rango de
elementos predefinido a través de operadores
–
Input iterator : extrae datos, movimiento hacia adelante
–
Output iterator : almacena datos, movimiento hacia
adelante
–
Forward iterator : almacena y extrae datos,
movimiento hacia adelante
–
Bidirectional iterator : almacena y extrae datos,
movimiento hacia adelante y hacia atrás
–
Random-access iterator : almacena y extrae datos,
acceso a elementos en cualquier orden
Iteradores STL
●
Operaciones:
- Operador *: (dereferenciación) funciona como
un apuntador, retorna el contenido del iterador
- Operadores ++ y --: mueve el iterador a la
siguiente posición o a la anterior posición
- Operadores == y !=: comparación de
iteradores, si apuntan o no al mismo elemento
- Operador =: asigna una nueva posición al
iterador (usualmente principio o fin del
contenedor)
Iteradores STL
Operaciones
*
* =
++
--
== , !=
=
Input
iterator
✔
✘
✔
✘
✔
✔
Output
iterator
✘
✔
✔
✘
✘
✔
Forward
iterator
✔
✔
✔
✘
✔
✔
Bidirectional
iterator
✔
✔
✔
✔
✔
✔
Randomaccess
iterator *
✔
✔
✔
✔
✔
✔
* además soporta operaciones de acceso aleatorio: +n, -n, <, >, <=, >=, +=, -=, []
Contenedores e Iteradores STL
●
Cada contenedor incluye funciones básicas para
usar con el operador =
–
begin(): iterador que representa el inicio de los
elementos
–
end(): iterador que representa el elemento
después del final
–
cbegin(): iterador constante (sólo lectura) que
representa el inicio de los elementos
–
cend(): iterador constante (sólo lectura) que
representa el elemento después del final
Contenedores e Iteradores STL
●
Cada contenedor incluye funciones básicas para
usar con el operador =
–
rbegin(): representa el inicio en la secuencia
inversa
–
rend(): representa el elemento después del final
en la secuencia inversa
–
crbegin(): iterador constante, representa el inicio
en la secuencia inversa
–
crend(): iterador constante, representa el
elemento después del final en la secuencia inversa
Contenedores e Iteradores STL
●
Cada contenedor tiene varios tipos de
iteradores:
–
–
–
–
container ::iterator
iterador de lectura/escritura (entrada/salida)
container ::const_iterator
iterador de sólo lectura (entrada)
container ::reverse_iterator
iterador en secuencia inversa de lectura/escritura
(entrada/salida)
container ::const_reverse_iterator
iterador en secuencia inversa de sólo lectura
(entrada)
Iteradores inválidos
●
Después de algunas operaciones en los
contenedores, los iteradores pueden resultar
inválidos:
* Cambiar el tamaño o la capacidad
* Algunas inserciones y/o eliminaciones
–
Iteradores singulares: sin asociar a un contenedor
–
Iteradores después del final
–
Iteradores fuera de rango
–
Iterador colgante: apunta a un elemento no
existente, en otra ubicación o no accesible
–
Iteradores inconsistentes
Tarea:
Libros en una biblioteca
separados por temas
Composición
●
Ejemplo: libros en una biblioteca separados por
tema
Novela
Académico
Crónica
Ana Karenina
Álgebra
La bruja
La María
Cálculo
Ivanhoe
Geometría
Infantil
Composición
●
Ejemplo: libros en una biblioteca separados por
tema
class Book {
public:
Book();
std::string GetName();
unsigned long GetNumberOfCopies();
void SetName(std::string name);
void AddOneCopy();
void EraseOneCopy();
protected:
std::string m_Name;
unsigned long m_Count;
};
Composición
●
Ejemplo: animales de un zoológico separados
por género
class Genre {
public:
Genre();
std::string GetName();
void SetName(std::string name);
void AddOneBook(std::string book);
unsigned long CountBooks();
bool EraseOneBook(std::string book);
protected:
std::string m_Name;
std::list<Book> m_Books;
};
Composición
●
Ejemplo: animales de un zoológico separados
por género
class Library {
public:
Library();
void NewBook( ... );
long Count() const;
void RemoveBook( ... );
protected:
std::list<Genre> m_Genres;
};
Composición
●
Multilistas
typedef std::list<T> TSubList;
typedef std::list<TSubList> TList;
TList lst;
TList::iterator lIt = lst.begin();
for ( ; lIt!=lst.end(); lIt++) {
TSubList::iterator slIt = lIt->begin( );
for ( ; slIt!=lIt->end(); slIt++)
std::cout << *slIt << std::endl;
}
Ejercicio
●
●
Completar tarea biblioteca:
–
Completar diseño de TADs (20%)
–
Implementación Libro (.h y .hxx) (20%)
–
Implementación Género (.h y .hxx) (22%)
–
Implementación Biblioteca (.h y .hxx) (24%)
–
Programa con procedimiento principal (.cxx) (14%)
En Uvirtual antes de terminar la clase (en un
archivo comprimido):
–
Documento PDF con diseño
–
Código fuente (.h, .hxx, .cxx)
Referencias
●
www.sgi.com/tech/stl
●
www.cplusplus.com
●
●
●
●
http://www.learncpp.com/cpp-programming/16-3stl-iterators-overview/
http://www.cs.northwestern.edu/~riesbeck/progra
mming/c++/stl-iterators.html
http://www.cprogramming.com/tutorial/stl/iterators
.html
http://www.angelikalanger.com/Conferences/Slid
es/CppInvalidIterators-DevConnections-2002.pdf