Voilà mon problème : je cherche à recréer la classe list de la librairie STL (puisque j'en ai besoin pour un programme que je développe). Je ne veux pas utiliser la classe de la STL, mais je préfère l'implémenter moi-même, pour créer une liste simplement chaînée. Dans ce but, j'ai créé une classe qui contient 4 variables : le pointeur qui pointe sur le début de la liste, celui qui pointe sur le dernier élément de la liste, un "itérateur" (pas encore mis en fonction) et la taille de la liste. Cependant, ce code ne fonctionne pas même s'il compile donc je sollicite votre aide. Merci d'avance.

#ifndef DEF_LISTE_CHAINEE
    #define DEF_LISTE_CHAINEE

    template <typename T> class ListeChainee
    {
        public :

        struct Element
        {
            T value;
            Element* next;
        };
        struct S_Iterator
        {
            Uint value;
            Element* next;
        };

        ListeChainee();
        ListeChainee(const ListeChainee &liste);
        ListeChainee(T &objet);
        ~ListeChainee();

        void push_front(T &objet);
        void push_back(T &objet);
        void pop_front();
        void pop_back();
        unsigned int size();
        void display();

        const ListeChainee &operator--(int nb);
        const ListeChainee &operator--(void);
        ListeChainee operator=(ListeChainee& liste);
        const T &operator[](int nb);



        protected :

        Element *m_head;
        Element *m_last;
        S_Iterator m_iterator;
        Uint m_size;


    };

#include "constantes.h"
#include "ListeChainee.h"

template <typename T>

ListeChainee::ListeChainee()
{
    m_head = NULL;
    m_last = NULL;
    m_iterator.value = 0;
    m_iterator.next = NULL;
    m_size = 0;
}
ListeChainee::ListeChainee(T &objet)
{
    m_head = new Element;
    m_head->value = objet;
    m_head->next = NULL;
    m_last = m_head;
    m_size = 1;

}
ListeChainee::ListeChainee(const ListeChainee &liste)
{
    Element* thistemp = NULL;
    Element * listetemp = NULL;

    thistemp = this->m_head;
    listetemp = liste.m_head;

    while(listetemp != NULL)
    {
        thistemp = new Element:
        thistemp->next = NULL;
        thistemp->value = listetemp->value;
        thistemp = thistemp->next;
        listetemp = listetemp->next;
        if(listetemp->next == NULL)
        {
            this->m_last = listetemp;
        }
    }
    this->m_size = liste->m_size;
    return (*this);

}
ListeChainee::~ListeChainee()
{
    Element *temp = NULL, *pretemp = NULL;

    temp = m_head;
    while(temp != NULL)
    {
        pretemp = temp;
        temp = temp->next;
        delete pretemp;
    }

}
void ListeChainee::push_front(T &objet)
{
    Element *nouveau = NULL;
    nouveau = new Element;
    nouveau->value = objet;
    nouveau->next = m_head;
    m_head = nouveau;
    m_size++;
}
void ListeChainee::push_back(T &objet)
{
    Element *nouveau = NULL;
    nouveau = new Element;
    nouveau->value = objet;
    nouveau->next = NULL;

    if(m_head != NULL)
    {
        m_last->next = nouveau;
        m_last = nouveau;
    }
    else
    {
        m_head = nouveau;
        m_last = nouveau;
    }
    m_size++;

}
void ListeChainee::pop_front()
{

    if(m_head != NULL)
    {
        Element *hold = NULL;
        hold = m_head->next;
        delete m_head;
        m_head = hold;
    }
}
void ListeChainee::pop_back()
{
    Element *hold = NULL;
    hold = m_head;
    if(hold != NULL)
    {
        if(hold->next != NULL)
        {
            while(hold->next->next != NULL)
            {
                hold = hold->next;
            }
            delete hold->next;
            m_size--;
            m_last = hold;

        }
        else
        {
            delete m_head;
            m_size = 0;
        }
    }
}
Uint ListeChainee::size()
{
    return m_size;
}

void ListeChainee::display()
{
    Element *temp = NULL;
    temp = m_head;

    while(temp != NULL)
    {
        cout << temp->value;
        cout << " ]...[ ";
        temp = temp->next;
    }
}

Hello,

Pourquoi ne pas utiliser la STL, ce sera certainement plus efficace et plus sécurisé que ton code.

Mis à part ça, as tu essayé de débuguer ton code via un débugueur ? Ce sera sûrement le moyen le plus efficace de voir si tu as des pointeurs fous.

c'est sûr la STL est tres pratique

Mais la coder soi même est un bonne entrainement sur l'utilisation des templates , les class,les operateurs,...



Au fait peux tu nous dire quel fonction ne pose aucun probleme?

(car ça fait de la lecture et les noms de variable [pour moi] ne sont pas très explicite )

thistemp = new Element:

Qu'est ce qu'ils font là tes deux points là ? Remplace les par un point-virgule.

Pourquoi tu as une variable membre itérateur ?

Pourquoi la valeur de ton itérateur est type Uint alors que ta classe contient des T ?

Que fait une fonction display() dans une classe "utilité" ?

Pourquoi la surcharge de l'opérateur -- ? Cette fonctionnalité me semble incongrue. Ce genre de manipulation devraient être commentées.

Il y a beaucoup de méthodes qui devraient être const...

Pourquoi renvois-tu une référence constante avec l'opérateur [] ?

Les variables membres devraient être private et non protected. Une classe de ce type ne devrait pas être surchargée et sinon, elle devrait offrir des méthodes à ces classes filles pour accéder à ces attributs.

Pourquoi tu as un return dans ton constructueur par copie ?

P.S. Je ne suis pas contre le fait que tu veuilles apprendre en travaillant fort pour implémenter des concepts connus dans une classe. Mais ne penses pas recréer celle de la STL. Concentre-toi à faire quelque chose de fonctionnel qui va répondre à tes besoins et rien d'autre.

Citation : neuneutrinos

c'est sûr la STL est tres pratique

Mais la coder soi même est un bonne entrainement sur l'utilisation des templates , les class,les operateurs,...

Je ne dis pas le contraire, mais apparement ici, c'est pour l'utiliser dans le cadre d'un autre programme.

Programmer la classe std::list<> est très certainement un excellent exercice, tout comme std::map<>, mais ça c'est une autre paire de manche.

Merci à tous pour vos réponses. Je vais donc préciser les points flous.

Citation : MatteX

Pourquoi tu as une variable membre itérateur ?

Pour me permettre de parcourir la liste en utilisant une boucle et j'utilise une boucle où i s'incrémente, garder un pointeur vers le dernier élément retourné me permet d'accéder plus rapidement à l'élément suivant (pas besoin de reparcourir toute la liste

Pourquoi la valeur de ton itérateur est type Uint alors que ta classe contient des T ?

En fait, l'itérateur contient le numéro de l'élément de la liste (forcément positif => Uint) + un pointeur sur l'élément


Que fait une fonction display() dans une classe "utilité" ?

Erreur de ma part

Pourquoi la surcharge de l'opérateur -- ? Cette fonctionnalité me semble incongrue. Ce genre de manipulation devraient être commentées.

Je veux pouvoir faire :
liste--;//Supprime le dernier élément
--liste;//Supprime le premier élément

Il y a beaucoup de méthodes qui devraient être const...


Pourquoi renvois-tu une référence constante avec l'opérateur [] ?
Erreur de ma part

Les variables membres devraient être private et non protected. Une classe de ce type ne devrait pas être surchargée et sinon, elle devrait offrir des méthodes à ces classes filles pour accéder à ces attributs.
C'est une habitude de mettre protected...je rectifierai.

Pourquoi tu as un return dans ton constructueur par copie ?


P.S. Je ne suis pas contre le fait que tu veuilles apprendre en travaillant fort pour implémenter des concepts connus dans une classe. Mais ne penses pas recréer celle de la STL. Concentre-toi à faire quelque chose de fonctionnel qui va répondre à tes besoins et rien d'autre.

Je ne prétends pas recréer la STL, juste créer une classe de liste chainée de base.

alors ce n,est pas un itérateur... Tu devrais repenser ton itérateur comme un objet fermé imitant un pointeur.

liste--; --liste;... c'est ce que je craignais, tant que tu ne distribu pas ton truc, tu peux faire ce que tu veux.

C'est-à-dire ? Quelles sont tes craintes ?

Ce que je vois là, c'est une liste qui se prend pour un vecteur. Une liste n'est pas structurée pour permettre l'accès direct aux données. Alors, cet opérateur [], je ne vois pas ce qu'il fait là. Si ton "itérateur" est un simple entier, cela signifie que, pour accéder à sa valeur, tu devra parcourir la liste... Un accès à un itérateur (tout comme un accès à un pointeur, d'ailleurs) est supposé avoir une complexité de O(1), pas O(n)! Je verais un Element * à la place...

Ah, ouais, je remarque l'utilisation de "cout" dans ta fonction display(). Cela signifie que ta classe ne sera utilisable qu'en console. Si tu tiens vraiment à utiliser un flux, passe un std::ostream en référence à la fonction et écrit dedans...

N'empêche, je trouve étrange de vouloir réinventer la roue... si c'était pour apprendre comment fonctionne une liste, d'accord, mais sinon... certains ce sont défoncé sur les conteneurs de la STL. T'a beau essayé, ton code ira beaucoup moins vite. Alors, voilà, pourquoi réinventer la roue?

Il y a deux choses. Il est très bien de savoir réinventer la roue. Mais quand on fait ça, réinventer doit rester le seul et unique objectif -- voir ça comme un TD/TP.

Par contre, quand il s'agit d'utiliser une roue pour construire quelque chose de plus grand, il faut savoir rester modeste et exploiter des roues abondamment testée par d'autres, et généralement mieux conçues.



Sinon, effectivement, utiliser des indices avec une liste chainée est contre nature.

De plus, embarquer un itérateur (ou un quelconque autre indice) de l'élément courant dans un conteneur n'a généralement pas le moindre sens.

Dernier truc, ton utilisation de --() ne parait logique qu'à toi. C'est ce genre de détournement à mauvais escient qui fait que certains pondent ensuite des langages ultra bridés avec pour excuse que les gens font n'importe quoi avec.

Ok...Pour mon projet je vais donc me rabattre sur les std::list. Merci à tous !