[C++] Classe Lista Concatenata

[Super Squirrel]

Per l'ennesima volta mi sono trovato nella condizione di dover dimensionare dinamicamente un array. Più volte mi è stato suggerito di ricorrere alla classe vector, ma non sapendo bene come funzionasse ho sempre preferito utilizzare la sola allocazione dinamica per risparmiare memoria.
Finalmente mi sono deciso ad affrontare l'argomento delle liste concatenate e ho provato ad implementare una classe.

#ifndef LISTA_H_INCLUDED
#define LISTA_H_INCLUDED

namespace mino
{
template <typename T>
class lista
{
private:
    struct nodo
    {
        T dato;
        nodo *next;
    };
    nodo *testa;
    unsigned int dim;
public:
    lista(const unsigned int& = 0, const T& = 0);
    lista(const lista&);
    ~lista();
    void add_testa(const T& = 0);
    void add_coda (const T& = 0);
    void add_(const unsigned int&, const T& = 0);
    void remove_testa();
    void remove_coda ();
    void remove_(const unsigned int&);
    void ridimensiona(const unsigned int&);
    unsigned int get_dim();
    bool trova(const T&);
    lista& operator =(const lista&);
    T& operator[](const unsigned int&);
};

template <typename T>
lista<T>::lista(const unsigned int& _dim, const T& _dato)
{
    testa = nullptr;
    dim = 0;
    for(unsigned int i = 0; i < _dim; i++)
    {
        add_testa(_dato);
    }
}

template <typename T>
lista<T>::lista(const lista& l)
{
    testa = nullptr;
    dim = 0;
    nodo *iteratore = l.testa;
    while(iteratore != nullptr)
    {
        add_testa(iteratore->dato);
        iteratore = iteratore->next;
    }
}

template <typename T>
lista<T>::~lista()
{
    for(unsigned int i = 0; i < dim; i++)
    {
        remove_testa();
    }
}

template <typename T>
void lista<T>::add_testa(const T& _dato)
{
    nodo *nuovo = new nodo;
    nuovo->next = testa;
    nuovo->dato = _dato;
    testa = nuovo;
    ++dim;
}

template <typename T>
void lista<T>::add_coda(const T& _dato)
{
    if(dim == 0)
    {
        add_testa(_dato);
    }
    else
    {
        nodo *iteratore = testa;
        while(iteratore->next != nullptr)
        {
            iteratore = iteratore->next;
        }
        nodo *nuovo = new nodo;
        nuovo->next = nullptr;
        nuovo->dato = _dato;
        iteratore->next = nuovo;
        ++dim;
    }
}

template <typename T>
void lista<T>::add_(const unsigned int& indice, const T& _dato)
{
    if(indice <= dim)
    {
        if(indice == 0)
        {
            add_testa(_dato);
        }
        else if(indice == dim)
        {
            add_coda(_dato);
        }
        else
        {
            nodo *iteratore = testa;
            for(unsigned int i = 0; i < indice - 1; i++)
            {
                iteratore = iteratore->next;
            }
            nodo *nuovo = new nodo;
            nuovo->next = iteratore->next;
            nuovo->dato = _dato;
            iteratore->next = nuovo;
            ++dim;
        }
    }
}

template <typename T>
void lista<T>::remove_testa()
{
    if(dim != 0)
    {
        if(dim == 1)
        {
            delete testa;
            testa = nullptr;
        }
        else
        {
            nodo *temp = testa;
            testa = testa->next;
            delete temp;
        }
        --dim;
    }
}

template <typename T>
void lista<T>::remove_coda()
{
    if(dim != 0)
    {
        if(dim == 1)
        {
            remove_testa();
        }
        else
        {
            nodo *iteratore = testa;
            while((iteratore->next)->next != nullptr)
            {
                iteratore = iteratore->next;
            }
            delete iteratore->next;
            iteratore->next = nullptr;
            --dim;
        }
    }
}

template <typename T>
void lista<T>::remove_(const unsigned int& indice)
{
    if(indice < dim)
    {
        if(indice == 0)
        {
            remove_testa();
        }
        else if(indice == dim - 1)
        {
            remove_coda();
        }
        else
        {
            nodo *iteratore = testa;
            for(unsigned int i = 0; i < indice - 1; i++)
            {
                iteratore = iteratore->next;
            }
            nodo *temp = iteratore->next;
            iteratore->next = temp->next;
            delete temp;
            --dim;
        }
    }
}

template <typename T>
void lista<T>::ridimensiona(const unsigned int& _dim)
{
    while(dim != _dim)
    {
        if(dim > _dim)
        {
            remove_coda();
        }
        else
        {
            add_coda();
        }
    }
}

template <typename T>
unsigned int lista<T>::get_dim()
{
    return dim;
}

template <typename T>
bool lista<T>::trova(const T& _dato)
{
    nodo* iteratore = testa;
    while(iteratore != nullptr)
    {
        if(iteratore->dato == _dato)
        {
            return 1;
        }
        iteratore = iteratore->next;
    }
    return 0;
}

template <typename T>
lista<T>& lista<T>::operator =(const lista<T>& l)
{
    if(this == &l)
    {
        return *this;
    }
    ridimensiona(l.dim);
    nodo *iteratore_1 = testa;
    nodo *iteratore_2 = l.testa;
    while(iteratore_2 != nullptr)
    {
        iteratore_1->dato = iteratore_2->dato;
        iteratore_1 = iteratore_1->next;
        iteratore_2 = iteratore_2->next;
    }
    return *this;
}

template <typename T>
T& lista<T>::operator[](const unsigned int& indice)
{
    if(indice < dim)
    {
        nodo *iteratore = testa;
        for(unsigned int i = 0; i < indice; i++)
        {
            iteratore = iteratore->next;
        }
        return iteratore->dato;
    }
    throw "ERRORE";
}

}

