L'élément après le dernier sur une liste

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
Ἕν οἶδα ὅτι οὐδὲν οἶδα (Σωκράτης)

Bonjour,

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) :

template <typename T> struct Node {
T *data = 0;
Node *prev = 0;
Node *next = 0;

Node() {}
~Node() { delete data; }
Node(const T& data) : data(new T(data)) {}
Node(const Node& n) : Node(n.data) {}
Node& operator=(const Node& n) {
delete data;
data = new T(n.data);
}
};

template <typename T> class List;

template <typename T> struct Node_iter {
friend List<T>;

T& operator*() { return *n->data; }
T* operator->() { return n->data; }

bool operator==(Node_iter rhs) { return n == rhs.n; }
bool operator!=(Node_iter rhs) { return n != rhs.n; }

Node_iter& operator++() { n = n->next; return *this; }
Node_iter operator++(int) {
Node_iter old = *this; ++(*this); return old;
}

Node_iter& operator--() { n = n->prev; return *this; }
Node_iter operator--(int) {
Node_iter old = *this; --(*this); return old;
}

private:
Node<T> *n = 0;
Node_iter() {}
Node_iter(Node<T> *n) : n(n) {}
};

#include <cstddef> // ptrdiff_t, size_t
#include <algorithm> // reverse_iterator

template <typename T> class List {
public:
typedef const Node_iter<T> const_iterator;
typedef const T& const_reference;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef Node_iter<T> iterator;
typedef T& reference;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::size_t size_type;
typedef T value_type;

// 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;
}

const List<T>& operator=(const List<T>& l) {
// XXX
}

reference front() { return *first->data; }
const_reference front() const { return *first->data; }

reference back() { return *after_last->prev->data; }
const_reference back() const { return *after_last->prev->data; }

// insert data before pos
void insert(iterator pos, const value_type& data) {
node *new_node = new node(data);
++nb_node;

node *next_node = pos.n;
new_node->next = next_node;

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;

next_node->prev = new_node;
}

void push_back(const value_type& data) { insert(end(), data); }
void push_front(const value_type& data) { insert(begin(), data); }

// delete element at pos, return an iterator on the next element
iterator erase(iterator pos) {
if (pos == end())
return pos;

node *n = pos.n;
node *prev = n->prev;
node *next = n->next;

next->prev = prev;
if (prev)
prev->next = next;
else
first = next;

delete n;
--nb_node;
return iterator(next);
}

size_type size() { return nb_node; }
bool empty() { return nb_node == 0; }

iterator begin() { return iterator(first); }
const_iterator begin() const { return iterator(first); }

iterator end() { return iterator(after_last); }
const_iterator end() const { return iterator(after_last); }

private:
typedef Node<T> node;

node *first = 0;
node *after_last = 0;
size_t nb_node = 0;
};

--
Benoit Izac