Double liste liée avec des pointeurs intelligents: problèmes avec la méthode d'insertion
J'essaie d'implémenter une liste double liée basée sur un modèle, en suivant le livre de Stroustrup "Principes et pratique en utilisant C ++", chapitre 20.4. Au lieu de pointeurs bruts, je souhaite utiliser des pointeurs uniques . Le code est organisé comme suit:
- header Node.h où la structure
Nodeest implémentée: ununique_pointerest utilisé pour le nœud suivant, et un brut pour le précédent - header Iterator.h où
Iteratorest implémenté - header List.h où la classe
Listest implémentée - un main.cpp où les méthodes sont testées
J'ai vu qu'il y avait eu d'autres questions assez similaires, comme celle-ci, mais je ne sais pas si la conception de ma méthode d'insertion: iterator insert(iterator p, const T& x)est correcte . En particulier, j'obtiens un défaut de segmentation si j'appelle auto it3 = insert(--p,4). Est-ce que ça va ou dois-je résoudre ce problème?
Voici mon Node.h
#ifndef Node_h
#define Node_h
#include <algorithm>
#include <iostream>
#include <memory> // std::unique_ptr
#include <utility> // std::move
namespace Node {
template <typename T>
struct Node {
T data;
std::unique_ptr<Node> next;
Node* previous;
Node() noexcept = default;
explicit Node(const T& _data) : data{_data}, next{nullptr},previous{nullptr} {
std::cout << "l-value"<<std::endl;
}
Node(const T& _data, Node* _next, Node* _previous): data{_data}, next{_next}, previous{_previous} {}
explicit Node(T&& x) : data{std::move(x)} {
std::cout << "r-value" << std::endl;
}
Node(T&& x, Node* _next, Node* _previous) : data{std::move(x)}, next{_next}, previous{_previous} {
std::cout << "r-value" << std::endl;
}
explicit Node(const std::unique_ptr<Node> &x) : data{x->data} {
if (x->next){
next.reset(new Node{x->next});
}
// if (x->previous){
// previous.reset(new Node{x->previous});
// }
}
~Node()=default;
//Move semantics, Copy semantics
void printNode(){
std::cout << "Data is: " << data <<"\n";
}
};
} //end namespace
#endif /* Node_h */
Ensuite, voici le Iterator.h
#ifndef Iterator_h
#define Iterator_h
#include "Node.h"
#include <iterator>
template <typename T >
struct __iterator {;
using NodeT = Node::Node<T>;
NodeT* current;
//public:
using value_type = T;
using difference_type = std::ptrdiff_t;
using iterator_category = std::forward_iterator_tag;
using reference = value_type&;
using pointer = value_type *;
explicit __iterator(NodeT* p) : current{p} {}
__iterator() noexcept=default;
~__iterator()=default;
reference operator*() const noexcept{
return current->data;
}
pointer operator->() const noexcept{
return &**this;
}
__iterator& operator++() {
current = current->next.get();
return *this;
}
__iterator& operator--(){
current=current->previous; //previous is just a raw pointer
return *this;
}
friend bool operator==(__iterator &a, __iterator &b) {
return a.current == b.current;
}
friend bool operator!=(__iterator &a, __iterator &b) { return !(a == b); }
};
#endif /* Iterator_h */
Voici l'en-tête List.h
#include "Iterator.h"
#include <cassert>
template <typename T>
class List {
private:
std::unique_ptr<Node::Node<T>> first;
std::unique_ptr<Node::Node<T>> last;
int _size;
public:
using iterator = __iterator<T>;
iterator begin(){return iterator{first.get()};}
iterator end(){return iterator{nullptr};} //one past the last
iterator go_to(const int n){
assert(n>=0);
int i=0;
if (n < _size) {
auto tmp{begin()};
while (i<n) {
++tmp;
++i;
}
return tmp;
}else{
return iterator{nullptr};
}
}
List() : first{nullptr}, last{nullptr},_size{0} {}
~List() noexcept = default;
template <typename O>
void push_front(O &&x) { // forwarding ref. not r-value
first.reset(new Node::Node<T>{std::forward<O>(x),first.release(),nullptr});
if (_size==0) {
last.reset(nullptr);
}
++_size;
}
template <typename O> //forward reference
void push_back(O&& x){
auto tmp = first.get();
auto _node = new Node::Node<T>{std::forward<O>(x)};
if (!tmp) {
first.reset(_node);
return;
}
while (tmp->next) {
tmp = tmp->next.get();
}
tmp->next.reset(_node);
++_size;
}
iterator substitute(iterator p, const T& x){
//_size must not be incremented!
iterator tmp{p};
if(tmp.current){
*tmp = x;
return tmp;
}else{
return iterator{nullptr};
}
}
iterator insert(iterator position,const T& value) {
auto newNode = new Node::Node<T>(value, position.current->next.get(), position.current);
std::cout << position.current << std::endl;
if (position.current == last.get() ) {
last.reset(newNode);
}
position.current->next.release(); //otherwise: "pointer being freed was not allocated"
position.current->next.reset(newNode); //set next of previous node to newNode
++_size;
return position;
}
friend std::ostream& operator<<(std::ostream& os, List& l){
auto itStop = l.end();
os << "The list has " << l._size << " elements"<<"\n";
for (auto it = l.begin(); it!=itStop; ++it) {
os<< *it << " ";
}
return os;
}
};
Enfin, voici le fichier main.cpp avec les tests:
#include "List.h"
int main() {
List<int> l{};
int i=8;
l.push_front(i); //l-value
l.push_back(4); //r-value
l.push_back(i+2); //r-value
l.push_back(95); //r-value
l.push_front(29); //l-value
l.push_front(i*i); //r-value
std::cout << "My list so far: " << l<<std::endl;
auto p{l.go_to(3)};
auto itt = l.substitute(p, 29);
std::cout << "My list after substitution: \t" << l<<std::endl;
auto pp{l.go_to(2)};
auto it2 = l.insert(pp,98);
std::cout << "My list after insertion: \t" << l<<std::endl;
auto it3= l.insert(--pp,998);
std::cout << "My list after insertion: \t" << l<<std::endl;
return 0;
}
MODIFIER :
Version corrigée de push_front:
template <typename O>
void push_front(O&& x) {
auto node = std::make_unique<Node::Node<T>>(std::forward<O>(x));
std::swap(node, first);
first->next = std::move(node);
if (_size == 0) {
assert(!last);
assert(!first->next);
last = first.get();
}else{
first->next->previous = first.get()
}
++_size;
}
Réponses
Vous rencontrez un certain nombre de problèmes de gestion de la mémoire dans cette liste chaînée. La chose clé à retenir est que cela unique_ptrindique la propriété d'un objet. L'utilisation de release, resetet dans une moindre mesure getest une odeur de code: pas toujours erronée, mais souvent une indication que la classe est utilisée de manière incorrecte. Habituellement, vous devriez utiliser swapet déplacer-affectation à la place. Je vais les appeler pendant que je travaille sur les fichiers.
Une note rapide: je n'ai pas testé ni même compilé le code suivant; il peut contenir des erreurs.
Node.h
C'est généralement bien. Le constructeur "copy" ( Node(std::unique_ptr<Node>&)) devrait probablement être simplement supprimé. Cela n'a pas vraiment de sens de copier un nœud et tous ses descendants. Même si vous vouliez ce comportement, cette implémentation est boguée. Il supprime tous les liens précédents, de sorte que vous ayez une liste à lien unique qui prétend être une liste à double lien.
Iterator.h
Votre classe d'itérateur n'est pas tout à fait correcte. Cela ne fonctionne pas comme un enditérateur. En particulier, --l.end()présente un comportement non défini car il déréférence un pointeur nul. En pratique, les classes itératrices ont tendance à avoir besoin d'une référence à la collection dont elles proviennent.
De plus, cet itérateur ne répond pas aux exigences d'un itérateur bidirectionnel (je sais que vous le marquez comme un itérateur avant, mais il ne répond pas non plus à ces exigences). En particulier, il viole:
- "lvalues de type It satisfont Swappable"; Je suis un peu rouillé ici mais je suis presque sûr que votre destructeur déclaré par l'utilisateur empêche le constructeur de déplacement et l'opérateur d'affectation de déplacement déclarés implicitement d'être générés; vous devez fournir ces fonctions (par exemple en utilisant
= default) ou uneswapfonction. - Il ne prend pas en charge les opérateurs d'incrémentation et de décrémentation postfix.
List.h
List::lastn'est pas vraiment implémenté correctement. Autant que je sache, il n'est jamais défini sur autre chose que nullptrpar le code tel quel . Dans tous les cas, cela ne devrait pas être un unique_ptr, car tout ce qu'il pointe appartient déjà à un autre unique_ptr.
Alors passons lastà un Node::Node<T>*. Nous avons les suivants invariants qui sont vraies avant et après chaque sortie de la fonction de membre: Si _size == 0, first==last==nullptr. Autrement,
firstpointe vers le premier nœud de la listefirst->previous == nullptr- Étant donné un nœud accessible
n,n->nextest nul oun->next.get() == n->next->previous lastpointe vers le dernier nœud accessible de la liste.last.nextest nul._sizeles nœuds sont accessibles.
Nous devons écrire nos fonctions membres pour que ces invariants restent vrais.
go_toserait généralement réalisé en appliquant std::nextà l'itérateur de début. Cela a une différence de comportement lorsque vous essayez de dépasser la fin de la liste; l'utilisation std::nextentraînerait un comportement indéfini dans ce cas. Si vous voulez le comportement actuel, vous pouvez l'implémenter avec quelque chose comme
iterator go_to(const int n) const {
if (n >= _size) {
return end();
} else {
return std::next(begin(), n);
}
}
Lorsque vous utilisez unique_ptrpour gérer la mémoire, vous ne devez généralement pas utiliser new. À la place, utilisez std::make_uniquesi vous utilisez C ++ 14 ou une version ultérieure (et écrivez le vôtre make_uniqueen C ++ 11). Cela vous permet d'améliorer la sécurité des exceptions de votre code. Essayez ceci pour push_front:
template <typename O>
void push_front(O&& x) {
auto node = std::make_unique<Node::Node<T>>(std::forward<O>(x));
swap(node, first); // assuming you implement swap or add a "using std::swap;" on the previous line
first->next = std::move(node);
if (_size == 0) {
assert(!last);
assert(!first->next);
last = first.get();
}
++_size;
}
Ici, le nœud est créé de manière sûre pour les exceptions. Il n'y a aucune chance de fuite first, puisque nous ne le publions pas (votre code fuirait firstsi l'allocation échouait ou si Nodele constructeur de la commande lançait (en raison du Tlancement du constructeur de déplacement)). En supposant que vos opérations swapet movesont no-throw, soit push_frontréussit, et le nouvel élément a été inséré au début, soit l'allocation échoue, se push_frontlance et la structure de données n'a pas été modifiée.
Quant à push_back, si vous n'utilisez pas lastici, il n'y a aucune raison d'avoir lastdu tout.
template <typename O>
void push_back(O&& x) {
auto node = std::make_unique<Node::Node<T>>(std::forward<O>(x));
if (_size == 0) {
assert(!last);
assert(!first);
first = std::move(node);
last = node.get();
_size = 1;
return;
}
assert(!last->next);
node->previous = last;
last->next = std::move(node);
last = last->next.get();
++_size;
}
Encore une fois, nous nous assurons que les invariants de la classe tiennent, même si nous lançons lors de la construction du nouveau nœud.
Je ne pense pas que ce substitutesoit une fonction raisonnable. L'utilisateur de votre liste doit écrire *it = x;et il doit savoir si son itérateur est valide ou non.
La sémantique normale pour insertest d'insérer une valeur juste avant l'itérateur passé, pas juste après. Cela permet insertd'insérer à n'importe quelle position dans la liste et cela signifie qu'il inserta une sémantique sensible quand end()est passé comme itérateur.
iterator insert(iterator it, const T& value) {
auto node = std::make_unique<Node::Node<T>>(value);
auto prev = it.current ? it.current->previous : last;
auto ptr = prev ? &first : &prev->next;
swap(*ptr, node);
(*ptr)->next = std::move(node);
(*ptr)->previous = prev;
++_size;
if (!last) last = first.get();
return iterator(ptr->get());
}
Se déplacer class Nodeet struct __iteratorentrerclass List
C'est très étrange de voir Node::Node<T>à l'intérieur du code. A Nodeest un détail d'implémentation de votre List, il doit donc être déclaré à l'intérieur class List. Il en va de même __iterator. Par exemple:
template<typename T>
class List {
class Node {
T data;
std::unique_ptr<Node> next;
Node *previous;
};
std::unique_ptr<Node> first;
std::unique_ptr<Node> last;
...
public:
class iterator {
Node *current;
public:
using value_type = T;
...
};
iterator begin() {...};
...
};
Remarquez comment tout cela évite d'avoir à introduire des namespaces ou des __préfixes ( ce que vous devriez éviter ) pour les masquer, et comment cela réduit le nombre de fois que vous devez écrire explicitement <T>. Bien sûr, maintenant tout doit être déclaré à l'intérieur List.h, mais je ne vois pas cela comme un inconvénient.
Je pense que vous devriez suivre la norme C ++ insertpour les conteneurs en passant un beginet un enditérateur, par exemple
template<typename T>
void insert(Iterator begin, Iterator begin2, Iterator end2);
void insert(Iterator begin, T value);