Implementation stl (list)

Commenter

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

S'inscrire maintenant

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)