Universidade Federal de Minas Gerais
Instituto de Ciências Exatas
Departamento de Ciência da Computação

Algoritmos e Estruturas de Dados I

“Containers” e iteradores

Considere o problema de programação onde (i) precisamos guardar os nomes de alunos e sua notas, (ii) precisamos guardar o nome de pessoas e seu cargo na empresa, o numero de um empregado e seus dados pessoais. Estes são problemas recorrentes em Programação e podem ser resolvidos utilizando elementos denominados “containers”. Resolvido o problema de como guardar ou armazenar uma informação temos um outro problema que é como percorrer os elementos que estão armazenados em um “container”. O elemento que exibe comportamentos sobre como percorrer os elementos de um “container” é denominado “iterador”. O ambiente da linguagem C++ provê ao programador vários tipo de “containers” e também vários tipos de iteradores.

O trecho de programa abaixo mostra um exemplo de “container” denominado “vector”. Estamos usando este container para guardar 3 valores inteiros:

#include <vector>

...

vector<int> c;
c.push_back(10);
c.push_back(20);
c.push_back(30);

Observe a especialização do container vector para guardar valores do tipo int. O container vector sobrecarrega o operador indexação (define a função operator[]) e permite um tipo de “iteração” especial via indexação:

for(int i=0; i<c.size(); i++) cout<<c[i]<<endl;

Mas podemos utilizar um iterador “de verdade” através da construção:

for(vector<int>::iterator it=c.begin(); it!=c.end(); ++it) cout<<*it<<endl;

Apesar de parecer “complicado” a vantagem do “iterador” é que ele é geral e pode ser utilizado de forma ortogonal a vários tipos de containers. A interpretação do trecho acima é a seguinte: it é uma variável do tipo iterador de container de ints(vector). O valor inicial de it é dado por uma função de instância de vector que retorna o valor do “primeiro” elemento armazenado. A iteração é feita enquanto o valor de it não é igual ao valor correspondente ao “ultimo” elemento de vector (atente para este último). Os projetistas da biblioteca STL da linguagem C++ definiram que os iteradores deveriam funcionar como ponteiros! observe a expressão ++it e *it, fazem lembrar ponteiros (o conceito neste caso é sobrecarga de opearadores!). Em nosso curso não vamos ver todos os tipo de containers nem todos os tipo de iteradores. O material abaixo mostra de maneira bem grosseira e tosca como é implementado um container denominado list. Nosso objetivo principal é a discussão da estrutura de lista que pode ser criada dinamicamente. Observe o seu uso no trecho de programa abaixo:

#include <list>

...

list<int> lista;
lista.push_back(10);
lista.push_back(25);
lista.push_back(30);
for(list<int>::iterator it=lista.begin(); it!=lista.end(); ++it) cout<<*it<<endl;

Este estilo de “iterador” está presente em várias das classes definidas para C++, observe seu uso com a classe string:
string s("abcde");
for(string::iterator it=s.begin(); it!=s.end(); ++it) cout<<*it<<endl;

O container list implementa uma estrutura de <“nodos” duplamente encadeados> e o significado disso é explicado no material a seguir. Deverá então ficar claro a razão de não ser possível indexar os componentes de uma “lista duplamente encadeada” (de forma similar à indexação dos componentes de um “arranjo/vetor”).

Encadeamento

O programa abaixo ilustra um série de técnicas relacionadas ao encadeamento de elementos que fazem o envelope de informação a ser colecionada. Para simplificar a apresentação colecionamos valores inteiros que devem ser armazenados no campo info da classe Nodo (não vamos usar “programação genérica”). A classe Nodo define os campos ant e prox que devem ser usados para apontar para instâncias, respectivamente, anteriores e posteriores à instância considerada. A classe Lista utiliza um nodo postiço para poder servir como ponto de origem da coleção. Uma lista vazia tem uma instância de Nodo, postico, com campos ant e prox apontando para este mesmo elemento.

#include <cstdlib>
#include <iostream>

using namespace std;
class ErroDeRemocao{};
class Nodo{private: int info;
public:
Nodo(){info=0;}
Nodo(int i){info=i;}
Nodo *ant; Nodo *prox;
void ajustaInfo(int i){info=i;}
int obtemInfo(){return info;}
};
class Lista{private:
Nodo postico;
public:
Lista(){
postico.prox=&postico;
postico.ant=&postico;
}
void adicione(int i){
Nodo *p=new Nodo(i);
p->prox=postico.prox;
p->ant=&postico;
postico.prox->ant=p;
postico.prox=p;
}
void removeUltimoInserido(){
if(postico.prox==&postico){
throw new ErroDeRemocao();
}
Nodo *p=postico.prox;
postico.prox=p->prox;
p->prox->ant=&postico;
delete p;
}
void escreve(){
Nodo *n;
for(n=postico.prox; n!=&postico; n=n->prox){
printf("%d\n", n->obtemInfo());
}
}
};

int main(int argc, char *argv[]){
Lista l1;
l1.adicione(10);
l1.adicione(20);
l1.adicione(30);
l1.escreve();
printf("remove ultimo inserido\n");
l1.removeUltimoInserido();
l1.escreve();
system("PAUSE");
return EXIT_SUCCESS;
}

Na definição da estrutura da classe Lista é utilizada a variável postico (postiço) do tipo Nodo. Podemos sintetizar isto da seguinte forma:

class A{...};
class B{public: A a;…};
…
B b;

Na forma sintética acima A corresponde a Nodo, a corresponde a postico, B corresponde a Lista e b corresponde a l1.

Após a passagem do fluxo de controle pela declaração

Lista l1;

Temos a seguinte estrutura em memória:

As linhas em azul representam a relação “é instância de” entre objetos e classes. As linhas pretas com um circulo cheio na origem e uma seta no final representam endereços.

Após a passagem do fluxo de controle pela sentença
l1.adicione(10);

A estrutura é alterada para:

Observe que esta nova instância da classe Nodo é criada de forma dinâmica usando o operador new. Esta nova instância não tem nome (ao ser criada seu endereço é guardado no ponteiro p). Ao final da execução de l1.adicione(10) o ponteiro p sai de escopo e esta intância de Nodo só pode ser acessada via navegação a partir dos ponteiros da instância de Nodo de nome “postico”.

Exercício

Faça o desenho da estrutura de dados criada a partir da variável l1 depois que forem inseridas as intâncias da classe Nodo que “empacotam” os valores 10, 20 e 30.

Transforme o programa acima para ser “parcialmente” genérico, ou seja reescreva a classe Nodo de forma a poder colecionar qualquer tipo. Não precisa ser “muito” genérico.

Escolha alguns operadores da linguagem C/C++ para serem sobrecarregados de forma “intuitiva”.