Além dessas estruturas de dados mais elementares,
na STL você vai ter algumas coisas mais extraordinárias,
como, por exemplo, a estrutura conjunto.
Está aqui, vamos abrir o Set.sln, set é conjunto em inglês,
então eu tenho um Set.sln aqui.
Posso chamar de Conjunto.sln também, obviamente,
mas, por algum motivo, eu acabei colocando set.
Ok, folks.
Então nós temos lá nosso stdafx, vamos dar uma espiada nele.
Está aí, ele está usando o set e o algorithm,
o iostream e mais o que já vem por default ali.
Está aqui o principal, baseado em Deitel, include stdafx,
O contêiner associativo "set", ou conjunto,
é usado para armazenagem
e recuperação rápida com chaves únicas, elementos únicos.
A implementação de um "set" é identica aquela de um "multiset",
de multiconjunto que a gente vai ver daqui a pouco,
exceto pelo fato de que um "set", a duplicata é ignorada.
Como este é o comportamento matemático objetivado, desejado, em um conjunto,
não se identifica esse comportamento como um erro comum de programação.
O que significa essas duas frases aqui?
Significa que eu não posso repetir elementos no conjunto.
Por quê? Porque na teoria de conjuntos da matemática, elementos não se repetem.
O conjunto de números inteiros
só vai ter um número três, não vai ter "n" números três.
Ainda o set suporta iteradores bidirecionais,
ou seja, posso usar iterator com ele,
mas não de acesso aleatório.
O que isso significa mesmo?
Significa que eu não posso usar colchetes
e nem usar o begin mais um dado número.
Então eu posso usar os colchetes tradicionais, tal qual eu uso em list, por exemplo.
Aqui tem um typedef, ou seja, estou definindo um novo tipo
que vai ser chamar Conjunto_Reais e vai representar isso aqui.
Conjunto ele trabalha, vai ser um conjunto de reias longos,
que vai ser ordenado por operador de
menor parametrizado com double.
É possível, então, designar para o set que a ordenação dele,
a chave dele, vai trabalhar com um operador de menor
e isso gera um resultado.
Aqui eu estou criando, por exemplo, o ConjReais1 do tipo Conjunto_Reais.
Se eu não tivesse criado o tipo, feito um typedef,
eu seria obrigado a vir aqui
e fazer isso aqui.
Como eu criei o tipo,
fica mais pedagógico, então criei o ConjReais1 do tipo Conjunto_Reais.
Nesse ConjReais1, já vou colocar algo nele
que é o que está no espaço de memória "a" até "a + TAMANHO".
O que que é isso?
É o conteúdo que vai estar nesse vetor de double que criei.
A gente sabe que "a" é ponteiro para o início do vetor, esse já é conhecido,
vou de "a" até "a + TAMANHO", estou indo até o final do vetor,
insiro o conteúdo desse vetor nesse ConjReais1.
Aqui eu criei um saída
que é um ostream_iterator, conhecido já de vocês,
ele vai dar um cout e um espaçamento dos elementos imprimidos.
Aqui, justamente, estou fazendo o que?
Eu estou imprimindo aqui, via copy, o que eu coloquei no ConjReais1.
Vamos tentar executar isso aqui.
Está compilando.
Vamos ver aquela primeira parte da execução.
Está aqui, o que interessa é isso,
de fato ele tem ali o conjunto,
e veja que ele ordena do menor para o maior, nesse caso,
porque eu parametrizei com um less lá,
e o less faz parte da std, ou seja,
ele é um elemento já pronto
que permite parametrizar o segundo parâmetro do template set,
e o less, ele mesmo, também é um template.
Eu tenho, então, um template parametrizando outro template.
Isso é possível? É, tanto é que está aí,
muito embora seja um uso mais avançado de c++, bem entendido.
Então ele mostrou a coisa ordenada do menor para o maior, à luz do less aqui.
E aqui ele imprime com o copy.
Bom, aqui eu estou criando outro cara,
um objeto chamado par que é do tipo pair.
pair também é um duplo...
gabarito, duplo template, porque tem duas parametrizações de tipo.
Ele é um iterador no primeiro elemento
e um booleano no segundo elemento.
Vamos ver o que significa.
Aqui no ConjReais1, eu estou tentando fazer um insert,
eu posso inserir nos elementos da STL de várias maneiras, vocês já viram isso,
através de construtora, através de insert como no exemplo dado aqui.
Eu inseri o valor 13.8,
e aí eu faço o par apontar para esse elemento,
o par, como ele também é um iterator,
ele consegue, sendo um iterator, um ponteiro de alto nível por assim dizer,
ele consegue apontar para o elemento criado de maneira de alto nível.
Aí eu faço aqui um cout, estou fazendo par.first,
eu estou dizendo
o par.first me traz o que? Me traz o cara apontado,
ou seja, ele trás a parte
iterador que é capaz de apontar para alguém,
no caso para o 13.8, por assim dizer.
e o second é um booleano,
ele diz se esse cara foi inserido ou não no conjunto.
Se ele foi inserido, é porque não existia já um 13.8,
então ele vem aqui e diz: "Olhe, inseri o 13.8, você vai poder apontar para ele,
e sim, deu boa."
Agora se o 13.8 já estivesse inserido,
já existisse um 13.8 lá dentro,
ele dizia: "Opa, já existe um 13.8, não inseri,
está aqui o 13.8 que já existe,
e é falso que eu inseri um novo", então é isso que acontece.
Tanto é que aqui, por exemplo, eu já tenho o 9.5,
depois lá, se eu tentar fazer um insert do 9.5,
vai acontecer o que eu falei, ele vai apontar para o 9.5 que já existe,
não vai inserir o novo 9.5,
e vai dar um false aqui.
Eu testo aqui com o operador ternário, que vocês já conhecem,
9.5 não foi inserido, de novo no caso,
e aqui estou usando o copy para imprimir.
Então isso aqui é o conjunto, conjunto que respeita a teoria de conjuntos
no caso da STL.
Como vocês podem imaginar,
aqui eu estou só dando uma degustação, em alguma medida, dos componentes,
por quê?
Porque a STL é gigante.
a gente podia passar o ano inteiro falando da STL.
Você tem que, no caso,
pegar o livro do Deitel e ler o capítulo inteiro da STL
para ter um belo apanhado de tudo que acontece nesse âmbito,
ou ir utilizando.
Por exemplo, quando o pessoal está a disciplina de técnicas de programação, o pessoal faz um jogo,
ele vai aplicando os componentes lá, por exemplo,
e vai utilizando, consultando o livro, criando funções, fazendo isso e fazendo aquilo,
para explorar, na prática, melhor essa componentização toda da STL.
Sempre, claro, consultando livros, consultando professor, consultando monitor, consultando todos os meios, em fim.
Vamos executar isso aqui, dar mais uma compilada.
Ok, não inseri nenhum erro nas minhas alterações ali.
E está aí a execução.
13.8 foi inserido porque ele não existia.
9.5 não foi inserido porque ele já existia.
E é isso.
Bom.
Além de eu ter conjuntos,
eu tenho os multiconjuntos.
O multiconjunto é similar a um conjunto
salvo pelo fato de ele ser, justamente, multi no sentido de ele poder repetir o mesmo elemento.
Um conjunto de inteiros só vai permitir um número três no conjunto,
um multiconjunto de números inteiros permite várias instâncias,
vários três dentro do multiconjunto.
Está aqui nosso Multiset.cpp dentro do nosso Multiset.sln.
Vou dar uma olhadinha no que eu estou usando no stdafx.
iostream, set e algorithm.
Aqui então, exemplo baseado no Deitel,
stdafx.h que a gente viu lá, está inserindo,
O contêiner associativo "multiset"
oferece armazenagem e recuperação rápida de chaves.
Um "multiset" permite chaves duplicadas,
elementos duplicados, por assim dizer.
A ordenação dos elementos é determinada por um "objeto função de comparação",
como acontece lá no próprio conjunto que a gente tinha o less.
Por exemplo, em um "multiset" de inteiros,
os elementos podem ser ordenados
em ordem crescente ordenando-se
as chaves com o objeto função de comparação "less".
O tipo de dado das chaves em todos os contêineres associativos deve suportar adequadamente a comparação,
com base no objeto de comparação especificado,
as chaves ordenadas com "less" devem suportar a comparação com "operator<",
ou seja, se eu usar o "less", usar o menor,
o operador de menor deve estar sobrecarregado nos objetos que estão parametrizando a coisa toda,
int tem o operador de menor sobrecarregado, então funciona.
Em tempo, se as chaves usadas
em contêineres associativos são de tipos definidos pelo programador,
estes tipos devem prover os operadores de comparação apropriado.
Então se eu quero usar um less
no multiconjunto de um tipo que eu estou criando,
eu tenho usar lá, ir lá nesse tipo, nessa classe, e sobrecarregar o operador de menor, bem entendido.
O "multiset" suporta iteradores bidirecionais,
mas não iteradores de acesso randômico, ou seja, também, não posso usar colchetes.
Aqui vai ter a página que eu me inspirei nesse exemplo que é a página 943,
para quem quiser ir fuçar aquela edição.
Aqui tem um vetorzinho "a" com 10 elementos,
está aqui os caras, o vetor já vem inicializado.
Aqui eu criei um tipo, um typedef, ims,
integer multiset,
que é um multiset parametrizado com inteiro, trabalhando
com operação de menor parametrizada com inteiro.
Criei aqui um MultisetInteiro do tipo ims lá definido.
Aqui um Saída do tipo ostream_iterator.
Aqui eu coloquei, aqui eu estou testando
se existe, quantos 15 existe nesse conjunto.
Bom, por hora não vai ter 15 nenhum, vai retornar 0 aqui.
Agora eu inseri dois números 15,
e está ok porque ele é um multiconjunto, então posso ter dois 15 em um conjunto de inteiros definidos.
Depois do insert dos 15, eu estou
dizendo quantos 15 existe, provavelmente vai dar dois.
Aqui eu criei um const_iterator,
um iterador para aquele camarada lá,
um cons_iterator Resultado.
Olhe só, eu posso pegar, fazer o iterador
apontar para o 15 se o 15 for encontrado no multiconjunto,
aí se o Resultado não está no final, é porque o 15 existe.
Outra coisa que eu posso fazer no Multiset
é inserir um 20 aqui, fazer um insert por exemplo,
e também o meu Resultado fazer um find,
o Resultado vai dizer se ele encontrou ou não,
o Resultado, na prática, vai apontar para o 20,
se ele não encontra, ele vai apontar para o end.
Se o Resultado for igual ao end, não encontrou o valor 20,
se for diferente de end,
encontrou o tal do 20.
"E não é que encontrei a tal do 20!"
Bom, eu posso, além de inserir elemento a elemento,
como eu estou fazendo aqui via insert,
eu também posso usar um...
um insert mais robusto
que é o insert de range, de um dado espaço de memória.
Aqui no caso, ele vai inserir todo o vetor,
vetor "a", bem entendido,
dentro desse MultisetInteiro.
Se tiver elementos que estão repetidos no multiset,
ele vai inserir o repetidos, inclusive, porque é um multiconjunto justamente.
Aqui estou imprimindo através do copy.
Aqui é legal...
eu posso, também, ir lá no meu multiset e fazer um lower_bound.
O lower_bound me trás o que?
Me trás o limite inferior do 9,
encontra, na prática, a primeira ocorrência do elemento 9.
Eu também posso fazer um upper_bound do 9,
encontro o primeiro elemento após a última ocorrência do 9.
Se eu tiver mil noves,
ele vai percorrer os mil noves e pegar o elemento logo após o último nove.
Ambas as funções retornam interators, ou seja, apontamentos,
ou const_iterators apontando para posição apropriada
ou o iterator retornado por end,
se o valor procurado não está no multiset.
O que mais que eu tenho aqui?
Também posso criar um pair, aqui, que eu chamei de "p",
que vai ser um const_iterator em ambos os parâmetros.
O que que esse pair faz?
Eu posso pegar nesse pair
que...
diferente do pair que eu usava lá antes que era iterator com booleano, aqui são dois iterators.
Aqui, então, eu estou usando um pair que são dois iteratos,
e constantes inclusive,
e esse pair vai receber o resultado do equal_range.
equal_range do multiset, número 22.
O equal_range me trás, na verdade ele executa
o lower_bound e o upper_bound conjuntamente.
Ele vai ter o p.first e o p.second.
Aqui ele vai trazer o lower_bound
e o upper_bound automaticamente para mim, é isso que ele faz.
Bom, tudo isso considerado,
recompilar.
Às vezes você está mexendo no código você acaba digitando alguma coisa, então sempre recompila.
Está aqui a execução.
Está ali.
Atualmente existem 0 valores iguais a 15.
Após insert, existem 2 valores iguais a 15.
Encontrou o valor 15, obviamente que ele está lá.
E não é que encontrei a tal do 20, ok.
Após insert de MultisetInteiros...
MultisetInteiros...
Após o insert do vetor, eu encontrei todos esses caras aqui.
Limite inferior do 9 é o próprio 9 que ele encontrou.
Limite superior do 9 é o 15 que está ali.
Usando equal_range para encontrar o limite inferior e superior
de 22, 22 está aqui.
Então, primeiro é o 22 e o último é o 30,
vem depois do último 22 que está ali.
Bom.
Aqui na verdade, pessoal, mais uma vez é para trazer para vocês
exemplificações da riqueza, tanto de componentes,
quanto de algoritmos que a gente tem, de recursos, de métodos,
componentes para lidar com o tocante da STL.
Agora, a gente também vai trabalhar,
já já, com outro elemento que é o map.
Cadê o map?
Aqui está o map nosso de cada dia.
Map, bom, chamei de mapa, Mapa.sln, solution.
Vamos lá.
Faz tempo que não vejo esse código, vamos ver o que ele está fazendo.
Bom, ele está criando um mapa.
Mapa permite eu criar par de coisas.
Vamos primeiro no nosso stdafx,
ver o que a gente está inserindo lá.
Então estou usando o iostream e o map.
Ok.
Aqui eu criei um exemplo adaptado do Deitel, stdafx,
main, aqui eu estou criando um tipo MapaIntReal,
ou seja, vou poder inserir nesse meu mapa, o mapa é um conjunto
só que é um conjunto de duplas,
eu vou poder inserir inteiros e reais.
Preciso inserir duplas em um mapa.
E aí o que acontece?
Ele mapeia o inteiros para os reais,
e eu posso dar alguma significância para isso na minha lógica de execução do programa,
mas o que ele mapei são elementos.
Então aqui eu tenho, por exemplo, eu estou inserindo, criei um mapa de pares aqui,
aqui um para MapaIntReal tipo definido ali,
na prática é isso aqui,
é um map de inteiro, double
e cujo os inteiros são ordenados a partir do operador less para não ter 0 como inteiro.
Aí eu faço o insert.
O insert, para poder inserir duplas,
ele tem que usar a função estática value_type
que existe dentro do mapa inteiros.
Esse é um uso meio extraordinário,
vamos dizer assim, da função estática, mas tudo bem.
Essa função recebe dois números e retorna um pair,
esse par, no caso, é inserido dentro do mapa.
Aqui, então, vai ser inserido todos esses pares.
Se eu tentar inserir um par repetido, ele não deixa,
porque o mapa é um conjunto de pares,
um conjunto não permite elemento repetido.
Eu não vou poder colocar, por exemplo, 15 e 2.7,
talvez eu possa colocar 15.993, como tem aqui,
993, está vendo? 99.3.
Ele não é o mesmo par, é outro par.
Agora, se eu tento colocar exatamente o mesmo par, ele não funciona.
Aqui eu estou contando, contém, aqui criei o Iterador,
iteradorzinho normal.
O Iterador aponta para o início, enquanto o Iterador não estiver no final, Iterador++.
Aqui eu uso o first e o second.
Os iteradores que navegam em mapas, eles vão nevegar em pares
e consegue localizar o first e o second de cada par.
Eu posso usar colchetes, olha que interessante, nos mapas,
o que é algo extraordinário
mas, na prática, o que o colchetes está fazendo é o seguinte:
ele está indo lá e pegando o elemento inteiro 25
e fazendo com que seu par vire uma...
25 o que que era?
33.334.
Agora o 25 vai poder ter, passar a ter o 9999.99.
Ele vai substituir o par 25 e 33.334
pelo par 25 e 9999.99.
Já no 40, não existe posição 40, não existe número 40,
se não existe número 40, ele faz uma traquinagem por trás
e um código de inserção do novo par.
Acresceu o 40 com o 8765.43,
mesma coisa aqui com o 1000
se não existe o elemento 1000 lá,
ele vai acabar inserindo o 1000, o 1000 e o 555.
Aqui eu estou imprimindo de volta os pares.
Isso aqui é só um teste que eu tinha feito outra hora, mas não precisa nesse momento.
Aqui eu vou compilar a coisa, como de hábito.
Jóia.
E executar.
Imprimiu os pares ali,
depois imprimiu o par substituído, o 25,
e preservou os demais, sempre ordenando do menor para o maior a partir da parte inteira,
e inseriu o 40 e o 1000 ali.
Muito legal, então você tem pairs,
que podem ter uma infinidade de aplicações, bem entendido, para pares.
Eu posso, por exemplo, usar para fazer tradutores.
Eu quero saber quais os equivalentes de caracteres de latino para cirílico, por exemplo.
Dá para fazer,
não que seja evidente, mas dá para fazer.
Eu quero saber algum conjunto de coordenadas,
sei lá, por algum motivo, de milhas para quilômetros.
Dá para fazer esse tipo de mapa que vai ter alguns números mais usados,
que servem de referência se, por algum motivo, você não quiser fazer o cálculo.
Deixa eu fechar aqui.
Tem o último componente que a gente vai ver hoje ainda,
que é o multimapa.
Ora, o multimapa é um mapa só que multi,
isso significa que ele permite, então, ter duplas repetidas
de elementos dentro de si, dentro do mapa.
Estou abrindo aqui o MultiMapa.sln, solution.
Ele está processando porque fazia um tempinho que não abria.
Cadê o header?
Está aqui.
Perdão, o header que eu digo é o stdafx.h.
Então estou usando o map,
aparentemente não estou usando mais o algorithm,
usei em algum momento, mas nesse momento não estou usando mais.
Cadê aqui?
stdafx.h, exemplo do Deitel, obviamente,
criei aqui um tipo MultiMapaIntReal, na prática,
é um multimapa de int e double, ordenando os inteiros do menor para o maior,
criei aqui o Pares.
Estou inserindo nesses pares aqui
15 e 2.7, 15 e 99.3.
Aqui estou contando quantos 15 tem, vai me dar 2.
Depois aqui eu inseri todos esses elementos,
inclusive dois elementos repetidos, estão vendo?
Vou criar um iterador
e vou imprimir os pares para ver
se ele realmente inclui todos, inclusive, particularmente, os pares repetidos aqui.
Vou compilar.
E vamos executar.
Está ali.
Primeiro ele achou 0 pares, depois ele achou 15 pares,
está onde isso no código?
Ah sim.
Criou Pares,
inicialmente tem 0 pares mesmo, depois insere e vai ter
2 pares, obviamente.
Aí depois ele insere todos os elementos,
incluindo os repetidos.
Inclusive ele coloca de maneira ordenada pelo índice inteiro.
Bom, pessoal, então é isso.
Aqui nós tivemos uma bela percorrida,
uma bela degustação, uma explicação, acolá dos componentes da STL.
Vimos os mais usuais,
já tínhamos visto vector e list,
vimos ainda hoje pilha, fila, fila com prioridade,
fila com duplo fim, vimos conjunto set, multiconjunto multiset,
vimos mapa e multimapa.
Foi um belo passeio pela STL,
STL você tem que utilizá-la, tem que brincar com ela,
tem que aplicar nos projetos de vocês
para você criar intimidade.
A gente utiliza bastante vector e list, nas minhas provas tenho cobrado
mais vector e list,
às vezes, já caiu um stack, já caiu um queue,
mas é bom conhecer os componentes de qualquer forma.
Espero que vocês tenham aproveitado bem a aula,
e nos vemos na próxima aula,
brevemente, espero.
Bons estudo aí.