Clase de Iteradores

5/20/2018 Clase de Iteradores

1/35

Clase de Iteradores en C++

Algoritmos y estructuras de datos II

Algoritmos y estructuras de datos II Clase de Iteradores en C++
http://find/


2/35

Hasta ahora vimos:

Clases

Manejo de memoria dinamica Templates

http://find/


3/35

template< typename T >

class A r re gl oD {

T * arreglo ;int e s p a c i o ;

int u l t i m o ;

public :

A r r e g l o D ( ) ;

A r r e g l o D ( int t a ma n io ) ;

A r r e g l o D ( const A r re g l oD < T > & o t r o A r re g l o ) ;~ A r r e g l o D ( ) ;

void i n s e r t a r A t r a s ( const T & el em );

int t a m a n i o ( ) const ;

const T & i es im o ( int i ) const ;

T & i es im o ( int i );

};

http://find/


4/35

Iteradores

Que es un iterador?

Como los usamos en C++?

http://find/


5/35

Iteradores

Que es un iterador? Un objeto que permite atravesar un contenedor.


http://find/


6/35

Iteradores

Que es un iterador? Un objeto que permite atravesar un contenedor. En general mantienen una interfaz comun y ocultan los

detalles de la estructura que iteran.


http://find/


7/35

Iteradores



Como los usamos en C++? En C++ los contenedores iterables contienen una clase interna

llamadaiterator y metodos para obtener una instancia queitere a partir de algun punto.

http://find/


8/35

Iteradores



Como los usamos en C++? En C++ los contenedores iterables contienen una clase interna

llamadaiterator y metodos para obtener una instancia queitere a partir de algun punto.

El estilo de C++ es levemente distinto al estilo que usamos en

la materia en los modulos de diseno, en el TP podran utilizarel que les sea mas comodo.

http://find/


9/35

Declarando un iterador a la Algo 2


class A r re gl oD {public :

...

class I t er ad or {

A r re g l oD < T > * a r r e gl o ;

int i n d i c e ;

Iterador( ArregloD * arreglo , int indice);friend I t e r a do r A r re g lo D < T > : : c r e a r I t ( ) ;

public :

bool hayMas() const ;

T & actual ();

void avanzar();

};

I t er a do r c r ea r It ( );

};

http://find/http://goback/


10/35

Definiendo un iterador a la Algo 2


typename ArregloD :: Iterador

A r re g l oD < T > : : c r e a r I t ( ) {

I t er a do r i t (this , 0);

return it ;}


ArregloD ::Iterador::Iterador(

A r re g lo D * a , int i ) :

a r re g lo ( a ) , i n di c e ( i ) { }

http://find/


11/35



bool ArregloD :: Iterador ::hayMas () const {

return i n d i ce < a r re g lo - > t a m a n i o ( ) ;

}


T & A rr eg lo D < T > :: I t er a do r : : a c t ua l ( ) {

return arreglo -> iesimo( indice);

}


void A r re g lo D < T > : : I t e r a d o r : : a v a n z ar ( ) {

indice++;}



12/35

Declarando un iterador a la Algo 2


class A r re gl oD {public :

...

class I t e r a do r _ co n s t {

const A r re g lo D < T > * a r r e gl o ;

int i n d i c e ;

I t e r a d o r _ c o n s t ( const ArregloD * arreglo , int indice);friend I t e r a d o r _ co n s t A r re g lo D < T > : : c r e a r I t ( ) const ;

public :

bool hayMas() const ;

const T & a c tu a l ( );

void avanzar();

};

I t e ra d o r_ c o ns t c r ea r It ( ) const ;

};

http://find/


13/35


template< typename T >typename ArregloD :: Iterador_con st

ArregloD :: crearIt () const {

I t e ra d o r_ c o ns t i t (this , 0);

return it ;

}


A r re g l oD < T > : : I t e r a d o r _ co n s t : : I t e r a d o r _ c on s t (

const A r r eg lo D * a , int i ) :

a r re g lo ( a ) , i n di c e ( i ) { }


const T & A r re g lo D < T > : : I t e r a d o r _ c o n s t : : a c t ua l ( ) {return arreglo -> iesimo( indice);

}

http://find/