#endif // LISTA_H_INCLUDED

Sembra funzionare, ma vorrei sapere se devo correggere o aggiungere qualcosa per migliorarla.

[apatriarca]

Ti consiglio di imparare ad usare std::vector. Esistono situazioni in cui ci sono alternative migliori, ma è alla fine quasi sempre il miglior punto di partenza. Le liste concatenate hanno invece pochissimi utilizzi.

Non mi è particolarmente chiaro quale genere di consigli/commenti stai cercando. Suppongo che alcune cose che potresti fare sono:
1. Creare dei test per verificarne il funzionamento in modo automatico.
2. Definire una interfaccia simile a quella fornita dalle classi standard.

[Super Squirrel]

Per spunti su altre funzioni da implementare avevo già pensato di dare un'occhiata alla lista delle funzioni pubbliche della classe vector.
Test per verificare il funzionamento della classe in modo automatico sono una buona idea, ma in particolare volevo sapere se le varie funzioni che ho implementato potevano essere ottimizzate... anche se mi rendo conto che può risultare scoraggiante rispondere ad una richiesta del genere.
Inoltre mi chiedevo se vale la pena aggiungere un puntatore alla coda... nel senso se il maggior consumo di memoria può essere giustificato da un miglioramento delle prestazioni.

Ho implementato questa classe per poter sfruttare il dimensionamento dinamico degli "array" senza ricorrere a classi già fatte, perchè non mi piace utilizzare funzionalità che non so come siano state implementate. Quindi in futuro utilizzerò anche la classe vector.

Ti consiglio di imparare ad usare std::vector. Esistono situazioni in cui ci sono alternative migliori, ma è alla fine quasi sempre il miglior punto di partenza. Le liste concatenate hanno invece pochissimi utilizzi.

La classe vector non è implementata come una lista concatenata?

[apatriarca]

No, è un array allocato dinamicamente. Ogni volta che l'array viene riempito completamente, questo viene copiato su un nuovo array di dimensione doppia rispetto all'originale.

Riguardo all'uso di una doppia lista concatenata al posto di una normale dipende dal suo utilizzo. Se è spesso necessario accedere alla fine o iterare sull'array al contrario allora la doppia lista concatenata è certamente meglio. Una doppia lista concatenata è implementata in std::list.

