Laboratório de Programação Orientada a Objetos para Engenharia … · 2014. 11. 12. · Escola Politécnica da Universidade de São Paulo Laboratório de Programação Orientada

Escola Politécnica da Universidade de São Paulo Escola Politécnica da Universidade de São Paulo

Laboratório de Programação

Orientada a Objetos para

Engenharia Elétrica

Aula 11: Exercício Integrador (parte 2)

PCS3111

Agenda

1. Container List

2. Iterators

3. Container Map

4. Exercício Integrador (parte 2)

2

Agenda

1. Container List

2. Iterators

3. Container Map


3

4

STL – Standard Template Library

Based on: [Lafore 2002]. Lafore, R. Object-Oriented Programming in C++. 4th. Edition, 2002. Ed, SAMS.

STL – Standard Template Library

Containers • Sequence containers

Vector

List

Deque -> queue / stack

• Associative containers

Set

Multiset

Map (árvore binária balanceada)

Multimap

Várias especializações a partir destes containers padrão

5


Sequence Containers

6


Sequence Containers

7 Based on: [Lafore 2002]. Lafore, R. Object-Oriented Programming in C++. 4th. Edition, 2002. Ed, SAMS.

Container List Um container List é uma lista duplamente ligada, sendo

que cada elemento tem um ponteiro para o elemento

anterior e para o elemento seguinte

O container guarda o enedereço do início e do final lista,

e assim o acesso é bastante rápido nas duas direções


Container List


Container List


Output: 10 20 30 40

Container List


Output: 10 20 30 40

// list.cpp #include <iostream> #include <list> using namespace std; int main() { list<int> ilist; ilist.push_back(30); ilist.push_back(40); ilist.push_front(20); ilist.push_front(10); while (!ilist.empty()) { cout << ilist.front() << " "; ilist.pop_front(); } cout << endl; }

Adapter-Based Containers


É implementado

como heap.

Agenda

1. Container List

2. Iterators

3. Container Map


13

Iterators

Podem ser considerados como smart pointers

• Podem ser incrementados ou decrementados,

independentemente da forma de armazenamento dos

dados

• O código acima só pode ser usado se os dados

estiverem armazenados em espaços contíguos de

memória

• Por exemplo, não funcionaria numa lista ligada


Iterators

Podem também ser vistos também como

conectores entre containers e algoritmos

• Determinam que algoritmos podem ser usados com

quais containers

• Por exemplo, o algoritmo sort () necessita de acesso

randômico ao container que deseja ordenar, senão

teria de iterar o container para achar cada elemento

antes de movê-lo, e isto seria ineficiente

• Um outro exemplo seria o algortimo reverse (), que

necessita de iterar o container nas duas direções,

senão também seria muito ineficiente

• Iterators são uma solução elegante para conectar

algoritmos a containers


Iterators


Iterators


Iterators


Iterators


Iterators


Iterators


Iterators


Iterators


Output: 2 4 6 8

Iterators (usando C++11)


Output: 2 4 6 8 //listout.cpp #include <iostream> #include <list> #include <algorithm> using namespace std; int main() { list<int> l{2,4,6,8}; //list<int>::iterator p; for (auto p=l.begin(); p!=l.end(); p++) cout << *p << " "; cout << endl; }

Iterators


Iterators


Output: 2 4 6 8 10

Iterators


Iterators


Output: Found 8.

Iterators (usando C++11)


Output: Achei 8.

//iterfind.cpp #include <iostream> #include <list> #include <algorithm> using namespace std; int main() { list<int> l{2,4,6,8,10}; // Procura numero 8 auto p=find(l.begin(), l.end(), 8); if (p==l.end()) cout << "Nao achei 8\n"; else cout << "Achei 8\n"; }

Agenda

1. Container List

2. Iterators

3. Container Map


30

Associative Containers

Nos containers sequenciais, os dados são

armazenados um após o outro

• assim, encontrar um dado requer varrer uma a uma

as posições do container

Nos containers associativos, os itens são

armazenados de um modo mais complexo, mas

que permite que sua recuperação seja feita de

modo mais eficiente

• a recuperação é feita através de uma chave

• a chave pode ser um atributo do container, ou então

ela é o próprio container


Associative Containers


Container Map


Container Map


Container Map


Container Map


//asso_arr.cpp #include <iostream> #include <string> #include <map> using namespace std; int main() { map<string,int> popul{ {"Wyoming",470}, {"Colorado",2890}, {"Nevada",800}, {"Montana",787} }; for (auto p=popul.begin(); p!=popul.end(); p++) cout << "Estado: " << p->first << ". Populacao: " << p->second*1000 << endl; }

Estado: Colorado. Populacao: 2890000 Estado: Montana. Populacao: 787000 Estado: Nevada. Populacao: 800000 Estado: Wyoming. Populacao: 470000

Container Map


//asso_arr.cpp #include <iostream> #include <string> #include <map> using namespace std; int main() { map<string,int> popul; popul["Wyoming"]=470; popul["Colorado"]=2890; popul["Nevada"]=800; popul["Montana"]=787; string st="Colorado"; cout << "Populacao de " << st << " e' " << 1000*popul[st] << endl; st="Nevada"; cout << "Populacao de " << st << " e' " << 1000*popul[st] << endl; }

