Pessoal, boa tarde,
aqui é o professor Simão falando.
Hoje é dia 18 de agosto de 2020,
uma quarta-feira, agora são 15h46 da tarde.
Eu estou aqui para falar hoje para vocês do grupo de slides 15.
onde a gente se aprofunda um tanto mais na chamada STL,
standard tamplate library,
falando de filas, queue,
fila com prioridade, priority queue,
fila com duplo fim, chamada de deque,
pilha, que é stack, conjunto, set,
multiconjunto, que é multiset,
mapa, map e multimapa, multimap,
que seria um belo apanhado dos principais componentes da STL.
Esse grupo de slides é baseado no livro do Deitel,
do pai e filho Deitel, dos Deitel então,
"C++ Como Programar", 3ª Edição Bookman, 2001,
baseado, claro que fiz ajuste aqui e acolá.
Aqui o último slide desse grupo de slides diz o seguinte:
Estudar, diretamente nos códigos disponibilizados de
fila, fila com prioridade,
fila duplo fim, pilha, conjunto e
multiconjunto, mapa e multimapa.
Isso considerado, vamos direto para o código,
já que é isso que o slide está dizendo aqui.
Se a gente for no site e baixar os códigos,
vocês vão encontrar algo mais ou menos assim.
Vai ter código que ali no grupo de slides 15,
por algum motivo, estão selecionados em A, B e C.
A gente vai estudar naquela ordem que apareceu lá no grupo de slides.
Vou abrir aqui um exemplo de fila então, queue,
que se chama Fila.sln, um exemplo,
solution, então tem o Microsoft Visual C++ como de hábito,
mas nada impede que a pessoa utilize outro ambiente de desenvolvimento que melhor agradar,
conforme já discutido anteriormente.
Aqui eu acabei de rodar esse exemplo um pouco antes de gravar a aula, inclusive para testar,
então já está convertido para a versão corrente do Microsoft Visual C++.
Aqui eu tenho o meu projeto,
eu tenho um Fila.cpp que seria equivalente ao main.cpp,
mas em fim, é o cpp que tem a função main,
ou o equivalente ao main, nesse caso o _tmain.
Aqui tem esses argumentos de entrada que a gente não está utilizando.
O que a gente tem aqui?
Tem um include só que é o stdafx.h,
Como a gente está no ambiente Microsoft Visual C++,
a gente sabe que a tem o stdafx.h e stdafx.cpp, isso já foi discutido.
O .cpp está muito mais para a forma,
enquanto o stdafx.h tem os recursos que nos interessam.
Isso vem por default, isso foi eu quem incluiu aqui à luz do livro do Deitel.
Então iostream, não estou colocando o namespace inteiro
para evitar dar acesso a partes do código que não precisam do namespace,
e também para evitar acúmulo de comandos que eu não necessito,
considerando que o compilador não faria essa distinção automaticamente,
então aqui eu estou me garantindo.
Aqui eu incluí meu queue e incluí meu algorithm.
Não estou usando o aqui o using namespace, nem using namespace std,
isso afeta alguma coisa no código lá.
Se você olhar aqui no código principal,
você vai quer, bom, incluindo o stdafx.h, eu venho no main e crio uma fila,
que é um fila de double, de reais longos,
Double é sinônimo de float, mas float tem menos capacidade conforme vocês sabem.
Aqui eu estou criando um queue.
Vejam, como eu não coloquei using namespace std lá na stdafx,
eu sou obrigado a usar aqui o pertencimento, mas isso é coisa que vocês já sabem.
Se eu colocasse lá, eu não precisaria usar aqui, embora pudesse até onde consta.
Aqui eu criei meu objeto fila então,
que é um queue parametrizado com double, então uma fila de doubles.
Bom, antes de explicar aqui, observações.
Aqui eu estou dizendo que estou usando um exemplo do Deitel, isso é importante.
Aqui eu estou fazendo, finalmente, minha fila e estou fazendo push na Fila.
Estou fazendo um push de 3.2,
fazendo do 9.8 e um push do 5.4.
Eu faço um Fila.push e logo em seguida faço um Fila.back no cout,
ele pega e me da o último, as costas da fila, o último que foi inserido.
Eu faço isso para ir imprimindo, passo a passo, a medida que foi inserindo.
Aqui eu coloquei um teste,
enquanto a Fila não estiver vazia,
eu vou imprimir o conteúdo que está na frente na Fila e vou fazendo um pop.
O pop retira o cara da fila.
Hora, é um fila gente, o nome já diz, fila, queue.
Se é fila, é first in, first out,
primeiro que entra é o primeiro que sai,
igual uma fila de supermercado, uma fila bancária,
supostamente, o primeiro que entra é o primeiro que sai,
mas isso vocês já sabem dos estudos de vocês,
de estrutura de dados, ou até intuitivamente pelo conhecimento geral de filas.
Bom, isso posto,
está aqui nosso código.
Vou far um zoom in só para pegar a função inteira.
Aqui, obviamente, estou fazendo um exemplo procedimentado,
porque o c++ permite trabalhar com orientado a objetos
e procedimental, conforme já discutido nessa disciplina, nesse curso.
Vou recompilar aqui,
para deixar crystal clear que, de fato, vai estar rodando o que está compilado.
Está aí a compilação.
Vou executar agora, está aqui a execução.
Inseri os valores 3.2, 9.8, 5.4.
Você veja que 3.2, inserido por primeiro,
depois veio o 9.8, depois o 5.4.
Na retirada acontece isso,
ele tira primeiro o 3.2, depois o 9.8 e o 5.4,
seguindo a política usual de fila.
Às vezes quando estou fazendo o código
com demonstrações, eu costumo dar um grupo de endl aqui,
coisa que não fiz dessa vez, não sei o porquê.
Ele facilita o vislumbre do que aconteceu na execução.
Mais uma vez aqui então, vou recompilar tudo.
Vou executar de volta aqui.
Está ali.
Inseriu e retirou usando o first in, first out.
Esse é componente a mais que a gente tem na STl que é o queue,
STL, standard template library, biblioteca padrão de gabaritos,
o queue é um gabarito, então, que é parametrizado com outro tipo.
Aqui eu tenho uma fila parametrizada com um real longo,
queue parametrizado com double, dito outramente,
Vamos passar para o próximo exemplo de código
que vai ser a fila com prioridade.
Fila com prioridade está aqui.
O que é uma fila com prioridade?
O nome já é mais ou menos intuitivo.
Está aqui o solution, estou abrindo.
Vejam bem, se você está em uma fila de banco,
existe prioridade para pessoa que é gestante,
que está gestante, para pessoa que é idosa,
pessoa que está com criança de colo tem prioridade, então ela passa na frente
em relação à política geral do first in, first out.
Legal.
Aqui está um exemplo bem tranquilo.
A gente vem aqui e cria um fila com prioridades.
O que eu tenho aqui para cima?
O stdafx, que vocês já sabem,
o main, a menção que eu estou adaptando o exemplo do Deitel,
a fila com prioridade, a priority_queue, de reais longos,
coloquei ali o 3.2, 9.8 e o 5.4,
depois eu vou retirar da lista de prioridades o que está no topo.
Legal.
Vamos ver isso aqui executando então.
Vamos dar um rebulid aqui.
Está compilando.
Sucesso, em fim, êxito.
Vamos rodar.
Vejam que interessante.
Retirando de ListaPrioridade,
ele está tirando primeiro o 9.8,
5.4 e 3.2.
Ele tirou o que?
O que está no topo, ele sempre tira o primeiro.
Vejam que ele está usando um top aqui,
mas vejam como foi inserido, foi inserido o 3.2,
o 9.8 e o 5.4.
Isso significa que ele coloca como prioridade o próprio número.
Então através de alguma política,
ele dá prioridade para as coisas, onde vai do maior para o menor.
Na verdade ele faz isso porque ele tem o operador de menor sobrecarregado,
o operador de menor sobrecarregado que no final das contas permite
fazer esse tipo de alternação,
e aqui como é uma fila com prioridade,
ele ordena do maior para o menor e cria essa fila ordenada na prática,
aliás do maior para o menor cria essa fila ordenada, bem entendido.
Então aqui é um exemplo bem simples, mas permite vocês verem
que existe o queue, priority_queue,
pode ser útil, obviamente, em um conjunto de contextos.
Legal, vou fechar aqui.
Aqui eu tenho um, saindo aqui do C e indo para o B, eu tenho o...
o deque, vamos ver esse deque e como ele funciona.
Principal, inclui meu stdafx, como sempre,
nesse projeto chamado deque.sln, solution,
tenho o main que está no deque.cpp.
Aqui eu tenho então, a menção que o exemplo é derivado do Deitel,
eu tenho o include stdafx, standard fixament,
tenho o main,
e aqui eu estou criando, vejam que interessante, um objeto chamado valores,
que é um deque parametrizado com double.
Um deque significa, na verdade, double end queue,
ele é uma fila
que permite navegar, permite a utilização,
não só através de push_front,
mas também através de push_back, permite os dois no final das contas.
E mais que isso na verdade, ele tem uma peculiaridade que é a seguinte,
ele permite, bom, aqui vocês estão vendo que eu criei o objeto,
inseri nele aqui esses 3 valores.
Aqui eu estou usando o que?
Estou usando um for para navegar no deque
que permite utilizar os colchetes.
Então, na prática, esse double ended
está significando aqui para nós
que, além de poder fazer push_front e push_back,
eu posso também utilizar os colchetes.
Essas são as peculiaridades dessa fila double ended, deque.
Aqui além de criar os Valores por valores em valores
e navegar através de colchetes como se fosse um vector da vida,
eu também criei aqui um objeto Saida,
que vai trabalhar baseado no cout e em espaçamentos dos elementos usados no cout,
e esse objeto Saida é do tipo ostream_iterator,
ou seja, um iterator que vai permitir iterar e imprimir na Saida, no cout,
e está parametrizado com double.
A gente já tinha visto em aulas passadas o que é um ostream_iterator,
é um cara que permite automatismo,
tanto de vez de iterar e jogar na saída
um dado conjunto visado.
Então se você olhar aqui, por exemplo,
depois de inserir em Valores, depois de navegar em Valores via colchetes,
eu estou aqui fazendo um pop_front.
O que ele está fazendo? Ele está apagando da frente da fila.
E aí ele está fazendo o que?
Aqui ele está usando o algoritmo copy,
que é o algoritmo que está no algorithm,
se você for aqui, com certeza eu coloquei no stdafx o algorithm,
vamos ver lá.
Está ali, include deque, include também o algorihtm.
É no algorithm que tem o copy.
O copy está permitindo eu fazer o que?
Usar esse objeto Saida, esse objeto Saida aqui criado,
o copy vai pegar aqui o objeto Saida e vai fazer esse objeto Saida navegar
e imprimir tudo que existe do início de Valores até o final de Valores.
Então vai fazer o automatismo.
Eu posso navegar assim,
posso navegar por iterador normal,
começa em begin, enquanto ele não estiver em end, vai fazendo o iterador++,
ou eu posso usar esse iterador mais automatizado que existe na STL.
Como eu trabalho com colchetes,
eu posso ir lá em uma posição dada em Valores e alterar aqui,
por exemplo, na posição 1 eu estou alterando para 5.4
e depois estou imprimindo aqui uma lista que vai ter a posição 1
alterado o valor que tinha para 5.4.
Bom.
A gente pode vir aqui e fazer a compilação nossa de cada dia.
Recompilar tudo.
E agora nós vamos, em fim, executar a coisa.
Está ali.
Eu inseri os valores, naveguei via colchetes,
ele insere, supostamente ele deveria inserir do jeito que eu coloquei aqui,
vamos ver o porquê não.
Inserir 3.5, depois 2.2 e 1.1.
Será que essa versão que ele executou é a versão que eu compilei?
Já vou descobrir.
Vamos fechar aqui.
Bom, continuando então.
Vamos dar um limpada na solução.
Recompilar e reexecutar.
Acho que já sei o que aconteceu.
Vou executar, em todo caso, e já vou explicar.
Óbvio né, óbvio que está diferente do código.
Aqui eu estou fazendo um push_front, push_front e depois um push_back,
então natural que ele tenha esse ordenamento aqui, obviamente.
Isso é procedente, então está certo.
Aqui eu estou mostrando esse conteúdo que eu naveguei via vetores,
depois eu fiz um pop_front, ele eliminou o primeiro,
então ele vai imprimir isso aqui,
depois na posição 1 eu substitui por 5.4.
De fato a posição 1, que seria a posição 0,
então na posição 1, substitui por 5.4.
Então está aqui a nossa fila com duplo final.
Peculiaridades desse exemplo é que também usei esse algoritmo aqui,
aliás esse objeto que pode ser animado pelo algoritmo copy,
que permite você navegar um dado conjunto,
no sentido de iterar e imprimir no fluxo de saída no caso do cout,
com os espaçamentos dos caras impressos.
Bom.
Vamos dar uma olhadinha também, pessoal,
Pilha.
Pilha é outro conhecido de vocês,
de estrutura de dados ou até intuitivo, uma pilha de pratos, uma pilha de livros,
uma pilha, sei lá eu, de moedas.
Se você quer fazer coisas de maneira organizada, você vai empilhando,
e para desempilhar você vai ter que tirar a última que empilhou
para evitar uma catástrofe ali, entre aspas.
Então na prática,
ele vai usar um last in, first out,
um LIFO, last in é último que entrou,
first out é primeiro a sair.
Vamos abrir nosso projeto de pilha.
Provavelmente vai se chamar Pilha.sln, solution.
Estamos abrindo a coisa.
Está pensando um pouquinho.
Bom, abriu aqui, folks.
Tenho aqui o include stdafx.h,
onde incluo as coisas que são pertinentes,
não tem muito mistério.
Está ali o stack,
aqui incluí o vector e o list, não sei bem o porquê,
mas talvez não fosse necessário.
Vamos aqui... Ah, sim, vai ser necessário por um motivo, já lembrei o porquê,
inclusive por isso que está ali.
Está aqui o nosso programa.
Testando a classe stack da biblioteca padrão.
Exemplo vem lá do Deitel, conforme já informado.
Aqui vejam que interessante,
eu tenho o _tmain, antes do tmain eu tenho a definição de uma função,
função essa que só aparece depois do main,
como a função só aparece depois da main e eu uso ela na main,
eu sou obrigado a colocar a assinatura antes, isso já foi discutido.
Aqui a função ela trabalha com parâmetro que trabalha por referência, referência escondida,
e, ademais, não é uma função qualquer,
é uma função template.
A gente já viu que é possível ter uma função template.
Está aqui a função, então, que trabalha com template da STL.
Ele vai receber um dado parâmetro da chamada da função,
e esse parâmetro
de tipo, do tipo T
vai permitir instruir com o parâmetro
da função em si, que é o pilha ali no caso, e vai trabalhar.
Se você olha na implementação da função lá para baixo,
você vai ver que ele faz o que?
Ele vem aqui, recebe uma pilha de dado tipo,
testa se a pilha não está vazia,
e mostra o conteúdo do topo da pilha
e faz um pilha.pop(),
ou seja, ele vai retirar as coisas que estão no topo da pilha.
Professor, precisava dessa função?
Até podia fazer sem a função, podia fazer
esse código direto dentro da função main,
aliás, esse código dentro da função main,
mas aqui foi apenas um recurso
para lembrar que é possível criar funções com template.
Eu já tinha mostrado isso par vocês em slides
quando a gente estava trabalhando com vector e list,
e resolvi mostrar isso aqui também como exemplo de código, direto no código, só como reforço.
Legal.
Aqui está a função main.
Aqui eu criei uma stack baseada em inteiro,
quando você faz isso, essa stack, na verdade,
ela vai trabalhar baseado, em alguma medida, em um deque, é isso que está acontecendo,
pilha baseada em deque.
Através lá das heranças,
quem elaborou essa STL
usou essa ideia de criar pilhas inspiradas em componentes anteriores.
Aqui nesse caso o default vai ser trabalhar com o deque,
mas claro que daí a política muda,
aqui não vai ser FIFO, vai ser LIFO, last in, first out.
Bom, aqui eu estou colocando na pilha,
um push, estou colocando um valor,
aqui um for que varia de 0 a 10,
e eu vou empilhar os números.
Então 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
o 10 não entra obviamente, de 0 a 9 na prática,
vou empilhar esses números.
Mas vejam que eu não tenho só pilha baseada em deque,
eu tenho também uma pilha baseada em vector
cujo a essência é a lá vector,
outra pilha aqui cuja essência é a lá list,
como vocês estão vendo aqui a segunda parametragem.
Professor, então é possível um template ter mais que um parâmetro?
É, vejam que está acontecendo aqui.
Aqui ele está recebendo uma pilha de inteiro baseado em vector,
uma pilha de inteiro baseado em list,
mas ele também permite trabalhar
com uma outra sobrecarga do template com um parâmetro só,
depende do que você, então, vai utilizar aqui na chamada.
Legal.
Aqui eu empilhei, em todas as pilhas, os números.
São 3 pilhas,
cada qual com uma essência diferente,
mas que vão reproduzir a mesma funcionalidade,
e depois estou chamando lá a função para desempilhar,
como é uma função template ela se adapta a cada um.
Aqui a vantagem da função
é que em vez de colocar o código, eu não preciso repetir aquele código 3 vezes, de desempilhamento,
apesar que também não seria nada crítico,
ele vai desempilhar.
Bom, vamos ver essa execução rodando, então.
Vamos fazer nossa compilação para garantir o óbvio.
Está compilando.
Tem alguns warnings ali.
Aqui vocês têm a execução.
Está lá, desempilhou a partir do último empilhado que foi o 9,
depois o penúltimo que foi o 8, depois o antepenúltimo que foi o 7, e assim por diante.
Bom, então vocês estão vendo que vocês podem trabalhar com filas,
vocês sabem que, com filas e pilhas,
vocês sabem que as coisas mais elementares em estrutura de dados
é lista, fila e pilha.
Vocês sabem que a gente tem a lista que é o list,
agora vocês viram que a gente tem as filas,
tanto que tem o queue, tem o priority queue,
e tem o double ended, deque,
e vocês também podem trabalhar com stack, que está aqui.
As stacks, inclusive, podem ter orientações internas distintas,
mas reproduzem o mesmo resultado.