Nota inoltre che accedere ai nodi della lista è abbastanza importante in quanto vuoi essere in grado di fare operazioni in posizioni qualsiasi della lista senza dover iterare tutte le volte.

[Super Squirrel]

Capisco.

Considerando i vari pro e contro di array e liste, è ovvio che alla fine la scelta migliore ricadrà su l'uno o sull'altro in base al tipo di problema che si sta affrontando.
Però, laddove si utilizzano array di grandi dimensioni o di tipi non nativi che occupano parecchia memoria, e si vuole modificare più volte la dimensione dell'array, secondo me l'utilizzo delle liste è preferibile all'allocazione dinamica degli array. Quindi in questi casi è meglio usare le liste che la classe vector, o sbaglio?

Sicuramente ci sono molte funzionalità e controlli che ignoro sull'implementazione della classe vector, ma sinceramente mi aspettavo qualcosa in più rispetto alla semplice allocazione dinamica di array. In ogni caso quali sono i vantaggi ad usare la classe vector rispetto ad un'allocazione dinamica della memoria implementata al momento?

[apatriarca]

Ci sono due grossi problemi sul tuo ragionamento:
1. L'occupazione di memoria di un vector è al più 2N*sizeof(T) + sizeof(std::vector) dove T è il tipo. Nel tuo caso hai N*(sizeof(T) + sizeof(lista::nodo*)) + sizeof(lista). La differenza non è quindi sostanzialmente diversa. In alcuni casi un vector potrebbe usare meno memoria e in altri il vantaggio ce l'ha la lista. In particolare, se sizeof(T) < sizeof(lista::nodo*), allora il vector occupa meno memoria. Se utilizzi una lista concatenata questo vantaggio del vector può essere anche più grande. In ogni caso l'occupazione di memoria nella maggior parte dei casi non è un parametro importante. Pure un cellulare ha ormai tantissima memoria.
2. Ignori due parametri MOLTO importanti: costo dell'allocazione di memoria e costo dell'accesso alla memoria. In linea di massima, l'allocazione della memoria è una delle operazioni più lente che puoi fare. Su una lista concatenata allochi memoria continuamente. In effetti ci sono anche molti altri vantaggi nel fare poche allocazioni grosse piuttosto che tante piccole. Per esempio un uso più efficiente della memoria. Il secondo aspetto riguarda un grosso limite nell'analisi asintotica classica. I computer moderni hanno una memoria gerarchica e accessi sequenziali alla memoria sono incredibilmente più veloci di accessi casuali. L'iterazione su un array è quindi potenzialmente più veloce di quello su una lista di almeno un ordine di grandezza.
3. Molti dei vantaggi asintotici delle liste sugli array (come la cancellazione in O(1)) richiedono di essere già in possesso del puntatore al nodo precedente a quello da cancellare. Se è necessaria una iterazione per arrivare all'elemento la complessità diventa uguale a quella di un array.

Insomma non esiste quasi alcun caso in cui una lista concatenata è più efficiente di un array allocato dinamicamente. E anche nei pochi casi in cui questo vantaggio sia presente, esistono soluzioni migliori.

[Super Squirrel]

Mi sembra di capire che il vantaggio teorico delle liste sugli array dinamici sia annullato dal fatto che i computer oggi hanno molta memoria e che ormai la velocità della CPU è nettamente superiore a quella di accesso alla RAM. Quindi nonostante lo spreco di memoria e la scarsa efficienza di alcune operazioni come inserimento e cancellazione di elementi, tranne alcuni casi, l'array risulta nella pratica una scelta più efficace rispetto alle liste. Giusto?

No, è un array allocato dinamicamente. Ogni volta che l'array viene riempito completamente, questo viene copiato su un nuovo array di dimensione doppia rispetto all'originale.

Quindi se volessi implementare una classe simile a vector dovrei dotarla (come dati-membro) di un puntatore, di una dimensione "utilizzata" e di una dimensione "reale" ?