Implementation stl (list)

Soyez le premier à donner votre avis sur cette source.

Snippet vu 9 166 fois - Téléchargée 30 fois

Contenu du snippet

Salout,
J'ai codé récemment une toute petite implementation de la fonctionnalite LIST de la STL, c'est tres simple...
J'ai implemente une classe "List" pour cela, et j'ai defini la plupart des fonctions appropriées au fonctionnement d'une liste, voici la liste :
- push_front()
- push_back()
- pop_front()
- pop_back()
- remove()
- begin()
- end()

Il sufit alors d'instancier un objet de la classe List, et de fare appel aux methodes membres pour effectuer des operations (comme pour rajouter un element au debut de la liste, ou a la fin, en supprimer, obtenir le pointeur de tete, etc...)

Source / Exemple :


// Implémentation de la List

/* List.h : class for double linked list */
/* Writed by Taron_ -> GPL attitude ;) */

#ifndef _LIST_H_
#define _LIST_H_

#include <iostream>
using namespace std;

/* Types of errors */
#define ERROR_ALLOCATE_HEAP 1
#define ERROR_FREE_HEAP     2

#define OK 0

/* Class declaration */

template <typename T> 
class List
{
 private:
   struct Link   // Struct for linked list
   {
      T Value;   // Value of new object
       
      Link *Next;
      Link *Prev;
   };
          
   typedef struct Link Link;            
   Link *End;   

 public:
   List();   /* Constructor & Destructor */
  ~List();

   friend ostream& operator<<(ostream&, List<T>);

   int push_front(T);  /* Insert a element */
   int push_back(T);
   
   void pop_front();   /* Delete a element */
   void pop_back();
 
   void remove(T);

   Link* begin();   /* Get address for begin and end of list */
   Link* end();

   Link *Temp, *Head;
};

template <typename T>
ostream& operator<<(ostream& Out, List<T> L)
{
   L.Temp = 0;

   if(L.Head->Value == 0) L.Temp = L.Head->Next;
   else L.Temp = L.Head;

   /* Display all object */
   for(; L.Temp != 0 ; L.Temp = L.Temp->Next)
      cout << L.Temp->Value << endl;             

   return Out;
}

template <typename T>
List<T>::List()   /* Constructor */
{
   Head = (Link *)malloc(sizeof(Link));   /* Prepare the list */
  
   Head->Next = 0;
   Head->Prev = 0;
   
   Head->Value = 0;

   End = Head;   
}

template <typename T>
List<T>::~List()   // Destructor
{
   Temp = 0;
   
   if(Head->Value == 0) Temp = Head->Next;
   else Temp = Head;   

   for(; Temp != 0 ; Temp = Temp->Next);
   // free(Temp);
}

template <typename T>
int List<T>::push_front(T Value)   /* Add a value front of the list */
{
   Link *New = 0;
   New = (Link *)malloc(sizeof(Link));

   if(Head->Value != 0)
   {
      if(!New) return ERROR_ALLOCATE_HEAP;   // Can't allocate heap memory !
   
      New->Next = Head;
      New->Prev = 0;
   
      Head->Prev = New;
      New->Value = Value;

      Head = New;   // Update of new Head
   }

   else Head->Value = Value;

   return OK;
}

template <typename T>
int List<T>::push_back(T Value)   /* Add a value at the end of the list */
{
   Temp = 0;
   Link *New = 0;
   
   if(Head->Next != 0)
   {
      for(Temp = Head ; Temp->Next != 0 ; Temp = Temp->Next); 
   }

   else Temp = Head;
   
   New = (Link *)malloc(sizeof(Link));   // Allocate memory for new object
   if(!New) return ERROR_ALLOCATE_HEAP;   // Can't allocate heap memory !

   Temp->Next = New;

   New->Prev = Temp;   /* Insert into list */
   New->Next = 0;

   New->Value = Value;
   End = New;

   return OK;
}

template <typename T>
void List<T>::pop_front()   /* Delete the first element of the list */
{
   Temp = Head;

   Head = Head->Next;
   free(Temp);   // Be free
}

