Newsgroup: it.comp.lang.c++
Titolo: Dove posso migliorare?(lunghetto)

Sto cercando di esercitarmi per un esame che avrò a breve, e vi sarei grato
per delle eventuali correzioni al mio codice.
Veniamo al dunque: ho cercato di realizzare una classe pila con
record concatenati e allocati dinamicamente,il record è costituito da un
campo intero e uno puntatore
al record precedente, questa è la specifica:
#ifndef pilad_H_
#define pilad_H_
struct record{
int dato;
record * prec;
};
typedef record * P;
class pilad{
public:
pilad(){testa=0;}
void push(const int e);
void pop(int& e);
void top(int& e)const;
bool emply()const;
void stampa()const;
~pilad();//distruttore
private:
P testa; // puntatore alla testa della pila
};
#endif
E l'implementazione:
#include "pilad.h"
#include<iostream>
void pilad::push(const int e){
P p;
p=new record;
p->dato=e;
p->prec=testa;
testa=p;
}
void pilad::pop(int& e){
e=testa->dato;
P p=testa;
testa=testa->prec;
delete p;
}
void pilad::top(int& e)const{
e=testa->dato;}
bool pilad::emply()const{
return (testa==0);
}
void pilad::stampa()const{
P q=testa;
 while(q!=0){
  cout<<q->dato<<endl;
  q=q->prec;
  }
}
pilad::~pilad(){
P p1=testa;
 while(p1!=0){
  testa=testa->prec;
  delete p1;
  p1=testa;
 }
}
Come posso verificare se il distruttore deallochi correttamente ogni record
della pila?
Inoltre è possibile fare in modo che la pila stampi gli elementi dall'inizio
e non dalla fine?(lo so sarebbe contro i principi logici della pila..ma
vorrei sapere se si può fare)
Oltre queste domande vi chiedo solo si segnalarmi tutto ciò che non va nel
codice e come migliorarlo.
Grazie.

 codice e come migliorarlo.
Mi sembra che vada bene, ma lascio la parola agli esperti ;)
Ciao,
Cecco

 codice e come migliorarlo.
1) invece che prendere un reference e tornare void, top e pop potrebbero
non prendere parametri e ritornare l'oggetto di testa.
2) Aggiungi il copy constructor e il copy operator.
3) Rendi il tutto "templated" rispetto all'oggetto contenuto.
poi basta altrimenti tanto vale che usi la STL!
--
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

 inutile.
Lo so che è inutile, ma in teoria dovrebbe migliorare la
leggibilità(rendendo immediatemante comprensibile che il parametro è di
ingresso)
....almeno secondo il mio prof.,e all'esame preferisco fare come dice lui!!
:-))
2) Aggiungi il copy constructor e il copy operator.
Con "copy operator" ti riferisci all'operatore di assegnazione?
Cmq non li ho inseriti(sarebbe stato più corretto definirli privati in modo
da renderli non usabili) perchè secondo il mio libro: "...è opportuno
inibire l'assegnazione tra pile.."
E ti devo dire che non l'ho capita,ma mi sono adeguato al libro!
....forse considera l'assegnazione tra pile come samanticamente sbagliato,
nel senso che non sarebbe una cosa molto efficace assegnare una pila ad
un'altra già esistente..ma forse mi sto arrampicando sui muri...secondo te a
cosa si potrebbe riferire?
 Per quanto riguarda il costruttore di copia,sempre  secondo il mio libro,
essendo oneroso passare una pila per valore e quindi è  molto meglio inibire
questa
funzionalità e consentire il solo passaggio per riferimento.
Ciao, e grazie per i preziosi consigli!

 funzionalità e consentire il solo passaggio per riferimento.
Quindi ... tutto privato e non implementato.
In alternativa potresti implementarle (correttamente) e sostenere che
essendo private e non utilizzate da nessun membro di fatto sono inibite,
però le hai implementate per far vedere come sarebbero state se fossero
state pubbliche.
Appro: mi è venuto in mente che potrebbe essere interesante una funzione
di "reverse" della pila (nota: ci sono due modi per farlo. Quello più
efficiente richiede il copy operator. Ma ne esiste anche uno, meno
efficiente, che non lo richiede).


 efficiente, che non lo richiede).
