[C++] Lista doppiamente linkata di oggetti senza duplicati

[GrG]

Salve,

Come da titolo, dovrei fare (a scopo didattico) un template di una lista doppiamente linkata evitando la presenza di duplicati... (in particolare mi servirà poi inserire nella lista degli oggetti)

Il fatto è che sinceramente non ho le idee chiare su come fare e quindi volevo chiedervi qualche dritta

Il mio metodo add della lista aggiunge un nuovo nodo in testa inserendo nel campo che contiene il dato una copia dell'oggetto passato come parametro.

Questo lo realizzo così:

void add(T *obj) {
    Node *n = new Node;
    T *copy = new T(*obj);
    n->info = copy;
    [...]

e il mio nodo è definito con una struct:

struct Node {
    T* data;
    Node *next;
    Node *prev;
};
Node *head;

la domanda è, come faccio a vedere se la lista già contiene l'oggetto?

Il fatto è che è una lista template, quindi l'unica cosa su cui mi posso basare (o che almeno mi è venuta in mente) è guardare l'indirizzo di memoria dell'oggetto, nel metodo add quando gli arriva l'oggetto se lo copia e lo inserisce, la copia però ha un indirizzo diverso dall'originale, quindi se riaggiungo lo stesso oggetto, anche se mi scorro la lista guardando se l'indirizzo di memoria di quell'oggetto è già puntato il controllo sarà sempre false, poichè ogni volta creo copie con indirizzi diversi..

L'unica soluzione (piuttosto bruttina) che mi è venuta in mente è aggiungere un altro campo al nodo che mi memorizzi l'indirizzo di memoria dell'oggetto originale da cui ho fatto la copia e poi quando richiamo l'add andare a cercare l'indirizzo dell'oggetto in quel campo aggiuntivo

boh, qualcosa mi sfugge, forse c'è un metodo migliore, mi potreste dare qualche consiglio? (Considerando che non posso usare le liste/set/mappe delle librerie standard e che non posso dire che il generico oggetto T deve avere necessariamente metodi tipo equals in modo tale da sfruttare tale metodo per verificare l'esistenza di duplicati)

p.s. L'istruzione T *copy = new T(*obj); considerando che l'oggetto *obj non ha un costruttore copia mi fa una shallow copy?

Grazie in anticipo

[MItaly]

Dipende da qual'è la tua definizione di uguaglianza. Se per te due oggetti sono uguali se al momento dell'inserimento ricevi lo stesso puntatore, non vedo molte alternative al metodo che hai descritto; ma in genere si intende che due oggetti a e b sono uguali quando a==b.
In tal caso, ti basterà scorrere la lista e confrontare gli oggetti uno ad uno usando l'operatore == (sull'oggetto, non sul puntatore - if(*(n->info)==*obj) ...). Questo funziona senza dover fare nient'altro sui tipi primitivi, mentre per le classi custom si richiede che sia ridefinito l'operatore ==.

Nota comunque che la lista non è un buon contenitore se non vuoi avere duplicati - l'inserimento diventa O(n) quando potrebbe essere O(1) (se in testa o comunque dopo un elemento che hai già).
Puoi migliorare un po' le performance mantenendo ordinata la lista, ma il caso medio resta O(n).

Per questo motivo per avere container senza duplicati normalmente si usano le hashtable (non ordinate) o gli alberi RB (ordinati).

p.s. L'istruzione T *copy = new T(*obj); considerando che l'oggetto *obj non ha un costruttore copia mi fa una shallow copy?

Sì e no; il costruttore di copia predefinito si limita a copiare i singoli campi, senza fare null'altro di particolare, per cui se hai dei puntatori questi vengono semplicemente copiati senza fare altro; d'altra parte, se i campi in questione sono oggetti - e non puntatori - verrà richiamato a sua volta il loro costruttore di copie, per cui potenzialmente può essere una deep copy.

[GrG]

grazie mille! Non ci avevo proprio pensato a ridefinire l'operatore ==