Populacao de Colorado e' 2890000 Populacao de Nevada e' 800000

Agenda

1. Container List

2. Container Map

3. Iterators


38

Problema

Como ir de espaço a outro em um local?

• Exemplo: da cozinha para a suíte

Uma solução

Como implementar isso?

39

Sala de

Jantar

Cozinha Sala

Quarto1 Quarto2

Suíte

Banheiro

Banheiro

da Suíte

Corredor

Porta

Grafos

Um local pode ser representado como um grafo

• G = (V, E) V é o conjunto de vértices

• Vértices = Espaços

E é o conjunto de arestas

• Arestas = abertura / portas entre os locais

40

Sala de

Jantar

Sala

SuíteBanheiro da

Suíte

Quarto1

Quarto2

Banheiro

Corredor Cozinha

Espaço

Porta

Implementação

Como implementar isso?

• Uma opção: lista de adjacência

Vetor de tamanho |V| em que cada posição é uma lista

ligada de vértices adjacentes

Como implementar isso em C++?

41

1

2

3

4

2

2

1

1

3 /

3

2

3 /

4 /

4 /

Implementação em C++

Usando a STL

Problema

• Como relacionar a posição 0 ao espaço “Banheiro”?

Uma solução

• Usar um mapa: vértice → lista de vértices

42

// Um array de listas de Vértices std::list<Vertice*> listaDeAdjacencia[NUMERO_DE_VERTICES]; // Um vector de listas de Vértices std::vector<std::list<Vertice*>> listaDeAdjacencia;

std::map<Vertice*, std::list<Vertice*>> listaDeAdjacencia;

Traçar rota

Como traçar uma rota entre um Espaço e outro?

• Uma opção: busca em largura

A partir da origem, analisa todos os vértices adjacentes

Exemplo: da Sala ao Banheiro da Suíte

43

Banheiro

da Suíte Suíte

Sala

Cozinha

Sala de

Jantar Banheiro

Quarto 1

Quarto 2

Corredor

Traçar rota

Algoritmo (visto em PCS 3110)

44

Busca-Em-Largura (G, s) 1. for each vértice i ϵ V[G] – {s} 2. i.cor = BRANCO; 3. i.distancia = ∞ 4. i.predecessor = NIL 5. s.cor = CINZA 6. s.distancia = 0 7. s.predecessor = NIL 8. Seja Q uma nova fila 9. Enqueue (Q, s) 10. while !Queue-Empty(Q) 11. i = Dequeue(Q) 12. for each v ϵ G.Adj[i] 13. if v.cor == BRANCO 14. v.cor = CINZA 15. v.distancia = i.distancia + 1 16. v.predecessor = i 17. Enqueue(Q, j) 18. i.cor = PRETO

Busca em largura em C++

Cada vértice é um objeto

As informações não precisam ser guardadas no

vértice

• Use uma estrutura auxiliar

Simplifique o algoritmo!

• Cor e distância podem ser omitidas

Não são necessários

Use as estruturas da STL para facilitar a

implementação!

45

Exercício

Use o software feito na Aula 10

Entrega 0 (feito em casa)

• Altere o Espaço para usar um vector para armazenar

os Equipamentos

Entrega 1: Mapa (veja como testar)

• Crie uma classe Mapa representando o Grafo

46

class Mapa { public: Mapa(); void adicionarEspaco(Espaco* e); void conectar(Espaco* e1, Espaco* e2); void imprimirCaminho(Espaco* origem, Espaco* destino); private: std::vector<Espaco*> espacos; std::map<Espaco*,std::list<Espaco*>> listaDeAdjacencia; };

Exercício

Entrega 2: classe LeitorDoMapa

• Leia o grafo de um arquivo de configuração

• Formato

Exemplo: mapa.txt para a residência em casa.txt

• Caso um Espaço não esteja no Local, jogue um

ErroDeArquivo

• Veja como testar 47

<Número de Espacos> <Nome do Espaco A> <Nome do Espaco B> ... <Número de arestas> <Nome do Espaco A> <Nome do Espaco B> <Nome do Espaco C> <Nome do Espaco A> ...

Exercício

Entrega 2: classe LeitorDoMapa

• Definição

48

class LeitorDoMapa { public: LeitorDoMapa(Local* local); Mapa* carregar(); Mapa* carregar(std::string arquivo); private: Espaco* encontrar(std::string nome); static const std::string ARQUIVO_PADRAO; Local *local; };

Exercício

Entrega 3: menu

• Altere o main para carregar o Mapa usando o

LeitorDeMapa

• Altere a classe Painel para traçar a rota

Dicas

• Exemplo de saída: rota entre “sala” e “quarto 2”

Sala -> Corredor -> Quarto 2

• Use o predecessor para imprimir a rota

• Use as definições das classes nos .h entregues

49

Leia os detalhes das atividades a serem feitas

no enunciado

Documents

Laboratório de Programação Orientada a Objetos para Engenharia … · 2014. 11. 12. · Escola Politécnica da Universidade de São Paulo Laboratório de Programação Orientada