14/35

Ventajas:

http://find/


15/35

Ventajas:

Permite manipular eficientemente el contenedor manteniendooculta su representacion interna.

http://find/


16/35

Ventajas:


Podemos usar iteradores como punteros seguros a laestructura interna sin exponerla.


V
http://find/


17/35

Ventajas:


Podemos usar iteradores como punteros seguros a laestructura interna sin exponerla.

Permite escribir algoritmos genericos (asumiendo una interfazcomun).


template < typename T >


18/35


class L is ta {

struct N od o {

T e le m ;

N od o * a n te ri or , * s i g u ie n te ;

Nodo( const T & e , Nodo * ant , Nodo * sig ) :

e le m ( e ) , a n te r io r ( a n t ) , s i gu i e nt e ( s i g ) { }};

N od o * c a be z a ;

public :

class I t er ad or {

L is ta < T > * l i st a ;

N od o * n od o ;

I t er a do r ( L i s ta * l is ta , N od o * n od o ) ;

f r ie n d c la s s L i s t a < T > ;

public :

I t er a do r i n se r ta r ( const T & e );void remover();

};

Lista();

I t er a do r a g re g ar ( const T & t );

};Algoritmos y estructuras de datos II Clase de Iteradores en C++


19/35


L is ta < T >: : L is ta ( ) : c ab ez a ( N UL L ) { }


typename L i s t a < T > : : I t e r a d o r

L i s t a < T > : : a g r e g a r ( const T & e )

{

c ab ez a = new N o do ( e , NU LL , c ab ez a ) ;

if ( c a be za - > s i g u ie n te ! = N U LL )

c a be z a - > s i g u i en t e - > a n t e r i o r = c a b e za ;

typename L i st a < T > :: I t e r a do r i t (this , c ab ez a ) ;

return it ;

}

http://find/


20/35


L is ta < T >: : I t er ad or : : I t er ad or ( L is ta < T >* l , N od o * n ) :

l is ta ( l ) , n od o ( n) { }


typename L i s t a < T > : : I t e r a d o r

L i s t a < T > : : I t e r a d o r : : i n s e r t a r ( const T & e )

{

N od o * n od o = new N od o ( e , n od o , n od o - > s i g ui e nt e ) ;

if ( n od o - > s i gu ie nt e ! = N UL L )

n od o - > s i g ui e nt e - > a n t er i or = n od o ;

n odo - > s i gu ie nt e = n od o ;

I t er a do r i t ( li st a , n od o ) ;

return it ;

}

http://find/


21/35


void L i s t a < T > : : I t e r a d o r : : r e m o v e r ( )

{

if ( n od o == l is ta - > c ab ez a ) {

l is ta - > c a b ez a = n od o - > s i g ui e nt e ;

n od o - > s i g ui e nt e - > a n t er i or = N UL L ;

} else {

n od o - > a n te r io r - > s i g u i e n t e = n od o - > s i g u i e n t e ;if ( n od o - > s i gu ie nt e != N UL L )

n od o - > s i g u i en t e - > a n t e r i o r = n od o - > a n t e r i o r ;

}

delete nodo;

}


Iteradores a la C++
http://find/


22/35

Iteradores a la C++

C++, Java, Python y muchos otros lenguajes hace un uso intensivode iteradores, cada uno tiene su propia manera de hacerlos.En C++:

Los iteradores deben proveer los operadores *, ++, ->, ==y

otros dependiendo del tipo del iterador. Los objetos iterables usualmente tiene una clase interna

iterator (y/o const iterator) de forma similar a como lohicimos hasta ahora.

Los objetos iterables usualmente aceptan los metodosbegin() y end() (y potencialmente rbegin() y rend()).


http://find/


23/35

p yp

class L is ta {

N od o * c a be z a ;

N od o * f in ;

...

public :

class i t er at or {

L is ta < T > * l i st a ;

N od o * n od o ;

bool v a l i d o ;

...

public :

T & operator *();

b oo l o p er a to r ==( const L i st a < T > :: i t e r a to r & o tr o ) const ;

b oo l o p er a to r !=( const L i st a < T > :: i t e r a to r & o tr o ) const ;

i t e r a t o r & operator ++();

iterator operator ++( int );

i t e r a t o r & operator--();iterator operator- -( int );

};

i t er a to r b eg i n ( );

i t er a to r e nd ( ) ;

};Algoritmos y estructuras de datos II Clase de Iteradores en C++

