À titre d'exercice, j'essaye d'implémenter un semblant de std::list.
J'ai trois objets :
template<typename T> struct Node {
T payload; // la donnée à stocker
Node *prev; // adresse du noeud précédent
Node *next; // adresse du noeud suivant
};
template<typename T> class Node_iter {
friend List<T>;
Node<T> *node; // le noeud actuel
public:
// opérateurs *, ->, ==, !=, ++, --, etc.
};
template<typename T> class List {
Node<T> *first; // adresse du premier noeud de la liste
Node<T> *last; // adresse du dernier noeud de la liste
std::size_t nb_node; // nombre de noeuds
std::allocator alloc; // allocateur
public:
typedef Node_iter<T> iterator;
iterator end();
// une partie de ce que l'on attend d'une liste
};
Je bloque sur l'implémentation du end() qui doit renvoyer un itérateur
sur l'élément après le dernier. Autant, avec un std::vector, c'est facile
de chercher l'élément suivant puisque les éléments sont contiguës autant
là, je ne vois pas comment faire ça proprement.
Au début j'étais parti sur :
L'adresse du noeud précédent le premier est égale à 0
L'adresse du noeud suivant le dernier est égale à 0
Seulement, si je fais cela, je ne peux plus faire la conversion
itérateur -> élément car end() renvoie un iterator où node = 0, du coup
on ne peut pas faire -- dessus (-- revoit un itérateur ou node = node->prev).
Plus j'y réfléchi, plus je me dis que la seule solution est de créer un
noeud sans donnée et qu'il me servira de "noeud après le dernier", c'est
à dire que je remplace le membre de List last par after_last. Mais, du
coup, une liste vide contient toujours un noeud.
Est-ce la seule manière de faire ou est-ce que je suis à coté de la
plaque ?
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Lucas Levrel
Le 17 avril 2015, Benoit Izac a écrit :
template<typename T> class Node_iter { friend List<T>; Node<T> *node; // le noeud actuel public: // opérateurs *, ->, ==, !=, ++, --, etc. };
Au début j'étais parti sur : L'adresse du noeud précédent le premier est égale à 0 L'adresse du noeud suivant le dernier est égale à 0 Seulement, si je fais cela, je ne peux plus faire la conversion itérateur -> élément car end() renvoie un iterator où node = 0, du coup on ne peut pas faire -- dessus (-- revoit un itérateur ou node = node->prev).
Est-ce qu'il n'y a pas moyen de mettre un drapeau dans Node_iter pour particulariser le cas "end", et mettre un test dans -- ? (Il faudrait que Node_iter soit friend de List, je suppose.)
Plus j'y réfléchi, plus je me dis que la seule solution est de créer un noeud sans donnée et qu'il me servira de "noeud après le dernier", c'est à dire que je remplace le membre de List last par after_last. Mais, du coup, une liste vide contient toujours un noeud.
Ça ne me choque pas vraiment, pour un objet qui doit grossir à la demande, d'avoir une case « en attente ». D'ailleurs vector a une notion de capacité distincte de sa taille, pour des raisons de performances, non ?
-- LL Ἕν οἶδα ὅτι οὐδὲν οἶδα (Σωκράτης)
Le 17 avril 2015, Benoit Izac a écrit :
template<typename T> class Node_iter {
friend List<T>;
Node<T> *node; // le noeud actuel
public:
// opérateurs *, ->, ==, !=, ++, --, etc.
};
Au début j'étais parti sur :
L'adresse du noeud précédent le premier est égale à 0
L'adresse du noeud suivant le dernier est égale à 0
Seulement, si je fais cela, je ne peux plus faire la conversion
itérateur -> élément car end() renvoie un iterator où node = 0, du coup
on ne peut pas faire -- dessus (-- revoit un itérateur ou node = node->prev).
Est-ce qu'il n'y a pas moyen de mettre un drapeau dans Node_iter pour
particulariser le cas "end", et mettre un test dans -- ? (Il faudrait que
Node_iter soit friend de List, je suppose.)
Plus j'y réfléchi, plus je me dis que la seule solution est de créer un
noeud sans donnée et qu'il me servira de "noeud après le dernier", c'est
à dire que je remplace le membre de List last par after_last. Mais, du
coup, une liste vide contient toujours un noeud.
Ça ne me choque pas vraiment, pour un objet qui doit grossir à la demande,
d'avoir une case « en attente ». D'ailleurs vector a une notion de
capacité distincte de sa taille, pour des raisons de performances, non ?
template<typename T> class Node_iter { friend List<T>; Node<T> *node; // le noeud actuel public: // opérateurs *, ->, ==, !=, ++, --, etc. };
Au début j'étais parti sur : L'adresse du noeud précédent le premier est égale à 0 L'adresse du noeud suivant le dernier est égale à 0 Seulement, si je fais cela, je ne peux plus faire la conversion itérateur -> élément car end() renvoie un iterator où node = 0, du coup on ne peut pas faire -- dessus (-- revoit un itérateur ou node = node->prev).
Est-ce qu'il n'y a pas moyen de mettre un drapeau dans Node_iter pour particulariser le cas "end", et mettre un test dans -- ? (Il faudrait que Node_iter soit friend de List, je suppose.)
Plus j'y réfléchi, plus je me dis que la seule solution est de créer un noeud sans donnée et qu'il me servira de "noeud après le dernier", c'est à dire que je remplace le membre de List last par after_last. Mais, du coup, une liste vide contient toujours un noeud.
Ça ne me choque pas vraiment, pour un objet qui doit grossir à la demande, d'avoir une case « en attente ». D'ailleurs vector a une notion de capacité distincte de sa taille, pour des raisons de performances, non ?
-- LL Ἕν οἶδα ὅτι οὐδὲν οἶδα (Σωκράτης)
Benoit Izac
Bonjour,
le 17/04/2015 à 21:20, Lucas Levrel a écrit dans le message :
template<typename T> class Node_iter { friend List<T>; Node<T> *node; // le noeud actuel public: // opérateurs *, ->, ==, !=, ++, --, etc. };
Au début j'étais parti sur : L'adresse du noeud précédent le premier est égale à 0 L'adresse du noeud suivant le dernier est égale à 0 Seulement, si je fais cela, je ne peux plus faire la conversion itérateur -> élément car end() renvoie un iterator où node = 0, du coup on ne peut pas faire -- dessus (-- revoit un itérateur ou node = node->prev).
Est-ce qu'il n'y a pas moyen de mettre un drapeau dans Node_iter pour particulariser le cas "end", et mettre un test dans -- ? (Il faudrait que Node_iter soit friend de List, je suppose.)
Actuellement, j'ai : Node_iter& operator--() { n = n->prev; return *this; } Node_iter operator--(int) { Node_iter old = *this; --(*this); return old; } Il faut donc que n existe sinon ça fait boum sur n->prev.
Tu suggères donc d'ajouter un variable membre dans Node_iter contenant l'adresse de la liste et de faire un truc comme : Node_iter& operator--() { if (n == 0) n = l->last // List *l; else n = n->prev; return *this; }
Pourquoi pas mais ça m'oblige à créer les itérateurs non plus comme iterator(first); mais comme iterator(this, first);
Plus j'y réfléchi, plus je me dis que la seule solution est de créer un noeud sans donnée et qu'il me servira de "noeud après le dernier", c'est à dire que je remplace le membre de List last par after_last. Mais, du coup, une liste vide contient toujours un noeud.
Ça ne me choque pas vraiment, pour un objet qui doit grossir à la demande, d'avoir une case « en attente ». D'ailleurs vector a une notion de capacité distincte de sa taille, pour des raisons de performances, non ?
Oui mais, autant avec un vector, je comprends le besoin d'allouer un grand espace d'un coup pour éviter de faire des copies à chaque fois qu'il grandit, autant sur une liste qui va chercher une case mémoire n'importe où, je ne vois pas l'intérêt.
J'ai réussi à m'en sortir et ça semble bien fonctionner comme ça, c'est à dire en créant un noeud sans donnée qui reste pendant toute la durée de vie de la liste le "noeud après le dernier". Ce n'est pas fini mais pour les plus courageux, voici où j'en suis, toute remarque est bienvenue (c'est du C++11) :
// create an empty list List() : first(new node), after_last(first), nb_node(0) {}
// create a list with n elements ; each element is a copy of data List(int n, const T& data) : List() { for (auto i = 0; i < n; ++i) push_back(data); }
// create a list with a copy of [b, e) List(iterator b, iterator e) : List() { for (auto it = b; it != e; ++it) push_back(*it); }
// create a copy of l List(const List& l) : List(l.begin(), l.end()) {}
// delete all ~List() { node *node = first; Node<T> *next; while (node != after_last) { next = node->next; delete node; node = next; } delete after_last; }
node *prev_node = next_node->prev; new_node->prev = prev_node; if (prev_node) prev_node->next = new_node; else // it was the first node first = new_node;
le 17/04/2015 à 21:20, Lucas Levrel a écrit dans le message
<alpine.LNX.2.11.1504172108590.1699@localhost> :
template<typename T> class Node_iter {
friend List<T>;
Node<T> *node; // le noeud actuel
public:
// opérateurs *, ->, ==, !=, ++, --, etc.
};
Au début j'étais parti sur :
L'adresse du noeud précédent le premier est égale à 0
L'adresse du noeud suivant le dernier est égale à 0
Seulement, si je fais cela, je ne peux plus faire la conversion
itérateur -> élément car end() renvoie un iterator où node = 0, du coup
on ne peut pas faire -- dessus (-- revoit un itérateur ou node = node->prev).
Est-ce qu'il n'y a pas moyen de mettre un drapeau dans Node_iter pour
particulariser le cas "end", et mettre un test dans -- ? (Il faudrait
que Node_iter soit friend de List, je suppose.)
Actuellement, j'ai :
Node_iter& operator--() { n = n->prev; return *this; }
Node_iter operator--(int) { Node_iter old = *this; --(*this); return old; }
Il faut donc que n existe sinon ça fait boum sur n->prev.
Tu suggères donc d'ajouter un variable membre dans Node_iter contenant
l'adresse de la liste et de faire un truc comme :
Node_iter& operator--() {
if (n == 0)
n = l->last // List *l;
else
n = n->prev;
return *this;
}
Pourquoi pas mais ça m'oblige à créer les itérateurs non plus comme
iterator(first);
mais comme
iterator(this, first);
Plus j'y réfléchi, plus je me dis que la seule solution est de créer un
noeud sans donnée et qu'il me servira de "noeud après le dernier", c'est
à dire que je remplace le membre de List last par after_last. Mais, du
coup, une liste vide contient toujours un noeud.
Ça ne me choque pas vraiment, pour un objet qui doit grossir à la
demande, d'avoir une case « en attente ». D'ailleurs vector a une
notion de capacité distincte de sa taille, pour des raisons de
performances, non ?
Oui mais, autant avec un vector, je comprends le besoin d'allouer un
grand espace d'un coup pour éviter de faire des copies à chaque fois
qu'il grandit, autant sur une liste qui va chercher une case mémoire
n'importe où, je ne vois pas l'intérêt.
J'ai réussi à m'en sortir et ça semble bien fonctionner comme ça, c'est
à dire en créant un noeud sans donnée qui reste pendant toute la durée
de vie de la liste le "noeud après le dernier". Ce n'est pas fini mais
pour les plus courageux, voici où j'en suis, toute remarque est
bienvenue (c'est du C++11) :
// create an empty list
List() : first(new node), after_last(first), nb_node(0) {}
// create a list with n elements ; each element is a copy of data
List(int n, const T& data) : List() {
for (auto i = 0; i < n; ++i)
push_back(data);
}
// create a list with a copy of [b, e)
List(iterator b, iterator e) : List() {
for (auto it = b; it != e; ++it)
push_back(*it);
}
// create a copy of l
List(const List& l) : List(l.begin(), l.end()) {}
// delete all
~List() {
node *node = first;
Node<T> *next;
while (node != after_last) {
next = node->next;
delete node;
node = next;
}
delete after_last;
}
node *prev_node = next_node->prev;
new_node->prev = prev_node;
if (prev_node)
prev_node->next = new_node;
else // it was the first node
first = new_node;
le 17/04/2015 à 21:20, Lucas Levrel a écrit dans le message :
template<typename T> class Node_iter { friend List<T>; Node<T> *node; // le noeud actuel public: // opérateurs *, ->, ==, !=, ++, --, etc. };
Au début j'étais parti sur : L'adresse du noeud précédent le premier est égale à 0 L'adresse du noeud suivant le dernier est égale à 0 Seulement, si je fais cela, je ne peux plus faire la conversion itérateur -> élément car end() renvoie un iterator où node = 0, du coup on ne peut pas faire -- dessus (-- revoit un itérateur ou node = node->prev).
Est-ce qu'il n'y a pas moyen de mettre un drapeau dans Node_iter pour particulariser le cas "end", et mettre un test dans -- ? (Il faudrait que Node_iter soit friend de List, je suppose.)
Actuellement, j'ai : Node_iter& operator--() { n = n->prev; return *this; } Node_iter operator--(int) { Node_iter old = *this; --(*this); return old; } Il faut donc que n existe sinon ça fait boum sur n->prev.
Tu suggères donc d'ajouter un variable membre dans Node_iter contenant l'adresse de la liste et de faire un truc comme : Node_iter& operator--() { if (n == 0) n = l->last // List *l; else n = n->prev; return *this; }
Pourquoi pas mais ça m'oblige à créer les itérateurs non plus comme iterator(first); mais comme iterator(this, first);
Plus j'y réfléchi, plus je me dis que la seule solution est de créer un noeud sans donnée et qu'il me servira de "noeud après le dernier", c'est à dire que je remplace le membre de List last par after_last. Mais, du coup, une liste vide contient toujours un noeud.
Ça ne me choque pas vraiment, pour un objet qui doit grossir à la demande, d'avoir une case « en attente ». D'ailleurs vector a une notion de capacité distincte de sa taille, pour des raisons de performances, non ?
Oui mais, autant avec un vector, je comprends le besoin d'allouer un grand espace d'un coup pour éviter de faire des copies à chaque fois qu'il grandit, autant sur une liste qui va chercher une case mémoire n'importe où, je ne vois pas l'intérêt.
J'ai réussi à m'en sortir et ça semble bien fonctionner comme ça, c'est à dire en créant un noeud sans donnée qui reste pendant toute la durée de vie de la liste le "noeud après le dernier". Ce n'est pas fini mais pour les plus courageux, voici où j'en suis, toute remarque est bienvenue (c'est du C++11) :
// create an empty list List() : first(new node), after_last(first), nb_node(0) {}
// create a list with n elements ; each element is a copy of data List(int n, const T& data) : List() { for (auto i = 0; i < n; ++i) push_back(data); }
// create a list with a copy of [b, e) List(iterator b, iterator e) : List() { for (auto it = b; it != e; ++it) push_back(*it); }
// create a copy of l List(const List& l) : List(l.begin(), l.end()) {}
// delete all ~List() { node *node = first; Node<T> *next; while (node != after_last) { next = node->next; delete node; node = next; } delete after_last; }
node *prev_node = next_node->prev; new_node->prev = prev_node; if (prev_node) prev_node->next = new_node; else // it was the first node first = new_node;