Pessoal, boa noite.
Aqui é o professor Simão falando.
Estamos em Curitiba.
No dia 9 de julho de 2020.
Eu tô aqui pra falar
do Grupo de Slides número 3 parte C.
Aonde a gente vai começar a falar um pouco de de listas,
na prática até de coleções, né,
que permitem a gente tratar relacionamentos entre objetos, tá.
Introdução a listas em C++.
Pois bem.
Aqui a gente tem a classe Universidade
com aquele relacionamento dela
para com o grupo de... conjunto de Departamentos, tá.
Então, se você olhar ali, a gente criou
uma lista de ponteiros Departamento.
As vezes evolui um pouco o nome, como evoluiu aqui
mas não tem problema o conceito é o mesmo.
Aqui são 50, um vetor
de 50 ponteiros de Departamento.
E ali tem o setDepartamento() que vocês já conhecem.
Bom, qual é o problema dessa solução?
O problema dessa solução é que ela tem um número um pouco limitado, né,
número de Departamentos que podem tá, enfim, relacionados com uma Universidade.
Conforme já discutido em aula anterior,
ali você tem o problema de ficar limitado
a 5... perdão, a 50 Universidades.
Muito bem.
Como é que a gente resolve isso?
Bom, uma maneira de resolver isso, conforme eu já indiquei pra vocês, tá.
é vocês trabalharem com alocação de memória dinâmica.
Em vez daqui de vocês terem esse número 50
vocês podem ter só um ponteiro Departamento
e através desse apontamento usar lá o memory allocation
pra alocar uma quantia x
e depois, à medida que a coisa for evoluindo
e a quantia x lotar, você pode alocar x+n.
Usando artifícios como realloc, free,
ou malloc, free, malloc, enfim.
Vocês podem utilizar essas manipulações de alocação de memória.
Já de antemão e eu aviso pra vocês,
que o C++ tem uma outra maneira alternativa,
e própria dele, de alocar memória.
Em vez de usar o comando malloc, memory allocation,
ele tem o new, em vez de usar o comando free, ele tem o delete.
Entretanto, as duas formas funcionam no C++.
Só que se você alocar com o malloc, você tem que liberar com o free.
Se você alocar com o new, você vai ter que desalocar com o delete.
Então, é melhor não misturar, aliás, você não pode misturar esses pares de comando, tá.
Se você fez com malloc, libera com o free.
Se você fez com o new, libera com o delete.
E via de regra você deve usar no teu sistema inteiro só um formato de alocação.
Ou malloc-free ou new-delete.
Mas a gente vai ver isso pra frente, não se preocupem nesse exato momento
é apenas uma observação.
Legal.
Bom, então, vocês poderiam, de qualquer forma,
ter feito essa solução aí, usando alocação de memória dinâmica, tá.
Com técnicas que vocês já viram lá
em Fundamentos de Programação 1, ou matéria equivalente.
Muito bem. Agora uma outra maneira de você
não precisar ter que alocar e desalocar memória dinamicamente
fazendo tudo na unha, por assim dizer.
No braço, por assim dizer.
Você pode usar um componente existente do C++.
Pode usar um componente chamado Vector.
O Vector é, justamente, um componente que já faz essas alocações e desalocações
de maneira transparente pra você.
Então, quando estamos em construção usar o Vector do C++
que faz parte da STL.
A STL é a Standard Template Library.
Essa é uma Biblioteca Padrão de Templates.
O que que é um template? O que que é um gabarito?
Pra gente ter a Biblioteca Padrão de Gabaritos, tá.
É um tipo, por exemplo aqui, o tipo Vector
que pode ser parametrizado com outro tipo.
Então, aqui eu tô criando, por exemplo, um Vector
que vai servir para ponteiros Departamento.
Se eu quisesse um Vector de inteiro, eu ia passar um inteiro aqui.
Se eu quisesse ponteiros de inteiro, eu ia por int*.
Se eu quisesse aqui um Vector de Professores, eu ia ter Vector Professor*,
e assim vai.
Então, um template permite você criar
permite, na verdade, você ter um tipo que é parametrizado com outro tipo.
E aí criar instâncias mais flexíveis em função da parametrização
Conforme eu já disse, eu poderia criar aqui Vector
de ponteiro de Professores,
Vector de ponteiro de inteiros, Vector de inteiros e por aí vai.
Aqui eu tô dando um exemplo então, tá.
Eu tô criando agora um LpDptos
que não é mais um vetorzinho normal, ordinário no sentido de comum.
Agora eu tô criando um LpDpto que é um Vector, ou seja,
um vetor extraordinário, porque ele é baseado num componente preexistente lá da STL
O Vector aqui gente, então, insisto, ele é um... vai ser um conjunto
que vai permitir absorver e receber ponteiros de Departamento.
Há slides subsequentes que detalham
os componentes do tipo List e Vector.
A gente tá vendo o Vector nesse momento
da Standard Template Library, STL do C++.
A STL, Standard Template Library,
Biblioteca Padrão de Templates ou Gabaritos,
traz inclusive um conjunto de estrutura de dados como listas, filas e pilhas.
Estas estruturas são implementadas genericamente,
na forma de gabaritos ou templates.
Aqui é uma introdução, tá, pra vocês saberem que existe o Vector
Se quiserem ir já se simpatizando, utilizando aqui e acolá.
É um componente interessante e saber também que a STL existe
é uma biblioteca bastante pertinente pra utilidades de vocês.
Aqui, por exemplo, eu tenho o setDepartamento() recebendo o Departamento...
o endereço do Departamento como parâmetro
ele vai ter que armazenar lá naquele conjunto, né.
Então, nessa coleção aqui.
Então, tá aqui, ó. Eu recebo o ponteiro
e repasso o LpDptos,
A lista de ponteiros de Departamentos
usando o comandinho já pré-programado,
porque o componente já tá feito, né, o comando já existe, que é o push_back().
O push_back() empurra o final da lista, né, por assim dizer, ou seja, pra
as costas da lista... perdão, do vetor
o ponteiro passado por parâmetro ou o endereço, melhor dizendo,
de ponteiro que foi passado por parâmetro.
E aqui você vai ter, então,
você pode colocar aqui 10 Departamentos
nessa... na Universidade. Você pode colocar
20, 50, 51, 500, tá.
Por quê?
Porque o componente Vector já vai fazer esse procedimento de alocação
desalocação de memória, tá, pra você
sem que você se preocupe com isso
Tá, vamos um slide pra frente aqui. O que que vai mudar? Ah, sim.
Agora eu criei aqui uma funçãozinha a mais
chamada imprimeDepartamentos().
Tô salientando também qual é o include que eu utilizo
pra poder aplicar o componente Vector.
É a biblioteca vector, né.
Usando sempre o namespace std.
Tá ali o nosso setDepartamento().
Eu até aqui podia ter um if, né, testando se o pDep não é um ponteiro nulo.
pra não incluir coisa nula na lista.
Então seria interessante, né.
Vocês podem fazer isso na versão de vocês aí.
E aqui temos o imprimeDepartamentos().
Eu procurei fazer uma versão bem pedagógica
do imprimeDepartamentos() que é o seguinte.
A primeira coisa que eu faço, crio um ponteiro temporário
pDep, que é ponteiro Departamento,
que já é inicializado com nulo, já é aterrado.
O LpDptos, lista de ponteiros de Departamento, é do tipo vector.
O vector prevê uma funçãozinha size(),
que retorna o tamanho, ou seja, a quantidade de elementos
que tão aí dentro dessa coleção aqui, tá.
E armazeno isso em tamanho (tam). Tamanho uma variável inteira, né.
Vejam que eu tô usando um casting aqui, ou seja, um forjamento, uma conversão, tá.
Porque se você olhar certinho a especificação do size(),
você vai ver que ele retorna long int e não int.
Então, eu tô garantindo aqui que eu vou retornar um long int
e vou converter pra int pra armazenar em tamanho.
A maior parte dos compiladores já ia fazer essa compilação automática, tá.
mas a gente é cuidadoso, então a gente tá fazendo essa
conversão aí explicitamente.
Se você digitar lá no Google, ou olhar nos livros de referência do C++
lá tem a biblioteca STL com as propriedades,
as assinaturas de função, né, disponíveis em cada componente da STL.
No caso do vector, você já viu aí que temos a função push_back()
e temos a função aqui size(),
mas tem várias outras, bem entendido, que a gente vai explorar na sequência.
Aqui eu tenho um forzinho, um int i que recebe zero.
Enquanto i for menor que tamanho i é incrementado de 1 em 1, i++.
O que eu faço ali?
isso vai permitir que eu navegue no vetor,
ou no vector, melhor dizendo, né.
Vou chamar de vector pra distinguir, justamente, do vetorzinho normal
ordinário, né, no sentido de comum.
O vector é um vetor extraordinário.
Então esse vector aqui, ele já é preparado
o componente vector, ele já preparado pra utilizar o operador de colchetes.
Então, ele já é programado através de uma série de astúcias
pra utilizar o operador de colchetes.
Na verdade, essa astúcia se chama sobrecarga de operadores, tá.
A gente vai aprender a fazer essas astúcias
na sequência da disciplina, permitindo usar um objeto nosso
colchetes ([]), mais mais (++), menos menos (--), tá,
da maneira que nos convier, mas isso é assunto pra sequência.
Se você olhar aqui o i, por exemplo.
O i, na verdade, é um objeto temporário da classe inteiro
que tá usando aqui o ++.
Isso é como se fosse um método, tá, operator++().
Então, ele foi programado lá por quem montou o inteiro pra trabalhar com ++ no i.
Mas tudo bem, ali, ó, é um inteiro. No caso aqui o i é um inteiro.
Muito bem.
O fato aqui, gente, voltando ao ponto,
é o seguinte, eu tenho um forzinho aqui que vai percorrer de zero até tamanho.
Vai percorrer então, percorrer o quê? Vai percorrer o vector
usando aqui o colchetes, tá.
Aqui ele vai, na primeira passagem, ele vai acessar a primeira posição do vector.
depois a segunda, depois a terceira e assim vai.
E ele faz o quê com isso?
Ora, eu pego o apontamento
o endereço que está na posição i,
no caso lá da primeira posição, a posição zero,
vou jogar dentro de pDep que é um ponteirinho temporário.
E a partir dali eu recupero o nome do cara apontado lá dentro do vector.
Bom, a segunda passagem recupera a do segundo elemento
a terceira passagem do terceiro elemento e assim vai, tá.
Lembrando que você começa a contagem em zero e não em um
em vetores e em vectors do C e em C++,
do C++ aqui no caso do vector, bem entendido.
Bom, aqui então, na verdade, é basicamente pra fazer uma navegação aí, gente,
no vector que eu criei, tá.
Nessa instância de vector chamada LpDptos,
que é um acrônimo de lista de ponteiros de Departamentos.
Claro que isso aqui é uma versão bem pedagógica, né.
Eu posso fazer versões um pouco mais pragmáticas, tá.
Como essa aqui, tá. Essa aqui é muito mais direta.
Eu acesso diretamente lá cada posição do vector
e, já a partir dali, já recupero o apontamento dado
e já chamo o getNome()
São equivalentes essa aqui muito mais pragmáticas.
talvez menos pedagógica, mas mais pragmática.
Aqui tem uma observação que diz o seguinte
O Vector da Standard Template Library (STL),
seria um certo tipo de lista
sendo que existe o List da STL que não é
propriamente dito o Vector, tá,
mas eles são aparentados
Com vantagem de utilizar o operador de colchetes
tal qual fosse um vetor comum,
uma vez que tenha dados no vector em questão.
Aqui o que eu quis dizer é o seguinte, tá.
O Vector ele vai ser, na verdade, uma coleção de coisas,
tal qual o List o é.
Ainda que eles usem táticas distintas, tá.
Qual é a diferença dessas táticas?
A diferença é o seguinte, tá.
Enquanto o Vector
muito que provavelmente usa dentro de si
alocação e desalocação de memória
o List da STL, que já é outro componente,
que a gente vai ver na sequência,
ele já vai usar a técnica de lista encadeada.
Duplamente encadeada, no caso.
Então, os dois componentes servem,
tanto o Vector quanto o List,
eles servem pra quê? Pra trabalhar com coleções de coisas.
O Vector ele vai trabalhar com alocação e desalocação de memória.
Sempre fechando um número. Aloca 50
a hora que lotar, através de astúcias, aloca 100.
Copiando o que tinha naqueles 50 pra esses 100.
E aí tendo mais 50 espaços, e assim vai, né, em cada lotação.
Já o Lista, usa outra técnica.
Insisto, técnica de encadeamento, de lista encadeada
que eu vou detalhar pra vocês, na sequência.
Do ponto de vista, inclusive, da orientação a objetos.
Bom, se aqui eu tô usando Vector,
como um exemplo de componente da STL,
é natural que eu mostre pra vocês também o List. Não é isso?
Então, agora, vejam que eu não tô usando mais o Vector, tô usando o List.
Fiz uma nova versão dessa classe Universidade, tá,
substituindo o Vector pelo List, insisto.
E aí, obviamente que eu tenho que fazer um #include lá, tá.
Continuo tendo a função setDepartamento().
Veja que o Lista, tal qual o Vector,
também tem o push_back().
Não são todas as funções que o Vector e o List compartilham
e nem todos os operadores, mas tem coisas que eles compartilham.
Por exemplo, o List não tem o operador de colchetes,
não funciona o operador de colchetes com ele.
Já no Vector funciona.
Mesmo porque a gente supõe que
vetores, né, por mais que sejam extraordinários
utilizam o operador de colchetes.
Aqui nessa nova versão eu recrio o imprimeDepartamentos().
Só que agora como o List
que é esse outro componente da STL
ele não trabalha com colchetes
você tem que usar algum artifício pra ele navegar no list.
Ora, pra isso, existe um negócio chamado iterator.
Então, aqui eu tô criando um iterador que vai permitir iterar, ou seja, eu navegar
na coleção de dados, né, nesse caso na lista propriamente dita.
Este iterador, em português, é do tipo iterator
Veja que esse tipo aqui é um tipo que está aninhado
que pertence ao list.
Então, o list, ele já é um tipo
e o list tem dentro de si, um outro tipo
chamado de iterator, tanto é que eu tô criando o objeto aqui iterador
que se está dentro do list
é porque ele tem uma forte intimidade com o list, tá.
Se ele pertence...
dois pontos, dois pontos (::) é pertencimento, tá, é relacionamento, né, em alguma medida.
Então, significa que tem uma forte relação.
Que relação é essa? Ora,
O iterador vai permitir, justamente... o iterator, aqui no caso,
vai permitir justamente navegar nessa lista.
E, nesse caso, o iterador vai permitir navegar em que tipo de lista?
Lista de ponteiro Departamento.
O ponteiro... os componentes list
eles podem... eles tem uma funçãozinha begin()
que retornam pro início da lista.
Então, aqui o iterador vai tá navegando no início da lista, num primeiro momento.
Enquanto o iterador não estiver no final da lista
o iterador vai incrementando, navegando de posição em posição da lista.
O iterador ele mostra a posição inicial da lista.
Mas pra eu ver o conteúdo
da posição inicial da lista
toda posição em que o iterador estiver, em algum momento,
eu tenho que colocar um asterisco na frente.
Tal qual eu faço com ponteiros, gente.
Então, esse iterador aqui, em alguma medida,
por assim dizer, é um ponteiro de alto nível
Então, colocando um asterisco na frente do iterador eu vou recuperar
o conteúdo pra onde esse iterador está apontando.
Na prática, eu vou recuperar então, o ponteiro Departamento que está nessa lista.
Vou armazenar... vou colocar nesse ponteiro temporário pDep aqui,
e a partir do pDep informa o nome.
Obvio que posso fazer também uma versão muito mais pragmática,
desse imprimeDepartamentos() que essa versão aqui, tá.
Eu vou lá e já faço um acesso mais direto.
Sempre usando o operador de asterisco na frente do iterador.
Na verdade o iterador também é um objeto
da classe iterator, tá, e a classe iterator foi preparada pra trabalhar com o operador
de asterisco, tal qual, acontece com ponteiros, né,
que permitem, na hora que você coloca o asterisco na frente, recuperar a informação
que tá apontada por aquele ponteiro.
Então, isso daqui é legal, tá, porque permitiu vocês verem que
em vez de fazer, vou voltar lá no início dessa apresentação, tá.
Em vez de eu usar um vetorzinho fixo,
ou eu ficar quebrando cabeça, mas porque não, né, se eu quiser fazer isso
alocar e desalocar memória na unha,
tem como alternativa usar o Vector.
Que é o que vocês tão vendo agora em tela nesse slide 4, tá.
E aí, com as astúcias que o Vector permite.
Ou, alternativamente, eu posso usar um aparentado do Vector que é o List.
Tanto o Vector e o List elementos da STL.
O List não trabalha com operador de colchetes
porque em contrapartida ele permite esse artifício do iterador.
Muito bem.
Agora eu coloco umas questões pra vocês, tá, pra fins de reflexão.
Como compor uma classe similar ao List e mesmo ao Vector?
Bom, o Vector a gente mais ou menos sabe, tá.
Porque é alocação e desalocação de vetor.
Não é isso?
Inclusive, eu até rogo
que vocês façam esse exercício em casa, pra se divertir.
E agora como é que eu faço um equivalente a um List?
O List trabalha com aquela técnica de lista encadeada.
Como é que eu faço uma lista encadeada, particularmente, orientada a objetos?
Essa é uma questão que se apresenta.
E, antes disso, para que saber isto?
Por que eu vou querer saber fazer uma lista
ou mesmo um vector, na unha,
se eu já tenho os componentes prontos na STL.
Bom, vai ter casos gente,
em que vocês vão estar trabalhando em sistemas embarcados, por exemplo,
e esses sistemas vão ser sistemas onde vai ter pouca memória
e pouca capacidade de processamento, tá, por questões mercadológicas
aonde você vai fazer código em C ou em C++, tá,
e você vai querer ser bastante econômico no que você tá fazendo.
Acontece também pra muitos sistemas em tempo real, que na hora são embarcados.
Você quer ser econômico em termos de código,
para que o teu tempo de resposta seja
numa dada janela de tempo que você tenha ali que as vezes pode ser
de pequenas frações de segundo.
Muito bem.
Quando se usa um componente pronto, como o List e o Vector,
que é muito bom utilizar porque ele tá pronto, está funcional, certinho, testado etc.
Ele tem um contraponto. Este contraponto
é que às vezes o List e o Vector tem mais códigos do que você precisa,
ou seja, ele não é tão enxuto quanto você gostaria, eventualmente.
Então, tá aí uma motivação pra você saber fazer o próprio componente, né.
Então, tá ali as respostas, ó.
Para poder elaborar sua própria lista caso necessite, nesse âmbito
que eu já descrevi aqui.
Ademais, porque é um bom exemplo para se aprender
detalhes e nuances da orientação a objetos dentre outros.
De fato, montar uma lista encadeada orientada a objetos,
ela é bastante interessante para aprender uma série de conceitos da orientação a objetos.
Ela é um exemplo bastante rico.
Além do mais, saber implementar isto, né,
a lista duplamente encadeada,
ajudará a ter uma introdução útil
para a disciplina de Estrutura de Dados.
Isso é legal mesmo, tá.
Porque lá em Estrutura de Dados, até onde me consta,
vocês, não raro, vão implementar a lista encadeada em C,
ou seja, procedimentalmente.
E aqui vocês vão implementar orientado a objetos.
Em fazendo orientado a objetos, o que acontece
vocês vão poder comparar como é que uma implementação
de algo clássico, como uma lista encadeada,
em procedimental e orientado a objetos, né,
já permitindo uma primeira comparação aí,
ou uma comparação um pouquinho mais aguçada entre paradigmas, tá.
Continuando a leitura. Entretanto,
muito que obviamente, é apenas um conhecimento,
coincidente e felizmente útil, para tal disciplina.
Eu quero dizer aqui que eu não tô invadindo, tá, a disciplina de Estrutura de Dados
Eu tô pegando o mesmo objeto de estudo
que é a lista encadeada que me é útil pra explicar a orientação a objetos.
E aí, a disciplina de Estrutura de Dados ela vai rever outros detalhes
da questão de lista encadeada que nós não veremos aqui
a gente vai ver o que interessa pra nós do ponto de vista do aprendizado de OO.
Por fim, ao bem da verdade, a disciplina de Estrutura de Dados
discorre sobre uma diversidade muito maior de estrutura de dados,
além de listas, e mesmo pilhas e filas,
e abordagem algorítmicas
para tal conjunto de estrutura de dados.
Verdade, tá.
Além de montar listas, você vai ter maneiras de percorrimento da lista mais ou menos inteligente.
Você além de estudar listas,
filas, pilhas vai estudar árvores, grafos e outros elementos, tá.
Mas isso aqui é só pra dizer que então que
as vezes você tem o mesmo objeto
e você estuda esse objeto sobre ângulos distintos
em disciplinas distintas, tá.
Aqui é o caso que é a questão de lista encadeada.
Bom, pessoal, essa aqui foi uma aula mais curta, tá.
Desse Grupo de Slides 3 parte C.
Espero que tenham gostado.
Nos vemos na próxima aula,
aonde a gente já vai, justamente, começar a aprender
a fazer listas encadeadas orientadas a objeto.
Até breve.