Riprende un pň ciň che avevo intenzione di fare, cioč stampare gli el. dal
primo all'ultimo..piů o meno č lo stesso algoritmo..creo una pila inversa
alla precedente memorizzando la testa della pila  nella coda della
pila_reverse e cosi via... logicamente mi converrebbe implementare
l'algoritmo una volta in una funzione per poi riusarlo quando serve
richiamando la funzione, ad esempio in stampa() (come mi hai suggerito tu
del resto!)
Sono sulla strada giusta? :-)
..ma per ora non ci voglio pensare..appena risolverň il problema con i
template(leggi il mio ultimo post: "Problemi con classi template" e
capirai..) mi applicherň di piů...
Ciao.

 Sono sulla strada giusta? :-)
Dipende molto da come implementi la cosa. Nota che questo è uno di quei
casi in cui efficienza e riuso del codice fanno leggermente a cazzotti.


 uno, meno efficiente, che non lo richiede).
il metodo "meno efficiente" e` banale e non ci sono problemi. Ma quale 
sarebbe quello "piu` efficiente"? Non mi viene in mente.
ciao Anto
-- 
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.73, higher than 99% of all previous test takers.
C Language: 3.79, higher than 92% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

 sarebbe quello "piu` efficiente"? Non mi viene in mente.
Ho la sensazione che non hai capito. Prova a scriverlo, il metodo, e
vedrai che non è un problema così banale come sembra. In realtà non è
difficile. Ma il livello di "banalità" dei due casi è praticamente lo
stesso. Solo che in un caso hai bisogno del copy operator.


 stesso. Solo che in un caso hai bisogno del copy operator.
dopo questo messaggio ho la senzazione di non aver capito, ma non ho 
piu` i messaggi vecchi e non posso controllare.
Quando parlate di "copy operator" parlate di quello della classe pila o 
di quello degli oggetti contenuti? Io avevo capito (penso malamente) si 
trattasse di quello della classe pila.
Se invece parlavate del copy operator degli elementi ho sbagliato io, e 
adesso ho anche capito il senso della frase.


 sarebbe quello "piu` efficiente"? Non mi viene in mente.
Ovvero che ti pare banale implementare l'inversione *senza* usare copy
operator (caso meno efficiente) ma non sai come farlo usando il copy
operator (caso più efficiente).
E la cosa mi è suonata alquanto strana! Credo che tu non abbia capito
qualche cosa. Ma cosa lo devi dire tu!


 qualche cosa. Ma cosa lo devi dire tu!
