paulo1205
(usa Ubuntu)
Enviado em 25/05/2025 - 13:09h
Londreslondres escreveu:
paulo1205 escreveu:
Formas de corrigir:
• Insira os elementos da prioridade que você não quiser numa segunda fila, e depois de a primeira fila ficar vazia, troque as duas filas entre si (dica: basta trocar os ponteiros para o primeiro e para o último elemento de cada fila pelos correspondentes na outra).
Fi-lo, porém não imprime os de prioridade 1 e trava.
Eu falei em trocar de lugar (você inclusive destacou minha sugestão na sua mensagem). Você não trocou de lugar, só sobrescreveu a fila original com a segunda.
Trocando de lugar, a segunda fila vai ficar vazia, o que é essencial para a iteração seguinte do laço de repetição.
Um alternativa é copiar, como você fez, e zerar a segunda fila (vai dar na mesma, nesse caso).
Se você trocar
fila->primeiro = fila2->primeiro;
fila->ultimo = fila2->ultimo;
por
std::swap(fila->primeiro, fila2->primeiro);
std::swap(fila->ultimo, fila2->ultimo);
pode ver que vai imprimir tudo.
Porém você ainda vai ter um problema no seu programa, porque as alocações de memória não encontram desalocações correspondentes. Seu programa usa
new em vários lugares, mas nenhuma vez chama
delete, o que é um erro em C++, causando vazamento de memória, que pode ser observado rodando-se o programa sob a ferramenta
valgrind.
$ g++ -Wall -Wextra -Werror -O2 -pedantic-errors x.cc -o x
$ valgrind -s --leak-check=full ./x
==594225== Memcheck, a memory error detector
==594225== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==594225== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==594225== Command: ./x
==594225==
Imprimindo: atividade.odt - prioridade: 3
Imprimindo: documento.odt - prioridade: 2
Imprimindo: apresentacao.odp - prioridade: 2
Imprimindo: folder.pdf - prioridade: 1
Imprimindo: planilha.ods - prioridade: 1
==594225==
==594225== HEAP SUMMARY:
==594225== in use at exit: 622 bytes in 15 blocks
==594225== total heap usage: 19 allocs, 4 frees, 75,408 bytes allocated
==594225==
==594225== 64 (16 direct, 48 indirect) bytes in 1 blocks are definitely lost in loss record 7 of 11
==594225== at 0x4846FA3: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==594225== by 0x10949D: main (in /tmp/x)
==594225==
==594225== 95 (16 direct, 79 indirect) bytes in 1 blocks are definitely lost in loss record 8 of 11
==594225== at 0x4846FA3: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==594225== by 0x109335: main (in /tmp/x)
==594225==
==594225== 192 (96 direct, 96 indirect) bytes in 2 blocks are definitely lost in loss record 10 of 11
==594225== at 0x4846FA3: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==594225== by 0x1094C6: main (in /tmp/x)
==594225==
==594225== 271 (48 direct, 223 indirect) bytes in 1 blocks are definitely lost in loss record 11 of 11
==594225== at 0x4846FA3: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==594225== by 0x109349: main (in /tmp/x)
==594225==
==594225== LEAK SUMMARY:
==594225== definitely lost: 176 bytes in 5 blocks
==594225== indirectly lost: 446 bytes in 10 blocks
==594225== possibly lost: 0 bytes in 0 blocks
==594225== still reachable: 0 bytes in 0 blocks
==594225== suppressed: 0 bytes in 0 blocks
==594225==
==594225== ERROR SUMMARY: 4 errors from 4 contexts (suppressed: 0 from 0)
Na verdade, duas das chamadas a
new nem ao menos precisariam existir: não há por que fazer com que
fila e
fila2 sejam ponteiros; podem muito bem ser objetos diretamente.
Só fazendo a mudança de ponteiros para objetos (e as correspondentes trocas de “
fila->alguma_coisa” e “
fila2->alguma_coisa” para “
fila.alguma_coisa” e “
fila2.alguma_coisa”), a saída do
valgrind já muda.
$ valgrind -s --leak-check=full ./x
==600873== Memcheck, a memory error detector
==600873== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==600873== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==600873== Command: ./x
==600873==
Imprimindo: atividade.odt - prioridade: 3
Imprimindo: documento.odt - prioridade: 2
Imprimindo: apresentacao.odp - prioridade: 2
Imprimindo: folder.pdf - prioridade: 1
Imprimindo: planilha.ods - prioridade: 1
==600873==
==600873== HEAP SUMMARY:
==600873== in use at exit: 590 bytes in 13 blocks
==600873== total heap usage: 17 allocs, 4 frees, 75,376 bytes allocated
==600873==
==600873== 271 (48 direct, 223 indirect) bytes in 1 blocks are definitely lost in loss record 8 of 9
==600873== at 0x4846FA3: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==600873== by 0x109355: main (in /tmp/x)
==600873==
==600873== 319 (96 direct, 223 indirect) bytes in 2 blocks are definitely lost in loss record 9 of 9
==600873== at 0x4846FA3: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==600873== by 0x1094AE: main (in /tmp/x)
==600873==
==600873== LEAK SUMMARY:
==600873== definitely lost: 144 bytes in 3 blocks
==600873== indirectly lost: 446 bytes in 10 blocks
==600873== possibly lost: 0 bytes in 0 blocks
==600873== still reachable: 0 bytes in 0 blocks
==600873== suppressed: 0 bytes in 0 blocks
==600873==
==600873== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
As quantidades de blocos e contextos com vazamento ficarem duas unidades menores porque duas alocações manuais (de
fila e
fila2) deixaram de existir. Mas ainda há a questão da alocação e (falta de) desalocação dos elementos que são colocados dentro dessas duas filas ao longo da execução do programa, as quais ocorrem nos seguintes momentos:
1. Logo após a declaração de fila, quando ela é preenchida com cinco elementos (5 alocações).
2. No laço de repetição, quando
i==3,
fila2 recebe quatro elementos novos (4 alocações).
3. Quando
i==2,
fila2 recebe dois elementos novos (2 alocações).
As alocações em
fila2 não são estritamente necessárias, porque podemos mover o elemento que já existe na
fila, tomando apenas os cuidados de não deixar a fila original sem um primeiro elemento. O problema é que, da forma como você criou as classes
Elemento e
Fila, fica meio feio de o fazer, e acaba sendo necessário mexer pelo menos um pouco na classe Fila e no código do laço de repetição que tenta esvaziar a fila de impressão.
class Fila{
public:
/* ... */
// A função-membro mover() recebe como argumento uma segunda fila, para o final da qual o primeiro elemento desta fila deve ser movido.
void mover(Fila &outra_fila){
if(primeiro){
auto prox=primeiro->proximo;
if(!outra_fila.primeiro){
outra_fila.ultimo=outra_fila.primeiro=primeiro;
outra_fila.primeiro->proximo=nullptr;
}
else {
outra_fila.ultimo->proximo=primeiro;
outra_fila.ultimo=primeiro;
outra_fila.ultimo->proximo=nullptr;
}
primeiro=prox;
}
}
/* ... */
};
/* ... */
int main(){
/* ... */
for(int i = 3; i > 0; i--){
while(fila.primeiro != nullptr){
if(fila.espiar()->prioridade == i){
std::cout << "Imprimindo: " << fila.espiar()->nome << " - prioridade: " << fila.espiar()->prioridade << std::endl;
fila.remover();
}
else
fila.mover(fila2);
}
std::swap(fila.primeiro, fila2.primeiro);
std::swap(fila.ultimo, fila2.ultimo);
}
}
Com isso, reduzem-se um pouco mais os vazamentos de memória.
$ valgrind -s --leak-check=full ./x
==1684944== Memcheck, a memory error detector
==1684944== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==1684944== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==1684944== Command: ./x
==1684944==
Imprimindo: atividade.odt - prioridade: 3
Imprimindo: documento.odt - prioridade: 2
Imprimindo: apresentacao.odp - prioridade: 2
Imprimindo: folder.pdf - prioridade: 1
Imprimindo: planilha.ods - prioridade: 1
==1684944==
==1684944== HEAP SUMMARY:
==1684944== in use at exit: 271 bytes in 6 blocks
==1684944== total heap usage: 9 allocs, 3 frees, 75,040 bytes allocated
==1684944==
==1684944== 127 (48 direct, 79 indirect) bytes in 1 blocks are definitely lost in loss record 5 of 6
==1684944== at 0x4846FA3: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1684944== by 0x1093E3: main (in /tmp/x)
==1684944==
==1684944== 144 (48 direct, 96 indirect) bytes in 1 blocks are definitely lost in loss record 6 of 6
==1684944== at 0x4846FA3: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1684944== by 0x109335: main (in /tmp/x)
==1684944==
==1684944== LEAK SUMMARY:
==1684944== definitely lost: 96 bytes in 2 blocks
==1684944== indirectly lost: 175 bytes in 4 blocks
==1684944== possibly lost: 0 bytes in 0 blocks
==1684944== still reachable: 0 bytes in 0 blocks
==1684944== suppressed: 0 bytes in 0 blocks
==1684944==
==1684944== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
Para acabar com os vazamentos de memória de vez, temos de providenciar a desalocação dos elementos que foram dinamicamente alocados.
class Fila{
public:
/* ... */
~Fila(){
while(primeiro)
remover();
}
/* ... */
void remover(){
auto velho=primeiro;
primeiro = primeiro->proximo;
delete velho;
}
/* ... */
}; $ valgrind -s --leak-check=full ./x
==1688324== Memcheck, a memory error detector
==1688324== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==1688324== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==1688324== Command: ./x
==1688324==
Imprimindo: atividade.odt - prioridade: 3
Imprimindo: documento.odt - prioridade: 2
Imprimindo: apresentacao.odp - prioridade: 2
Imprimindo: folder.pdf - prioridade: 1
Imprimindo: planilha.ods - prioridade: 1
==1688324==
==1688324== HEAP SUMMARY:
==1688324== in use at exit: 0 bytes in 0 blocks
==1688324== total heap usage: 9 allocs, 9 frees, 75,040 bytes allocated
==1688324==
==1688324== All heap blocks were freed -- no leaks are possible
==1688324==
==1688324== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
No entanto, mesmo tendo eliminado todos os
bugs latentes, o código, no fim das contas, ficou inconsistente e ineficiente.
Inconsistente porque a alocação do elemento fora da classe
Fila e sua desalocação dentro de funções da classe apontam para uma possível (e bem real) violação de encapsulamento. Afinal de contas, o usuário deveria se preocupar apenas com nomes de arquivo e prioridades de cada um ao enviá-los para a fila de impressão, não com a existência de de uma entidade
Elemento, e muito menos que essa entidade não possa nem ser criada diretamente, mas sim na forma de ponteiro para dado dinamicamente alocado. Também a forma de mover os dados de uma fila para outra acabou aparecendo como um remendo feio para um problema de projeto da classe.
Aliás, nem mesmo sei se faz sentido falar em encapsulamento numa classe que tem todos os seus membros públicos, incluindo ponteiros. Por que um usuário da classe deveria usar a função-membro
espiar() em lugar do membro de dados
primeiro, se ambos estão igualmente disponíveis e, na prática, produzem exatamente o mesmo efeito? Você mesmo, aliás, usou
fila->primeiro para testar a condição do laço de repetição, mas
fila->espiar() na avaliação do nível de prioridade do próximo elemento da fila e na impressão, nas duas linhas imediatamente seguintes.
E ineficiente porque a varredura da fila se tornou também uma operação O(n²) (tipicamente precisando de exatamente
n²+n operações para varrer uma fila de tamanho
n). Um algoritmo que trabalhe com filas deveria ser O(n), ou muito próximo disso, para varrer a fila, e bem próximo de O(1) para as operações de inserção e exclusão.
Segue abaixo um esqueleto de implementação de fila de prioridade (classe
FilaPrio) que visa a eliminar pelo menos uma parte dos problemas acima. Ela trata cada valor possível de prioridade como uma fila comum, distinta das filas dos demais níveis, de modo a não apenas deixar as operações de entrada na fila e saída da fila O(1), mas permitir que a varredura da lista respeitando a prioridade ocorra em O(n). Note como a fila comum (classe
FilaPrio::FilaSimples) e a estrutura que representa os nós dessa fila simples (classe
FilaPrio::No) são detalhes de implementação de
FilaPrio, declaradas internamente e marcadas como
private na classe que as contém.
#include <iostream>
#include <string>
class FilaPrio {
public:
static const unsigned MAX_PRIO=3;
private:
class FilaSimples {
private:
struct No {
std::string data;
No *prox;
No(const std::string &s): data(s), prox(nullptr) { }
No(std::string &&s): data(std::move(s)), prox(nullptr) { }
};
No *prim, *ult;
size_t tam;
public:
FilaSimples(): prim(nullptr), ult(nullptr), tam(0) { }
FilaSimples(const FilaSimples &outra): FilaSimples() {
for(auto p=outra.prim; p; p=p->prox)
entra(p->data);
}
FilaSimples(FilaSimples &&outra): FilaSimples() { swap(*this, outra); }
~FilaSimples(){
while(prim){
auto prox=prim->prox;
delete prim;
prim=prox;
}
}
FilaSimples &operator=(FilaSimples outra){
swap(*this, outra);
return *this;
}
size_t tamanho() const { return tam; }
bool vazia() const { return !tam; }
void entra(const std::string &s){
if(!prim)
prim=ult=new No(s);
else {
ult->prox=new No(s);
ult=ult->prox;
}
++tam;
}
void entra(std::string &&s){
if(!prim)
prim=ult=new No(std::move(s));
else {
ult->prox=new No(std::move(s));
ult=ult->prox;
}
++tam;
}
std::string sai(){
if(!prim)
throw std::logic_error("fila vazia");
std::string s(std::move(prim->data));
auto old=prim;
prim=prim->prox;
delete old;
--tam;
return s;
}
friend void swap(FilaSimples &f1, FilaSimples &f2){
std::swap(f1.prim, f2.prim);
std::swap(f1.ult, f2.ult);
std::swap(f1.tam, f2.tam);
}
};
unsigned prio_max;
FilaSimples fila_prio[MAX_PRIO+1];
size_t tam;
public:
FilaPrio(): prio_max(0), fila_prio(), tam(0) { }
FilaPrio(const FilaPrio &outra): prio_max(outra.prio_max), fila_prio(), tam(outra.tam) {
for(unsigned n=0; n<=MAX_PRIO; ++n)
fila_prio[n]=outra.fila_prio[n];
}
FilaPrio(FilaPrio &&outra): FilaPrio() { swap(*this, outra); }
FilaPrio(std::initializer_list<std::pair<std::string, unsigned>> l):
FilaPrio()
{
for(const auto &i: l)
entra(i.first, i.second);
}
FilaPrio &operator=(FilaPrio fp){
swap(*this, fp);
return *this;
}
size_t tamanho() const { return tam; }
bool vazia() const { return !tam; }
unsigned maior_prio() const { return prio_max; }
void entra(const std::string &s, unsigned prio=0){
if(prio>MAX_PRIO)
prio=MAX_PRIO;
if(prio>prio_max)
prio_max=prio;
fila_prio[prio].entra(s);
++tam;
}
void entra(std::string &&s, unsigned prio=0){
if(prio>MAX_PRIO)
prio=MAX_PRIO;
if(prio>prio_max)
prio_max=prio;
fila_prio[prio].entra(std::move(s));
++tam;
}
std::string sai(){
std::string s(fila_prio[prio_max].sai());
if(fila_prio[prio_max].vazia())
while(prio_max>0 && fila_prio[--prio_max].vazia())
;
--tam;
return s;
}
friend void swap(FilaPrio &fp1, FilaPrio &fp2){
std::swap(fp1.prio_max, fp2.prio_max);
std::swap(fp1.fila_prio, fp2.fila_prio);
std::swap(fp1.tam, fp2.tam);
}
};
int main(){
FilaPrio f{
{"documento.odt", 2},
{"folder.pdf", 1},
{"planilha.ods", 1},
{"atividade.odt", 3},
{"apresentacao.odp", 2}
};
while(!f.vazia())
std::cout << "Imprimindo (prioridade " << f.maior_prio() << "): " << f.sai() << '\n';
}
... Então Jesus afirmou de novo: “(...) eu vim para que tenham vida, e a tenham plenamente.” (João 10:7-10)
