Voici un conteneur d'objets, une liste doublement chaînée.
Vous pourrez ajouter, insérer, supprimer, modifier, permuter et parcourir les éléments de la liste.
Pour des traitements plus rapides, des itérateurs sont à disposition.
Cette source est à but éducative, car si vous utilisez la STL, il est nettement préférable d'utiliser la librairie <list>.
Source / Exemple :
/* Container; liste doublement chaînée
fichier listc.h */
#include <windows.h> //Pour allocation/suppression de mémoire dans le tas
//#include <stdio.h>
template <class T> class listc;
template <class T> class i_listc;
template <class M> class engine { //classe de l'objet contenu
private:
engine<M>*next; //pointeur sur l'objet suivant
engine<M>*prev; //pointeur sur l'objet précédant
M data; //l'objet
friend listc<M>; //l'accès aux membres privés est autorisé pour le conteneur
friend i_listc<M>;//l'accès aux membres privés est autorisé pour l'itérateur
};
template <class T> class i_listc { //classe de l'itérateur
private:
engine<T>*elm;
listc<T> *parent;
friend listc<T>;
public:
typedef i_listc<T> iter;
i_listc(void *); //pour les conversions
i_listc(); //constructeur par défaut
T get(); //retourne l'objet
bool Delete(); //efface l'objet
bool InsertA(T);
bool InsertB(T);
bool set(T);
iter operator++ (); //passe à l'élément suivant
iter operator++ (int);
iter operator-- (); //passe à l'élément précédent
iter operator-- (int);
bool operator==(const iter&) const;
bool operator!=(const iter&) const;
listc<T> *ptr();
};
template <class T> class listc { //classe générale du conteneur de la liste chaînée
private:
engine<T> *head; //pointeur sur le premier objet
engine<T> *queue;//pointeur sur le dernier objet
int total; //nombre total d'objets contenus dans la liste chaînée
i_listc<T> cur;
bool New(T);
public:
typedef i_listc<T> iterator; //on crée un alias
iterator begin();
iterator end();
iterator ptr(int); //on revoit un itérateur sur le Nième objet de la liste
listc(); //constructeur par défaut
~listc();
bool Swap(iterator &, iterator &); //échange la place des éléments
bool AddFront(T); //ajoute un nouveau élément en début de liste
bool AddBack(T); //ajoute un nouveau élément en fin de liste
bool Delete(int i); //supprime le Nième objet
bool Delete(iterator &); //supprime l'objet pointé par l'itérateur
bool InsertA(iterator &, T); //Insert un nouveau élément après l'objet pointé
bool InsertB(iterator &, T); //Insert un nouveau élément avant l'objet pointé
bool set(iterator &, T); //modifie l'objet
Free(); //Efface tous les objets
T operator [] (int); //opérateur d'indexation
int Total(); //nombre total d'objets contenus
size_t size() const; //taille du conteneur
//aff();
};
/*
template <class T>listc<T>::aff() {
engine<T> *elm = head;
cout << "-\n";
while (elm) {
cout << "ptr: " << elm
<< " next: " << elm->next
<< " prev: " << elm->prev
<< " data: " << elm->data << endl;
elm = elm->next;
}
cout << "\n<head>\tptr: " << head << " next: " << head->next
<< " prev: " << head->prev
<< " data: " << head->data << endl;
cout << "<queue>\tptr: " << queue << " next: " << queue->next
<< " prev: " << queue->prev
<< " data: " << queue->data << endl;
cout << "-\n";
}
template <class T> listc<T>* i_listc<T>::ptr() {
return parent;
}
template <class T> i_listc<T>::i_listc(void *ptr) {
elm = (engine<T>*)ptr;
}
template <class T> bool i_listc<T>::operator ==(const i_listc<T> &source) const {
if (elm == source.elm) return 1;
return 0;
}
template <class T> bool i_listc<T>::operator !=(const i_listc<T> &source) const {
if (elm != source.elm) return 1;
return 0;
}
template <class T> i_listc<T>::i_listc():elm(NULL){; }
template <class T> i_listc<T> i_listc<T>::operator ++() { // ++x
if (!elm) return *this;
elm = elm->next;
return *this;
}
template <class T> i_listc<T> i_listc<T>::operator ++(int) { // x++
if (!elm) return *this;
i_listc<T> tmp = *this;
elm = elm->next;
return tmp;
}
template <class T> i_listc<T> i_listc<T>::operator --() { // --x
if (!elm) return *this;
elm = elm->prev;
return *this;
}
template <class T> i_listc<T> i_listc<T>::operator --(int) { // x--
if (!elm) return *this;
i_listc<T> tmp = *this;
elm = elm->prev;
return tmp;
}
template <class T> bool i_listc<T>::set(T data) {
return parent->set(*this,data);
}
template <class T> bool i_listc<T>::InsertA(T data) {
return parent->InsertA(*this,data);
}
template <class T> bool i_listc<T>::InsertB(T data) {
return parent->InsertB(*this,data);
}
template<class T>bool listc<T>::Swap(iterator &elm1, iterator &elm2) {
if (elm1 == NULL || elm2 == NULL) return 0;
iterator first, second;
engine<T> *ptr1, *ptr2;
if (elm1.elm->next == elm2.elm) first = elm1, second = elm2;
else if (elm2.elm->next == elm1.elm) first = elm2, second = elm1;
else goto next;
/*les deux éléments se suivent directement, donc nous n'échangerons
pas bêtement les pointeurs des deux éléments, en effet cela
pourrait conduire à un bogue (élément qui pointerait sur lui-même) */
ptr1 = first.elm->prev, ptr2 = second.elm->next;
second.elm->next = first.elm;
second.elm->prev = ptr1;
if (ptr1) ptr1->next = second.elm;
first.elm->prev = second.elm;
first.elm->next = ptr2;
if (ptr2) ptr2->prev = first.elm;
goto end;
next:
/*les deux éléments ne se suivent pas, nous utiliserons donc
une technique qui consistera à échanger tous les pointeurs
des deux éléments */
ptr1 = elm1.elm->next, ptr2 = elm1.elm->prev;
if (elm1.elm->prev) elm1.elm->prev->next = elm2.elm;
if (elm1.elm->next) elm1.elm->next->prev = elm2.elm;
elm1.elm->next = elm2.elm->next;
elm1.elm->prev = elm2.elm->prev;
if (elm2.elm->prev) elm2.elm->prev->next = elm1.elm;
if (elm2.elm->next) elm2.elm->next->prev = elm1.elm;
elm2.elm->next = ptr1;
elm2.elm->prev = ptr2;
end:
//on met à jour le pointeur de début de liste et de fin de liste
if (head == elm1.elm) head = elm2.elm;
else if (head == elm2.elm) head = elm1.elm;
if (queue == elm1.elm) queue = elm2.elm;
else if (queue == elm2.elm) queue = elm1.elm;
return 1;
}
template <class T>i_listc<T> listc<T>::ptr(int i) {
engine<T> *elm = head;
for (int o = 1;(elm && elm->next) && o != i;o++) elm = elm->next;
if (o == i && elm) {
cur.elm = elm;
cur.parent = this;
return cur;
}
cur.elm = NULL;
cur.parent = this;
return cur;
}
template <class T>T i_listc<T>::get() {
return elm->data;
}
template <class T> i_listc<T> listc<T>::begin() {
cur.elm = head;
cur.parent = this;
return cur;
}
template <class T> i_listc<T> listc<T>::end() {
cur.elm = queue;
cur.parent = this;
return cur;
}
template <class T> bool i_listc<T>::Delete() {
return parent->Delete(*this);
}
template <class T> bool listc<T>::New(T data) {
engine<T> *elm = (engine<T>*)HeapAlloc(GetProcessHeap(),0,sizeof(engine<T>));
elm->next = NULL;
elm->prev = NULL;
elm->data = data;
queue = head = elm;
total++;
return 1;
}
template <class T> bool listc<T>::set(iterator &iter, T data) {
if (iter.parent != this || iter.elm == NULL) return 0;
iter.elm->data = data;
return 1;
}
template <class T> bool listc<T>::AddFront(T data) {
if (!head) return New(data); /* si la liste est vide, on la crée */
iterator iter = begin();
return InsertB(iter,data);
}
template <class T> bool listc<T>::AddBack(T data) {
if (!head) return New(data);
iterator iter = end();
return InsertA(iter,data);
}
template <class T> bool listc<T>::InsertA(iterator &iter, T data) {
if (iter.parent != this || iter.elm == NULL) return 0;
engine<T> *elm = (engine<T>*)HeapAlloc(GetProcessHeap(),0,sizeof(engine<T>));
if (!elm) return 0;
if (queue == iter.elm) {
queue = elm;
elm->next = NULL;
}
else {
elm->next = iter.elm->next;
iter.elm->next->prev = elm;
}
iter.elm->next = elm;
elm->prev = iter.elm;
elm->data = data;
total++;
return 1;
}
template <class T> bool listc<T>::InsertB(iterator &iter, T data) {
if (iter.parent != this || iter.elm == NULL) return 0;
engine<T> *elm = (engine<T>*)HeapAlloc(GetProcessHeap(),0,sizeof(engine<T>));
if (!elm) return 0;
if (head == iter.elm) {
head = elm;
elm->prev = NULL;
}
else {
elm->prev = iter.elm->prev;
iter.elm->prev->next = elm;
}
iter.elm->prev = elm;
elm->next = iter.elm;
elm->data = data;
total++;
return 1;
}
template <class T> bool listc<T>::Delete(iterator &iter) {
engine<T>*elm;
if (iter.parent != this) return 0;
if (iter.elm == NULL) return 0;
elm = iter.elm->next;
if (iter.elm == head) {
head = elm;
if (head) head->prev = NULL;
}
else {
if (queue == iter.elm) queue = iter.elm->prev;
iter.elm->prev->next = elm;
if (iter.elm->next) iter.elm->next->prev = iter.elm->prev;
}
HeapFree(GetProcessHeap(),0,iter.elm);
total--;
iter.elm = elm;
return 1;
}
template <class T> bool listc<T>::Delete(int i) {
listc<T>::iterator iter = ptr(i);
return Delete(iter);
}
template <class T>T listc<T>::operator[](int i) {
engine<T> *elm = head;
for (int o = 0;(elm && elm->next) && o != i;o++) elm = elm->next;
if (o == i && elm) return elm->data;
return NULL;
}
template <class T> listc<T>::listc():head(NULL),queue(NULL),total(0){ ; }
template <class T> listc<T>::~listc() {
Free();
}
template <class T>int listc<T>::Total() {
return total;
}
template <class T>listc<T>::Free() {
engine <T> *elm = head;
while (head) {
head = elm->next;
engine<T> *del = elm;
HeapFree(GetProcessHeap(),0,del);
elm = head;
}
head = queue = NULL;
total = 0;
}
template <class T>size_t listc<T>::size() const {
return sizeof(listc<T>) + sizeof(engine<T>) * total;
}
Conclusion :
Si vous ne voulez pas utiliser <windows.h> pour la gestion dynamique de la mémoire, remplacez HeapAlloc() et HeapFree() par leur équivalent (new et add si vous utilisez les librairies C++).
Pour voir comment parcourir les éléments de la liste à l'aide d'itérateurs, regardez la fonction aff().
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.