Doppelte verknüpfte Liste mit intelligenten Zeigern: Probleme mit der Einfügemethode
Ich versuche, eine doppelt verknüpfte Liste mit Vorlagen zu implementieren, indem ich Stroustrups Buch "Prinzipien und Praxis mit C ++", Kapitel 20.4, folge. Anstelle von rohen Zeigern möchte ich eindeutige Zeiger verwenden . Der Code ist wie folgt organisiert:
- Header Node.h, in dem die Struktur
Nodeimplementiert ist: aunique_pointerwird für den nächsten Knoten und ein roher für den vorherigen Knoten verwendet - Header Iterator.h wo das
Iteratorimplementiert ist - Header List.h, in der die Klasse
Listimplementiert ist - eine main.cpp, in der die Methoden getestet werden
Ich habe gesehen, dass es andere ziemlich ähnliche Fragen gab, wie diese, aber ich weiß nicht, ob das Design meiner Einfügemethode: iterator insert(iterator p, const T& x)in Ordnung ist . Insbesondere erhalte ich einen Segmentierungsfehler, wenn ich anrufe auto it3 = insert(--p,4). Ist das in Ordnung oder sollte ich das beheben?
Hier ist mein 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 */
Dann ist hier der 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 */
Hier ist der Header 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;
}
};
Zum Schluss hier die Datei main.cpp mit den 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;
}
EDIT :
Korrigierte Version von 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;
}
Antworten
Sie haben eine Reihe von Problemen mit der Speicherverwaltung in dieser verknüpften Liste. Der Schlüssel zum Erinnern ist, dass unique_ptrdas Eigentum an einem Objekt angezeigt wird. Die Verwendung von release, resetund in geringerem Maße getist ein Code Geruch: nicht immer falsch, aber häufig ein Hinweis darauf , dass die Klasse nicht richtig verwendet wird. Normalerweise sollten Sie swapstattdessen eine Zuweisung verwenden. Ich werde diese aufrufen, während ich die Dateien durcharbeite.
Ein kurzer Hinweis: Ich habe den folgenden Code nicht getestet oder sogar kompiliert. Es kann einige Fehler enthalten.
Node.h
Das ist meistens in Ordnung. Der Konstruktor "copy" ( Node(std::unique_ptr<Node>&)) sollte wahrscheinlich nur entfernt werden. Es ist nicht wirklich sinnvoll, einen Knoten und alle seine Nachkommen zu kopieren. Selbst wenn Sie dieses Verhalten wollten, ist diese Implementierung fehlerhaft. Es werden alle vorherigen Links entfernt, sodass Sie eine einfach verknüpfte Liste haben, die vorgibt, eine doppelt verknüpfte Liste zu sein.
Iterator.h
Ihre Iteratorklasse ist nicht ganz richtig. Es funktioniert nicht als endIterator. Zeigt insbesondere --l.end()undefiniertes Verhalten, da es einen Nullzeiger dereferenziert. In der Praxis benötigen Iteratorklassen in der Regel einen Verweis auf die Sammlung, aus der sie stammen.
Darüber hinaus erfüllt dieser Iterator nicht die Anforderungen eines bidirektionalen Iterators (ich weiß, dass Sie dies als Vorwärtsiterator markieren, aber er erfüllt diese Anforderungen auch nicht). Insbesondere verstößt es gegen:
- "Werte vom Typ Es erfüllt Swappable"; Ich bin hier etwas verrostet, aber ich bin mir ziemlich sicher, dass Ihr vom Benutzer deklarierter Destruktor verhindert, dass der implizit deklarierte Verschiebungskonstruktor und der Verschiebungszuweisungsoperator generiert werden. Sie müssen entweder diese Funktionen (z. B. using
= default) oder eineswapFunktion bereitstellen . - Die Postfix-Inkrementierungs- und Dekrementierungsoperatoren werden nicht unterstützt.
List.h
List::lastist nicht wirklich richtig implementiert. Soweit ich das beurteilen kann, ist es nie auf etwas anderes eingestellt als nullptrdurch den Code, wie er ist. In jedem Fall sollte dies kein sein unique_ptr, da alles, worauf es hinweist, bereits einem anderen gehört unique_ptr.
Wechseln wir also lastzu a Node::Node<T>*. Wir haben die folgenden Invarianten, die vor und nach dem Beenden jeder Mitgliedsfunktion wahr sind: Wenn _size == 0, first==last==nullptr. Andernfalls,
firstzeigt auf den ersten Knoten in der Listefirst->previous == nullptr- Bei einem gegebenen Knoten erreichen
n,n->nextist null odern->next.get() == n->next->previous lastzeigt auf den letzten erreichbaren Knoten in der Liste.last.nextist Null._sizeKnoten sind erreichbar.
Wir müssen unsere Mitgliedsfunktionen schreiben, damit diese Invarianten wahr bleiben.
go_towürde normalerweise durch Anwenden std::nextauf den Anfangsiterator erreicht werden. Das hat einen Unterschied im Verhalten, wenn Sie versuchen, das Ende der Liste zu überschreiten. Die Verwendung std::nextwürde in diesem Fall zu einem undefinierten Verhalten führen. Wenn Sie das aktuelle Verhalten möchten, können Sie es mit so etwas implementieren
iterator go_to(const int n) const {
if (n >= _size) {
return end();
} else {
return std::next(begin(), n);
}
}
Wenn Sie unique_ptrSpeicher verwalten, sollten Sie diesen generell nicht verwenden new. Verwenden std::make_uniqueSie stattdessen, wenn Sie C ++ 14 oder höher verwenden (und schreiben Sie Ihr eigenes make_uniquein C ++ 11). Auf diese Weise können Sie die Ausnahmesicherheit Ihres Codes verbessern. Versuchen Sie dies für 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;
}
Hier wird der Knoten ausnahmesicher erstellt. Es besteht keine Möglichkeit eines Lecks first, da wir es nicht freigeben (Ihr Code würde auslaufen, firstwenn die Zuordnung fehlschlägt oder wenn der Konstruktor geworfen hat Node(aufgrund des Auslösens des TBewegungskonstruktors)). Angenommen, Ihre swapund moveNo-Throw-Operationen sind push_fronterfolgreich, und das neue Element wurde zu Beginn eingefügt, oder die Zuordnung schlägt fehl, push_frontwirft und die Datenstruktur wurde nicht geändert.
Was push_back, du , wenn du nicht mit lasthier, gibt es keinen Grund zu haben , lastüberhaupt nicht .
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;
}
Auch hier stellen wir sicher, dass die Invarianten der Klasse gültig sind, auch wenn wir beim Erstellen des neuen Knotens werfen.
Ich denke nicht, dass dies substituteeine vernünftige Funktion ist. Der Benutzer Ihrer Liste sollte schreiben *it = x;und wissen, ob sein Iterator gültig ist oder nicht.
Die normale Semantik für insertbesteht darin, einen Wert unmittelbar vor dem Übergeben des Iterators einzufügen , nicht erst danach. Dies ermöglicht insertdas Einfügen an einer beliebigen Position in der Liste und bedeutet, dass inserteine sinnvolle Semantik vorliegt, wenn sie end()als Iterator übergeben wird.
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());
}
Bewegen Sie sich class Nodeund struct __iteratorinclass List
Es ist sehr seltsam, Node::Node<T>in den Code zu sehen. A Nodeist ein Implementierungsdetail von Ihnen List, daher sollte es im Inneren deklariert werden class List. Das gilt auch für __iterator. Beispielsweise:
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() {...};
...
};
Beachten Sie, wie all dies vermeidet, dass namespaces oder __Präfixe eingeführt werden müssen ( die Sie vermeiden sollten ), um sie auszublenden, und wie dies die Häufigkeit verringert, mit der Sie explizit schreiben müssen <T>. Natürlich muss jetzt alles drinnen deklariert werden List.h, aber ich sehe das nicht als Nachteil.
Ich denke, Sie sollten dem C ++ - Standard insertfür Container folgen, indem Sie beispielsweise einen beginund einen endIterator übergeben
template<typename T>
void insert(Iterator begin, Iterator begin2, Iterator end2);
void insert(Iterator begin, T value);