template <typename T>
void List<T>::pop_back()   /* Delete the last element of the list */
{
   Temp = 0;

   for(Temp = Head ; Temp->Next != 0 ; Temp = Temp->Next);
   
   Temp->Prev->Next = 0;
   free(Temp);   // Free
}

template <typename T>
void List<T>::remove(T Value)
{
   if(Head->Value == 0) Temp = Head->Next;
   else Temp = Head;

   Link *Copy = 0;

   /* Moving in the list */
   for(; Temp != 0 ; Temp = Temp->Next)
      if(Temp->Value == Value)
	  {
         Copy = Temp->Prev;
         
		 if(Temp->Prev != 0)
		   Temp->Prev->Next = Temp->Next;
	
		 if(Temp->Next != 0)
		   Temp->Next->Prev = Temp->Prev;
         
   		 free(Temp);
		 Temp = Copy;
	  }
}

template <typename T>
List<T>::Link* List<T>::begin()
{
   return Head;   // Return head of the list
}

template <typename T>
List<T>::Link* List<T>::end()
{
   return End;   // Return end of the list
}

#endif

// voici un court exemple d'utilisation

#include <iostream>
#include "List.h"

using namespace std;

int main()
{
    List<char> l;
    
    l.push_back('z');
    l.push_back('p');
    l.push_front('r');
    l.push_back('b');
    l.push_front('p');
    l.push_back('i');
    l.push_front('p');
    l.push_back('u');
    l.push_back('p');

    cout << l << endl;

    l.remove('p');

    cout << l << endl;

    l.pop_front();
    l.pop_back();

    return 0;
}

Conclusion :


Je l'ai fait sur VC++...
Le seul problème dans mon code se situe dans le code du destructeurs : lorsque je libere avec free(), j'ai un "Fatal error !", je ne sais pas pourquoi, pourtant, je free() les bons elements (j'ai verifié lors du debugage). C'est pour ca que j'ai mis free() en comentaires (//).

Par contre, je suis desolé, je n'ai pas mis de commentaires (le peu qui s'y trouve, je l'ai mis en anglais :s)
Sinon le code n'est pas difficile a comprendre... bye !

PS : j'accepte tous commentaires.

A voir également

Ajouter un commentaire Commentaires
Messages postés
199
Date d'inscription
vendredi 16 avril 2004
Statut
Membre
Dernière intervention
28 février 2008

Merci :-)
Messages postés
6
Date d'inscription
mercredi 25 août 2004
Statut
Membre
Dernière intervention
23 septembre 2005

La methode est interessante :)
De + tu utilises une classe plutôt qu'une variable de type structuré. A++
Messages postés
199
Date d'inscription
vendredi 16 avril 2004
Statut
Membre
Dernière intervention
28 février 2008

Ha, ok merci :)
J'avais pas fait gaffe...
Messages postés
1878
Date d'inscription
jeudi 16 octobre 2003
Statut
Membre
Dernière intervention
16 mars 2011
1
évidemment....

=>mémoriser le ptr suivant avt de libérer l'elt...
Messages postés
2
Date d'inscription
dimanche 27 juillet 2003
Statut
Membre
Dernière intervention
8 septembre 2005

Analyson ta liberation de mémoire dans le destructeur (imaginons que l'on enlève ton commentaire):

for(; Temp !0 ; Temp Temp->Next)
free(Temp);

Que ce passe-t-il à l'exécution
1) première partie du for initialisation : rien car for(;...)
2) Teste de fin Temp!=0 (temp est rempli plus haut, imaginons qu'il y ai 2 elements donc temp!=0
3) tu libère la mémoire sur la quelle temp pointe (free Temp)
4) tu viens à la 3ème partie du for Temp=Temp->Next mais Temp (partie de droite) n'est plus alloué car tu a fait free, ton problème est a mon avis à ce niveau. Faudrait peut-être penser à sauver Temp->Next avant le free.
Afficher les 12 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (Taron31)