http://find/


24/35

p yp

T & L is ta < T > :: i t er a to r : : operator *() {

return n o d o - > e l e m ;

}


typename L is ta < T > : : i t e r a t o r & L is t a < T > : : i t e r a t o r : : operator + +( ) {v al id o = no do - > s i gu ie n te ! = N UL L ;

if ( v a l i d o )

n od o = no do - > s i gu i en te ;

return * this ;

}


typename L is ta < T > : : i t e r a t o r L is ta < T > : : i t e r a t o r : : operator- -( int ) {

i t er a to r i t (* this );

v al id o = no do - > a n te ri or ! = N UL L ;

if ( v a l i d o )

n od o = no do - > a n te ri or ;

return it ;}


bool L i s t a < T > : : i t e r a t o r : : operator ==(

const L i st a < T > :: i t er a to r & o tr o ) const {

return v a li do == o tr o . va li do && n od o == o tr o . no do ;

}Algoritmos y estructuras de datos II Clase de Iteradores en C++

Algoritmos genericos sobre iteradores en C++
http://find/


25/35

Algoritmos genericos sobre iteradores en C++

El header algorithm tiene definidas un gran numero de funcionescon clases templatizadas asumiendo que cumplen con la interfaz de

los iteradores. Por lo que cualquier clase que que sigacorrectamente el patron automaticamente tiene todos esosalgoritmos a su disposicion sin necesidad de implementarlos.Ejemplos:

find count

replace

reverse

sort random shuffle

min

max


Algoritmo de busqueda de algorithm h
http://find/


26/35

Algoritmo de busqueda de algorithm.h

template< class InputIt erator , class T >

I np u tI te r at or f in d (

I n p ut I t er a t or f ir st ,

I n p ut I t er a t or l as t ,

const T & va lue ){

for (; first != last && * first != value ; + + first );

return first;

}


Tipos de iteradores
http://find/


27/35

Tipos de iteradores

Los iteradores en C++ se separan en distintas categoras, lo quepermite implementar algoritmos genericos de distinta forma para

cada tipo de iterador:

1. Input

2. Output

3. Forward

4. Bidirectional

5. Random access

Para definir a que categora pertenece un iterador se utilizanmiembros de la clase iterator traits. Esto puede hacerse dedistintas formas, pero usualmente incluye herencia oespecializacion de templates por lo que queda fuera de este curso.


Recomendaciones al pasar del diseno a la implementacion
http://find/


28/35


Por cada modulo hacer una clase y un test.


http://find/


29/35



Hacer una clase interna por cada iterador en el modulo (y unaanaloga const si tiene sentido).


http://find/


30/35




Recordar que las clases templatizadas no forman unidades decompilacion (ojo con los cpp que no deben compilarse).


http://find/


31/35





Tener siempre presente el scope de las variables y los objetos.


http://find/


32/35

p p





Identificar que cosas deben alocarse en memoria dinamica yque cosas no.


http://find/


33/35

p p






Hacer delete de todo lo que se hace new, pero de nada mas.


http://find/


34/35

p p






Hacer delete de todo lo que se hace new, pero de nada mas.

LO MAS IMPORTANTE DE TODO ES PROGRAMAR DEFORMA INCREMENTAL. ESCRIBIR UNA FUNCION, SUTEST, COMPILAR Y PROBAR ANTES DE SEGUIR.


Ejercicio
http://find/


35/35

j

Implemente una clase Rosetree (un arbol con una cantidad

arbitraria de hijos) con un iterador preorder a la C++.Permita agregar y eliminar elementos a traves del iteradorretornando un iterador nuevo cuando corresponda.Puede hacer uso de las listas enlazadas y los algoritmos sobreiteradores de la librera standard:

# i n c lu d e < l is t >

# i n c l u d e < a l g o ri t h m >

En la pagina http://www.cplusplus.com/reference/ puedenencontrar la documentacion de estos modulos.

http://find/

Documents

Clase de Iteradores