la cosa sembra strana anche a me... Ricapitoliamo: noi abbiamo una 
classe del genere (tralasciando questioni stilistiche e di robustezza):
class Pila {
        static const int max_data = 100;
        int data[max_data];
        int stack_pointer;
public:
        Pila(): stack_pointer(0) { }
        void push(int);
        void pop();
        int top();
        void copy_reverse(Pila&);
};
void Pila::copy_reverse(Pila& dest)
{
        dest.stack_pointer = stack_pointer;
        if (stack_pointer > 0)
                for( int = 0, j = stack_pointer-1; 
                      i < stack_pointer; i++, j-- )
                   dest.data[j] = data[i];
}
Qua non c'e` alcun copy operator e non vedo come farlo in modo piu` 
efficiente. Continuo ad avere l'impressione di non aver capito 
esattamente di cosa stiamo parlando... :-(


 esattamente di cosa stiamo parlando... :-(
Vedi sopra.


Andrea Ferro wrote:
[snip]

Invertire una pila avendo a disposizione l'operatore di copia e' molto 
semplice (ma non so quanto sia effettivamente efficiente, visto che 
implica almeno una copia della pila):
void inverti(Pila & unaPila) {  
        Pila miaPila;
        while( !unaPila.empty() ) {
                miaPila.push( unaPila.top() );
                unaPila.pop()
        }
        unaPila = miaPila;
}
La funzione inverti accede solo ai membri pubblici di Pila e
non ha bisogno di alcuna informazione sulla sua implementazione
(funziona ugualmente sia nel caso dell'array che della lista
linkata).
Nota che questa implementazione comporta 3 * n copie 
e 2 * n creazioni/distruzioni di elementi.
E' possibile evitare la copia finale implementando l'algoritmo
all'interno della classe (e accedendo quindi direttamente agli
elementi)
 
void Pila::reverse() {
   Elem * new_first = 0;
   while( !empty() )
   {
        new_first = new Elem( top() , new_first );
        pop();
   }
   first = new_first;   
}
questo comporta n creazioni/distruzioni/copie.
Avendo pero' accesso all'implementazione della pila e' possibile 
ottenere un'inversione piu' "efficiente" (specialmente se 
gli elementi non sono dei semplici interi ma degli oggetti piu' 
grossi o comunque piu' pesanti da costruire/distruggere/copiare)
void Pila::reverse() {
    Elem *current = first;
    Elem *next = 0;
    while( current ) {
        Elem *tmp = current->next;      
        current->next = next;
        next = current;
        current = tmp;                  
    }       
    first = next;
}
In questo caso i dati non vengono toccati ma soltanto i puntatori
vengono riarrangiati.
A questo punto, disponendo di una reverse() abbastanza efficiente,
si riesce a scrivere un costruttore di copia altrettanto efficiente:
Pila::Pila (const Pila &other)
{
    Elem *p = other.first;
    while(p != 0) {
        push( p->data);
        p = p->next;    
    }
 
    reverse();  
}
Gli elementi vengono creati/copiati una volta sola e poi i puntatori
vengono riarrangiati.
Resta comunque un dubbio: Secondo Andrea, esiste una implementazione
di reverse() piu' efficiente in presenza di operatore di copia (oppure una
implementazione meno efficiente in sua assenza).
Effettivamente implementare la reverse con metodi pubblici e senza 
operatore di copia e' piuttosto complicato.
A me viene in mente questo, non so se esiste un modo migliore:
void reverse_swap(Pila & unaPila, Pila &unAltraPila)
{
        assert( unAltraPila.empty() );
        while(! unaPila.empty() )
        {
                unAltraPila.push( unaPila.top() );
                unaPila.pop();
        }
        // a questo punto unAltraPila contiene gli elementi di unaPila
        // in ordine inverso e unaPila e' vuota.        
}
void reverse(Pila & unaPila)
{
        Pila miaPila1;
        reverse_swap(unaPila , miaPila1); 
        // miaPila1 contiene gli elementi di unaPila invertiti
        // unaPila e' vuota
        Pila miaPila2;
        reverse_swap(miaPila1, miaPila2);
        // miaPila2 e' adesso uguale a unaPila com'era all'inizio
        reverse_swap(miaPila2, unaPila);        
        // finalmente, unaPila contiene gli elementi originali invertiti
}
Ma in realta' questa funzione "copia" una pila su un altra chiamando due 
volte la reverse_swap()
Saluti,
Fabio

 volte la reverse_swap()
Era esattamente il meccanismo che avevo in mente io per implementare la
reverse accedendo solo ai metodi pubblici della pila e senza fare uso
del copy operator (o del copy constructor, ovviamente).


 stare tutti i "controlli":
Dato che per farlo dobbiamo per forza usare uno stack usiamo quello che 
stiamo realizzando:
void Pila::reverse()
{
  Pila tmp;
  while( !empty() ) {
    tmp.push(top());
    pop();
  }
  std::swap(first, tmp.first);
}
 
Immagino che ci siano dei modi per evitare di deallocare/riallocare ogni 
elemento, ma oggi sono particolarmente fuso e non riesco ad arrivarci 
:-(.
Cmq, continuo a non capire dove potrebbe essere utile il copy operator.


 Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it
--


 solo metodi pubblici. 
infatti mi era venuto il dubbio, pero` per pigrizia ho optato per la 
soluzione facile ;-). Cmq ho visto il post di Fabio e (finalmente ;-) ho 
capito cosa volevi dire.
