Nous nous intéressons à un containeur que nous implantons comme une liste simplement chaînée.
#include<exception> #include<iostream> #include<memory> template<typename T> class List { private: struct Node { private: T m_value; Node* m_next_node; public: Node(T aValue): Node(aValue, NULL) {} Node(T aValue, Node* theNextNode): m_value(aValue), m_next_node(theNextNode) {} void insert_after(T aValue) { m_next_node = new Node(aValue, m_next_node); } Node* next() { return m_next_node; } T& value() { return m_value; } T value() const { return m_value; } }; Node* m_front; Node* m_back; public: List(): m_front(NULL), m_back(NULL) {} void push_front(T value) { if(m_front == NULL) { m_front = new Node(value); m_back = m_front; } else m_front = new Node(value, m_front); } void push_back(T value) { if(m_back == NULL) { m_front = new Node(value); m_back = m_front; } else { m_back->insert_after(value); m_back = m_back->next(); } } };
Proposez un destructeur qui détruit bien tous les éléments stockés dans la liste avant de détruire la liste.
Nous aimerions ajouter des itérateurs. Pour ce faire, nous proposons la classe suivante d’itérateurs qui fait référence au nœud de la liste.
class List { public: ... class iterator: std::iterator<std::forward_iterator_tag, T> { private: Node* m_current; public: iterator(Node* node): m_current(node) {} iterator& operator++() { if(m_current != NULL) m_current = m_current .next(); return *this; } iterator operator++(int) { auto result = iterator(*this); if(m_current != NULL) m_current = m_current->next(); return result; } reference operator *() { return m_current->value(); } pointer operator ->() { return &m_current.value(); } bool operator == (const iterator& another) { return m_current == another.m_current; } bool operator != (const iterator& another) { return m_current != another.m_current; } }; ... }
Ajouter les méthodes begin
et end
à la liste.
Est-il possible d’utiliser des std::unique_ptr
en lieu et place des pointeurs natifs de C++, expliquer pourquoi ?
Est-il possible d’utiliser des std::shared_ptr
en lieu et place des pointeurs natifs de C++, expliquer pourquoi ?
Réécrivez la classe avec des std::shared_ptr
. Avons-nous toujours besoin d’un destructeur ?
Nous souhaitons désormais imposer une sémantique qui est assez habituelle lorsque nous manipulons des itérateurs. Un itérateur est invalidé quand la collection sous-jacente est modifiée. La technique la plus classique pour déterminer si un containeur a été modifiée, consister à ajouter un numéro de version au containeur, souvent représenté par un nombre entier non-signé, qui est incrémenté chaque fois que le containeur est modifié. Lors que l’itérateur cherche à accéder à un élément, il vérifie que le numéro de version correspond au numéro de version qu’il a obtenu lors de sa création, si ce n’est pas le cas, l’itérateur déclenche une exception.
Modifier le code du containeur List
pour intégrer les fonctionnalités suivantes :
List
doit définir un champ qui contient le numéro de version du containeur. Le champ est supporté être à zéro lors de l’initialisation du containeur.invalid_iterator
et dérivant de std::exception
.Cependant, le code précédent n’est pas optimal. En effet, quand le containeur est détruit et qu’un itérateur faisant référence au containuer existe encore, l’itérateur va pour pouvoir d’abord vérifier le numéro de version. Cependant si la liste a été supprimé, le champ correspondant au numéro de version n’est plus accessible et nous aurons une erreur d’accès qui va se produire à ce moment.
Pour ce faire, nous souhaitons pouvoir garantir deux comportements :
C++ introduit une classe dénommée ''%%std::weak_ptr%%''. À la différence de std::unique_ptr
ou std::shared_ptr
, un std::weak_ptr
ne garantit pas que l’élément auquel il fait référence est accessible. Pour pouvoir accéder à un objet, il faut verrouiller l’accès en utilisant la méthode ''%%lock%%''/ Cette méthode retourne un std::shared_ptr
qui soit fait référence à l’élément si cette référence est encore actuelle ou fait référence à NULL
si la référence est devenue obsolète. La méthode ''%%expired%%'' indique si la référence à l’élément est devenue obsolète.
Désormais, si nous souhaitons implanter un itérateur qui détermine si la collection n’a pas été modifiée, cela impose :