[C++] Creare template nel Heap della memoria

[Emalele1688]

Salve a tutti, sono nuovo in questa sezione del forum;
Studio Ingegneria Informatica a Roma, programmo in C/C++ da molti anni ormai, e mi sto inbattendo ora nelle template (cosa che fin'ora ho fatto solo in Java).

Arrivo al dunque:

Devo creare, per scopi didattici, una lista collegata, del tutto simile alle std::list; Poi successivamente la dovrò utilizzare in una struttura ad albero, ma questo poco importa adesso!
Di liste ne ho create tantissime in C++ e Java, ma in C++ non ho mai usato i template.

Sono riusciuto fino adesso ad allocare l'oggetto con il template nello stack della memoria;
Per intenderci ho fatto questo:

LinkedList<int> SCL;

Dunque senza uso di puntatori e memoria dinamica.

Se volessi ora istanziare l'oggetto SCL nel Heap della memoria?
Dunque se vorrei fare questo:

LinkedList<int> *SCL = new LinkedList()

è una cosa fattibile?

Scrivo un codice di prova, che chiaramente non compila, e non c'entra nulla con le strutture collegate, per farvi capire cosa dovrei esattamente capire se si può fare:

template <class V>
class temp
{
public:
  temp()
  {}
  
  void set(V& v)
  {
    dt = v;
  }
  
  V dt;
};

int main()
{
  temp<int>* S = new temp();
  S->set(3);
  std::cout << S->dt << std::endl; //Stamperà 3
  
  return 0;
}

Premetto che, salvo errori, in questo main dovrebbe compilare:

int main()
{
  temp<int> S;
  S.set(3);
  std::cout << S.dt << std::endl; //Stamperà 3
  
  return 0;
}

[tomminno]

Il tuo problema è sicuramente dovuto al fatto che dichiari male l'allocazione, ma il compilatore non ti dice niente?

LinkedList<int> *SCL = new LinkedList<int>();

Non so come hai implementato la tua LinkedList ma seguendo l'esempio della libreria standard dovrebbe essere la tua classe ad allocare nell'heap gli elementi, quindi non dovresti avere la necessità di allocare dinamicamente il contenitore.

Io comunque eviterei l'utilizzo dei puntatori diretti in favore di shared_ptr (se lavori con un compilatore recente) oppure il deprecato auto_ptr.

[Emalele1688]

Grazie per la tua risposta Ora proverò subito la tua soluzione, il compilatore mi dava errore sui template, ma spesso gli errori di gcc, letti dal terminale non sono chiari, sicuramente dovrei leggermi più documentazioni sul compilatore gcc

Per quanto riguarda shared_ptr, vorrei evitare di usare smart pointer per adesso, poichè lo scopo del programma è totalmente didattico, e voglio imparare prima a gestire bene la memoria, e poi in programmi seri farò anche uso delle tecniche RAII.

Io i nodi della lista li ho allocati dinamicamente, ti mostro la funzione add, che ancora non ho provato:

void LinkedList::add(V& v)
{
  //head è il puntatore alla testa della coda FIFO (attributo privato della classe LinkedList, di tipo Node<V>)
  if(head == 0)
  {
    head = new Node<V>(v);
    ins = head; //ins è un puntatore di tipo LinkedList che uso solo per l'inserimento in coda
    size++; //Grandezza della coda
    return; //Il primo elemento è stato inserito, ritorna
  }
  
  ins->setNext(new Node<V>(v)); //setNext è un metodo della classe Node<V>, inserisce un nuovo nodo con elemento v
  ins = ins->next;
  size++;
}

Chiaramente le remove le gestisco con il delete, prestando attenzione su quello che vado a cancellare ...

Se la lista non la alloco dinamicamente (dunque avrei Node(v) e non new Node<V>(v)), non verrà allocata nel Heap giuso? E dove verrebbe allocata?
Si avrebberò vantaggi? O per lo meno sarebbe più giusto?

[tomminno]

Originariamente inviato da Emalele1688

Se la lista non la alloco dinamicamente (dunque avrei Node(v) e non new Node<V>(v)), non verrà allocata nel Heap giuso? E dove verrebbe allocata?
Si avrebberò vantaggi? O per lo meno sarebbe più giusto?

La lista la puoi allocare benissimo sullo stack, dato che i suoi elementi sono allocati nell'heap. E' quello che avviene anche con i contenitori standard del C++.

[Emalele1688]

Però non capisco una cosa:
Se la lista la alloco nello stack della classe LinkedList, dopo, quando eseguo una cancellazione di un nodo della lista, quel nodo rimane nella memoria finchè non eseguo una delete della classe LinkedList? Ed io non ho più l'oggetto del nodo cancellato, quindi non creo dei memory leak?

[tomminno]

Originariamente inviato da Emalele1688

Però non capisco una cosa:
Se la lista la alloco nello stack della classe LinkedList, dopo, quando eseguo una cancellazione di un nodo della lista, quel nodo rimane nella memoria finchè non eseguo una delete della classe LinkedList? Ed io non ho più l'oggetto del nodo cancellato, quindi non creo dei memory leak?

No il nodo rimane in memoria fino a che non ne esegui la delete dall'interno della classe LinkedList, che è l'unica ad averne un "riferimento".
Se tu allocassi LinkedList nell'heap ma non eseguissi la delete dei singoli nodi allocati sul distruttore di LinkedList avresti dei memory leak, l'operazione di delete non è ricorsiva.

[Emalele1688]

Infatti ho implementato il distruttore di LinkedList che esegue un ciclo per tutta la grandezza della lista, invocando la delete di ogni nodo ...
Ok allora per qui ci sono, è ok
Due chiarimenti sui template sperando di non uscire fuori dalla discussione del forum:

1 - Definendo le funzioni fuori dalla classe, in un file .cpp, il compilatore mi restituisce degli errori; Per esempio io il metodo remove (Rimuove all'indice 'i' e ritorna l'elemento a quella posizione) lo dichiaro cosi:

V LinkedList::remove(int index)
{ ... }

C'è qualcosa che sbaglio?

2 - Ho implementato il metodo get, che mi restituisce l'elemento V all'indice 'i', quando nel main faccio:

std::cout << SCL.get(i) << std::endl; //SCL è l'oggetto LinkedList (nello stack), 'i' il contatore

mi ritorna il seguente errore:

LinkedList.h: In member function ‘V LinkedList<V>::get(int) [with V=int]’:
main.cpp:19:27: instantiated from here
LinkedList.h:83:7: error: return-statement with no value, in function returning ‘int’

Dove sbaglio?

[tuccio`]

Originariamente inviato da Emalele1688

Infatti ho implementato il distruttore di LinkedList che esegue un ciclo per tutta la grandezza della lista, invocando la delete di ogni nodo ...
Ok allora per qui ci sono, è ok
Due chiarimenti sui template sperando di non uscire fuori dalla discussione del forum:

1 - Definendo le funzioni fuori dalla classe, in un file .cpp, il compilatore mi restituisce degli errori; Per esempio io il metodo remove (Rimuove all'indice 'i' e ritorna l'elemento a quella posizione) lo dichiaro cosi:

V LinkedList::remove(int index)
{ ... }

C'è qualcosa che sbaglio?

un paio di cose, intanto perché dovresti scrivere

template <typename V>
V LinkedList<V>::remove(int index)
{
  ...
}

e poi per questo: http://www.hwupgrade.it/forum/showthread.php?t=2334593

sulla seconda domanda non saprei dirti

[Emalele1688]

Cioè vuoi dire che la definizione dei metodi che fanno uso di template in C++ deve stare all'interno della classe nel file header? Laddove li dichiaro?

[tomminno]

Originariamente inviato da Emalele1688

Cioè vuoi dire che la definizione dei metodi che fanno uso di template in C++ deve stare all'interno della classe nel file header? Laddove li dichiaro?

Si, il codice delle classi template deve stare tutto nell'header.

[Emalele1688]

Non riesco a capire dove è che sbaglio ...
Chiamo bene la funzione get, che ritorna l'elemento di tipo V deciso a runtime, nel programma sottostante?

int main(int *s)
{
  LinkedList<int> SCL;
  SCL.add(5);
  SCL.add(4);
  
  std::cout << SCL.get(0) << std::endl;

  return 0;
}

La funzione get, è all'interno della classe LinkedList:

  V get(int index)
  {
    if(index >= size)
      return;
    
    Node<V> *tmp = head;
    while(tmp != 0 && index != 0)
    {
      tmp = tmp->next;
      index--;
    }
    
    return tmp->elem;
  }

Dovrebbe stamparmi 5, ma mi da un errore;
Chiaramente se commento la riga
std::cout << SCL.get(0) << std::endl;
il programma compila ...
Sbaglio nel main o nella dichiarazione del metodo get?

[Emalele1688]

RISOLTO!!! Sono un idiota Non avevo visto che sul metodo get la prima condizione tornava un void

[Emalele1688]

Scusa qualcuno mi potrebbe aiutare a capire deve è il problema?

Ho una classe template, che ha la funzione di classe padre:

template<class V>
class Compare
{
public:
  Compare(){}
  
  virtual short int compare(V a, V b) = 0;
};

Qui ho una implementazione della sua classe figlio:

#include "Compare.h"

template<class V>
class MyCompare : public Compare<V>
{
public:
  MyCompare()<V>
  {}
  
  int compare(V a, V b)
  {
    if(a < b)
      return -1;
    if(a > b)
      return 1;
    return 0;
  }
      
};

Se nel main metto:

Compare<int>* a = new MyCompare<int>();

o anche:

MyCompare<int> a;

NON COMPILA!!!

Qualcuno sa dirmi se ho sbagliato la gestione dei template??

[tuccio`]

forse perché hai sbagliato nel ridefinire la funzione compare che è pure virtual, una ritorna short int, l'altra int

comunque, non puoi usare less se devi ordinare qualcosa?

[Emalele1688]

Si è short int nel programma, ovvio .... Ho sbagliato a scriverlo nel post, comunque è short int.
Ma la funzione compare, nella classe padre deve essere virtual giusto? Io ho sempre lavorato così con l'ereditarietà;
I metodi che devo ridefinire in una sottoclasse devono essere virtuali, da quello che so .... Forse so male?

Comunque la compare la sto usando per ordinare un albero binario (una struttura dati Heap binaria).
Volevo evitare di usare le STL, che tra l'altro non conosco ancora bene ...
Ma less che fa esattamente?