C++ funzioni virtuali non pure

[pietrol83]

ciao a tutti, sempre sulle liste, poichè creando la classe lista con le funzioni virtuali pure ho avuto problemi di compilazione, ho deciso di renderle non pure. diciamo che va un po' meglio però mi da un errore sulle funzioni virtuali. posto la classe lista (con la relativa classe derivata) e il test della lista.

lista.h

#include <iostream>
#include <stdlib.h>

using namespace std;

template<class posizione, class tipoelem>
class lista
{
   public:
      virtual void crealista();
      virtual bool listavuota();
      virtual posizione primolista();
      virtual bool finelista(posizione);
      virtual posizione succlista(posizione);
      virtual posizione predlista(posizione);
      virtual tipoelem leggilista(posizione);
      virtual void scrivilista(posizione, tipoelem);
      virtual void inslista(posizione, tipoelem);
      virtual void canclista(posizione);
      
      void stampalista();
      void fondiordinate(lista &, lista &);
      void epurazione();
      void naturalmergesort();
   private:
      void distribuisci(lista &, lista &);
      void copiacatena(posizione, lista &, posizione, lista &);
      void copia(posizione, lista &, posizione, lista &, bool *);
      void merge(lista &, lista &, lista &, int *);
      void fondicatena(posizione, lista &, posizione, lista &, posizione, lista &);
      
};

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::stampalista()
{
   posizione p = primolista();
   while(!finelista(p))
   {
      cout << leggilista(p) << "\n";
      p = succlista(p);
   }
   cout << "\n";
}
   

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::fondiordinate(lista<posizione, tipoelem> &A, lista<posizione, tipoelem> &B)
{
   posizione pa = A.primolista();
   posizione pb = B.primolista();
   posizione pc = primolista();
   
   tipoelem elem1 = A.leggilista(pa);
   tipoelem elem2 = B.leggilista(pb);
   while(!A.finelista(pa) && !B.finelista(pb))
   {
      if(elem1 <= elem2)
      {
         inslista(pc, elem1);
         pa = A.succlista(pa);
      }
      else
      {
         inslista(pc, elem2);
         pb = B.succlista(pb);
      }
      elem1 = A.leggilista(pa);
      elem2 = B.leggilista(pb);
   }
   while(!A.finelista(pa))
   {
      inslista(pc, elem1);
      pa = A.succlista(pa);
      elem1 = A.leggilista(pa);
   }
   while(!B.finelista(pb))
   {
      inslista(pc, elem2);
      pb = B.succlista(pb);
      elem2 = B.leggilista(pb);
   }
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::epurazione()
{
   posizione p = primolista();
   posizione q;
   posizione t;
   while(!finelista(p))
   {
      q = succlista(p);
      while(!finelista(q))
      {
         if(leggilista(p) == leggilista(q))
         {
            t = succlista(q);
            canclista(q);
            q = t;
         }
         else
            q = succlista(q);
      }
      p = succlista(p);
   }
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::naturalmergesort()
{
   int numerocatene;
   lista<posizione, tipoelem> A, B, L;
   do
   {
      A.crealista();
      B.crealista();
      distribuisci(A, B);
      numerocatene = 0;
      crealista();
      merge(A, B, L, &numerocatene);
   }while(numerocatene != 1);
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::distribuisci(lista<posizione, tipoelem> &A, lista<posizione, tipoelem> &B)
{
   posizione p = primolista();
   posizione pa = A.primolista();
   posizione pb = B.primolista();
   do
   {
      copiacatena(p, *this, pa, A);
      if(!finelista(p))
         copiacatena(p, *this, pb, B);
   }while(!finelista(p));
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::copiacatena(posizione p, lista<posizione, tipoelem> &L, posizione pa, lista<posizione, tipoelem> &A)
{
   bool finecatena = false;
   do
      copia(p, L, pa, A, &finecatena);
   while(!finecatena);
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::copia(posizione p, lista<posizione, tipoelem> &L, posizione pa, lista<posizione, tipoelem> &A, bool *finecatena)
{
   bool esito = *finecatena;
   finecatena = &esito;
   tipoelem elemento = leggilista(p);
   A.inslista(pa, elemento);
   p = succlista(p);
   pa = succlista(pa);
   if(finelista(p))
      esito = true;
   else
      esito = (elemento > leggilista(p));
   finecatena = &esito;
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::merge(lista<posizione, tipoelem> &A, lista<posizione, tipoelem> &B, lista<posizione, tipoelem> &L, int *numcatene)
{
   posizione p = primolista();
   posizione pa = A.primolista();
   posizione pb = B.primolista();
   
   while(!A.finelista(pa) && !B.finelista(pb))
   {
      fondicatena(pa, A, pb, B, p, L);
      numcatene++;
   }
   while(!A.finelista(pa))
   {
      copiacatena(pa, A, p, L);
      numcatene++;
   }
   while(!B.finelista(pb))
   {
      copiacatena(pb, B, p, L);
      numcatene++;
   }
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::fondicatena(posizione pa, lista<posizione, tipoelem> &A, posizione pb, lista<posizione, tipoelem> &B, posizione p, lista<posizione, tipoelem> &L)
{
   bool finecatena = false;
   do
   {
      if(A.leggilista(pa) < B.leggilista(pb))
      {
         copia(pa, A, p, *this, &finecatena);
         if(finecatena)
            copiacatena(pb, B, p, *this);
      }
      else
      {
         copia(pb, B, p, *this, &finecatena);
         if(finecatena)
            copiacatena(pa, A, p, *this);
      }
   }while(finecatena);
}

listap.h

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include "lista.h"
#include "nodop.h"

using namespace std;

template<class tipoelem>
class listap : public lista<nodop<tipoelem> *, tipoelem>
{
   public:
      typedef nodop<tipoelem> *posizione;
      listap();                             //costruttore di default
      void crealista();                     //crea la lista vuota
      bool listavuota();                    //stabilisce se la lista è vuota o meno
      posizione primolista();               //restituisce la posizione del primo elemento della lista
      bool finelista(posizione);            //stabilisce se il nodo è l'ultimo della lista
      tipoelem leggilista(posizione);       //restituisce l'elemento della posizione specificata
      posizione succlista(posizione);       //restituisce la posizione del nodo successivo 
      posizione predlista(posizione);       //restituisce la posizione del nodo precedente
      void scrivilista(posizione, tipoelem);//scrive l'elemtno nel nodo specificato dalla posizione
      void inslista(posizione, tipoelem); //inserisce un nodo e scrive l'elemento nella posizione specificata 
      void canclista(posizione);          //elimina il nodo nella posizione specificata
   private:
      nodop<tipoelem> cella;                 //nodo della lista (nodo sentinella)
};

template<class tipoelem>
listap<tipoelem>::listap()
{
   crealista();                             //il costruttore invoca il metodo crealista
}

template<class tipoelem>
void listap<tipoelem>::crealista()
{
   cella.setprec(&cella);
   cella.setsuc(&cella);
   cella.setelem(0);
}

template<class tipoelem>
bool listap<tipoelem>::listavuota()
{
   return((cella.getprec() == &cella) && (cella.getsuc() == &cella));
}

template<class tipoelem>
typename listap<tipoelem>::posizione listap<tipoelem>::primolista()
{
   return(cella.getsuc());
}

template<class tipoelem>
bool listap<tipoelem>::finelista(typename listap<tipoelem>::posizione pos)
{
   return(pos == &cella);
}

template<class tipoelem>
tipoelem listap<tipoelem>::leggilista(typename listap<tipoelem>::posizione pos)
{
   return(pos->getelem());
}

template<class tipoelem>
void listap<tipoelem>::scrivilista(typename listap<tipoelem>::posizione pos, tipoelem elem)
{
   pos->setelem(elem);
}

template<class tipoelem>
typename listap<tipoelem>::posizione listap<tipoelem>::succlista(typename listap<tipoelem>::posizione pos)
{
   return(pos->getsuc());
}

template<class tipoelem>
typename listap<tipoelem>::posizione listap<tipoelem>::predlista(typename listap<tipoelem>::posizione pos)
{
   return(pos->getprec());
}

template<class tipoelem>
void listap<tipoelem>::inslista(typename listap<tipoelem>::posizione pos, tipoelem elem)
{
   posizione temp = new nodop<tipoelem>;
   
   temp->setprec(pos->getprec());
   temp->setsuc(pos);
   (pos->getprec())->setsuc(temp);
   pos->setprec(temp);
   temp->setelem(elem);
   pos = temp;
}

template<class tipoelem>
void listap<tipoelem>::canclista(typename listap<tipoelem>::posizione pos)
{
   posizione temp = pos;
   (pos->getsuc())->setprec(pos->getprec());
   (pos->getprec())->setsuc(pos->getsuc());
   pos = pos->getsuc();
   delete temp;
}

testlista.cpp

#include "listap.h"
#include <iostream>
#include <stdlib.h>

using namespace std;

int main()
{
   listap<int> list, list2, list3, list4;
   listap<int>::posizione pos = list.primolista();
   listap<int>::posizione pos2 = list2.primolista();
   listap<int>::posizione pos4 = list4.primolista();
   int k;
   
   for(int i = 0; i < 10; i++)
   {
      list.inslista(pos, (100 - (i * 10)));
      pos = list.primolista();
   }
   
   for(int i = 0; i < 10; i++)
   {
      list2.inslista(pos2, (50 - (i * 5)));
      pos2 = list2.primolista();
   }

   list.stampalista();
   list2.stampalista();
   
   cout << "\n\n";
      
   list3.fondiordinate(list, list2);
   list3.stampalista();
   cout << "\n\n";
   list3.epurazione();
   list3.stampalista();
   
   cout << "\n\n";
   for(int i = 0; i < 10; i++)
   {
      cin >> k;
      list4.inslista(pos4, k);
      pos2 = list2.primolista();
   }
   list4.stampalista();
   list4.naturalmergesort();
   cout << "\n\n";
   list4.stampalista();
   
   system("pause");
   return 0;
}

l'errore è il seguente:

[Linker error] undefined reference to `lista<nodop<int>*, int>::scrivilista(nodop<int>*, int)'


in pratica mi dà una lista di quell'errore per ogni metodo virtuale. cosa c'è che non va?
eppure i metodi virtuali vengono implementati nella classe derivata!!!

[shodan]

Originariamente inviato da pietrol83
eppure i metodi virtuali vengono implementati nella classe derivata!!!

Se i metodi di lista non sono virtuali puri sei obbligato a fornirne comunque un'implementazione. Questo perché non è obbligatorio ridefinire tale funzione in una classe derivata, come succederebbe se il metodo fosse virtuale puro.

In pratica togliendo i metodi virtuali puri non freghi il compilatore.

[pietrol83]

ma io inizialmente ho provato con i metodi virtuali puri però poi non mi è stato possibile implementare i metodi private di cui si serve il metodo naturalmergesort() perchè non è possibile istanziare oggietti della classe lista, il che è normale perchè una classe astratta non può essere istanziata. come posso risolvere il problema?

[pietrol83]

ora ho provato a rendere i metodi di lista come virtuali puri e a utilizzare i riferimenti a lista anzichè istanziare gli oggetti lista. il test viene compilato ma va in crash.

ho apportato le seguenti modifiche nel file lista.h (le modifiche sono segnate in rosso).

lista.h

#include <iostream>
#include <stdlib.h>

using namespace std;

template<class posizione, class tipoelem>
class lista
{
   public:
      virtual void crealista() = 0;
      virtual bool listavuota() = 0;
      virtual posizione primolista() = 0;
      virtual bool finelista(posizione) = 0;
      virtual posizione succlista(posizione) = 0;
      virtual posizione predlista(posizione) = 0;
      virtual tipoelem leggilista(posizione) = 0;
      virtual void scrivilista(posizione, tipoelem) = 0;
      virtual void inslista(posizione, tipoelem) = 0;
      virtual void canclista(posizione) = 0;
      
      void stampalista();
      void fondiordinate(lista &, lista &);
      void epurazione();
      void naturalmergesort();
   private:
      void distribuisci(lista &, lista &);
      void copiacatena(posizione, lista &, posizione, lista &);
      void copia(posizione, lista &, posizione, lista &, bool *);
      void merge(lista &, lista &, lista &, int *);
      void fondicatena(posizione, lista &, posizione, lista &, posizione, lista &);
      
};

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::stampalista()
{
   posizione p = primolista();
   while(!finelista(p))
   {
      cout << leggilista(p) << "\n";
      p = succlista(p);
   }
   cout << "\n";
}
   

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::fondiordinate(lista<posizione, tipoelem> &A, lista<posizione, tipoelem> &B)
{
   posizione pa = A.primolista();
   posizione pb = B.primolista();
   posizione pc = primolista();
   
   tipoelem elem1 = A.leggilista(pa);
   tipoelem elem2 = B.leggilista(pb);
   while(!A.finelista(pa) && !B.finelista(pb))
   {
      if(elem1 <= elem2)
      {
         inslista(pc, elem1);
         pa = A.succlista(pa);
      }
      else
      {
         inslista(pc, elem2);
         pb = B.succlista(pb);
      }
      elem1 = A.leggilista(pa);
      elem2 = B.leggilista(pb);
   }
   while(!A.finelista(pa))
   {
      inslista(pc, elem1);
      pa = A.succlista(pa);
      elem1 = A.leggilista(pa);
   }
   while(!B.finelista(pb))
   {
      inslista(pc, elem2);
      pb = B.succlista(pb);
      elem2 = B.leggilista(pb);
   }
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::epurazione()
{
   posizione p = primolista();
   posizione q;
   posizione t;
   while(!finelista(p))
   {
      q = succlista(p);
      while(!finelista(q))
      {
         if(leggilista(p) == leggilista(q))
         {
            t = succlista(q);
            canclista(q);
            q = t;
         }
         else
            q = succlista(q);
      }
      p = succlista(p);
   }
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::naturalmergesort()
{
   int numerocatene;
   lista<posizione, tipoelem> *A, *B, *L;
   do
   {
      A->crealista();
      B->crealista();
      distribuisci(*A, *B);
      numerocatene = 0;
      crealista();
      merge(*A, *B, *L, &numerocatene);
   }while(numerocatene != 1);
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::distribuisci(lista<posizione, tipoelem> &A, lista<posizione, tipoelem> &B)
{
   posizione p = primolista();
   posizione pa = A.primolista();
   posizione pb = B.primolista();
   do
   {
      copiacatena(p, *this, pa, A);
      if(!finelista(p))
         copiacatena(p, *this, pb, B);
   }while(!finelista(p));
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::copiacatena(posizione p, lista<posizione, tipoelem> &L, posizione pa, lista<posizione, tipoelem> &A)
{
   bool finecatena = false;
   do
      copia(p, L, pa, A, &finecatena);
   while(!finecatena);
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::copia(posizione p, lista<posizione, tipoelem> &L, posizione pa, lista<posizione, tipoelem> &A, bool *finecatena)
{
   bool esito = *finecatena;
   finecatena = &esito;
   tipoelem elemento = leggilista(p);
   A.inslista(pa, elemento);
   p = succlista(p);
   pa = succlista(pa);
   if(finelista(p))
      esito = true;
   else
      esito = (elemento > leggilista(p));
   finecatena = &esito;
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::merge(lista<posizione, tipoelem> &A, lista<posizione, tipoelem> &B, lista<posizione, tipoelem> &L, int *numcatene)
{
   posizione p = primolista();
   posizione pa = A.primolista();
   posizione pb = B.primolista();
   
   while(!A.finelista(pa) && !B.finelista(pb))
   {
      fondicatena(pa, A, pb, B, p, L);
      numcatene++;
   }
   while(!A.finelista(pa))
   {
      copiacatena(pa, A, p, L);
      numcatene++;
   }
   while(!B.finelista(pb))
   {
      copiacatena(pb, B, p, L);
      numcatene++;
   }
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::fondicatena(posizione pa, lista<posizione, tipoelem> &A, posizione pb, lista<posizione, tipoelem> &B, posizione p, lista<posizione, tipoelem> &L)
{
   bool finecatena = false;
   do
   {
      if(A.leggilista(pa) < B.leggilista(pb))
      {
         copia(pa, A, p, *this, &finecatena);
         if(finecatena)
            copiacatena(pb, B, p, *this);
      }
      else
      {
         copia(pb, B, p, *this, &finecatena);
         if(finecatena)
            copiacatena(pa, A, p, *this);
      }
   }while(finecatena);
}

[shodan]

Originariamente inviato da pietrol83
...però poi non mi è stato possibile implementare i metodi private di cui si serve il metodo naturalmergesort() perchè non è possibile istanziare oggetti della classe lista...

Basta cambiare modificatore: protected invece di private. Non vedo il problema.

Per le righe in rosso del metodo mergesort.
Ti sei accorto di usare pointer che puntano alla luna invece che a una istanza dinamica di lista?
(Che comunque non puoi avere visto che lista ha metodi puri?)

Cambiando il modificatore d'accesso e derivando la classe come avevi fatto prima avrai:

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::naturalmergesort()
{
   int numerocatene;
   lista<posizione, tipoelem> *A, *B, *L;

   A = new listap<quel che è> ;
   B = new listap<quel che è> ;
   L = new listap<quel che è> ;

   do
   {
      A->crealista();
      B->crealista();
      distribuisci(*A, *B);
      numerocatene = 0;
      crealista();
      merge(*A, *B, *L, &numerocatene);
   }while(numerocatene != 1);

   // eventuali delete di A, B, L

}

[pietrol83]

non posso mettere new listap<quel che è> perchè dalla classe base ereditano tre tipi di lista: con puntatori, vettori e cursori.
come posso fare??

per quanto riguarda i pointer, non ho capito a cosa ti riferisci...

[oregon]

Originariamente inviato da pietrol83
per quanto riguarda i pointer, non ho capito a cosa ti riferisci...

Al fatto che usi dei puntatori come

lista<posizione, tipoelem> *A, *B, *L;

direttamente così

A->crealista();

senza avere fatto la new per istanziare l'oggetto.

[pietrol83]

ho fatto:
A = new lista<posizione, tipoelem>
e la stessa cosa per B e L. questo è l'errore:

114 C:\Dev-Cpp\esercizi\Lista\lista.h cannot allocate an object of type `lista<nodop<int>*, int>'

mi è stato consigliato di fare:
A = new listap<quello che è> ma nn posso farlo poichè dalla classe lista.h ereditano altri due tipi di liste, con vettore e con cursori, le quali ereditano anche il metodo naturalmergesort.

[shodan]

Originariamente inviato da pietrol83
ho fatto:
A = new lista<posizione, tipoelem>
e la stessa cosa per B e L. questo è l'errore:

114 C:\Dev-Cpp\esercizi\Lista\lista.h cannot allocate an object of type `lista<nodop<int>*, int>'

Come annunciato prima:

(Che comunque non puoi avere visto che lista ha metodi puri.)

mi è stato consigliato di fare:

Non è un consiglio: è un obbligo del compilatore.

le quali ereditano anche il metodo naturalmergesort.

Se non devi lavorare con la lista corrente sarebbe meglio che naturalMergeSort non fosse una funzione membro (imho). In ogni caso dovresti cambiare prototipo in:

::naturalmergesort(lista<posizione, tipoelem>& A, lista<posizione, tipoelem>& B, lista<posizione, tipoelem>& L)

dove A,B,L saranno classi concrete (derivate da lista).
Invocando solo i metodi polimorfici di quelle classi all'interno di naturalMergeSort(), non importerà più come sia implementata la loro struttura dati interna (cursori, vettori, altro), ma solo l'interfaccia esportata.

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::naturalmergesort(
    lista<posizione, tipoelem>& A,
    lista<posizione, tipoelem>& B,
    lista<posizione, tipoelem>& L,
) {
   int numerocatene;
   do
   {
      A.crealista();
      B.crealista();
      distribuisci(A, B);
      numerocatene = 0;
      crealista();
      merge(A, B, L, &numerocatene);
   }while(numerocatene != 1);
}

[pietrol83]

ok proverò a fare così, ma in questo modo devo istanziare due lista in più nel main. A e B dovrebbero servire per raccogliere le catene di L.