Lista podwójnie połączona z inteligentnymi wskaźnikami: problemy z metodą wstawiania
Próbuję zaimplementować listę podwójnie połączoną z szablonem, postępując zgodnie z książką Stroustrupa „Zasady i praktyka przy użyciu C ++”, rozdział 20.4. Zamiast surowych wskaźników chcę użyć unikalnych wskaźników . Kod jest zorganizowany w następujący sposób:
- nagłówek Node.h, w którym zaimplementowano strukturę
Node
: aunique_pointer
jest używany dla następnego węzła, a surowy dla poprzedniego - nagłówek Iterator.h, gdzie
Iterator
jest zaimplementowany - nagłówek List.h, gdzie klasa
List
jest zaimplementowana - main.cpp, w którym testowane są metody
Widziałem, że były inne dość podobne pytania, takie jak to, ale nie wiem, czy projekt mojej metody wstawiania: iterator insert(iterator p, const T& x)
jest w porządku . W szczególności otrzymuję błąd segmentacji, gdy dzwonię auto it3 = insert(--p,4)
. Czy to w porządku, czy powinienem to naprawić?
Oto mój 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 */
Następnie mamy 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 */
Oto nagłówek 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;
}
};
Na koniec mamy plik main.cpp z testami:
#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;
}
EDYCJA :
Poprawiona wersja 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;
}
Odpowiedzi
Masz wiele problemów z zarządzaniem pamięcią na tej połączonej liście. Kluczową rzeczą do zapamiętania jest to, że unique_ptr
wskazuje na własność obiektu. Zastosowanie release
, reset
oraz w mniejszym stopniu get
są zapach kod: nie zawsze jest źle, ale często wskazanie, że klasa jest używana nieprawidłowo. Zwykle swap
zamiast tego powinieneś użyć i przenieść przypisanie. Wywołam je podczas przeglądania plików.
Krótka uwaga: nie testowałem ani nawet nie skompilowałem następującego kodu; może zawierać błędy.
Node.h
To jest w większości w porządku. Konstruktor "copy" ( Node(std::unique_ptr<Node>&)
) prawdopodobnie powinien zostać po prostu usunięty. Kopiowanie węzła i wszystkich jego potomków nie ma sensu. Nawet jeśli chciałeś takiego zachowania, ta implementacja jest błędna. Usuwa wszystkie poprzednie linki, dzięki czemu masz listę pojedynczo połączoną, która udaje listę podwójnie połączoną.
Iterator.h
Twoja klasa iteratora nie jest całkiem poprawna. Nie działa jako end
iterator. W szczególności --l.end()
wykazuje niezdefiniowane zachowanie, ponieważ odwołuje się do pustego wskaźnika. W praktyce klasy iteratorów zwykle wymagają odwołania do kolekcji, z której pochodzą.
Ponadto ten iterator nie spełnia wymagań iteratora dwukierunkowego (wiem, że oznaczyłeś to jako iterator do przodu, ale również nie spełnia tych wymagań). W szczególności narusza:
- „wartości typu spełnia Swapable”; Jestem trochę zardzewiały, ale jestem prawie pewien, że twój destruktor zadeklarowany przez użytkownika zapobiega generowaniu niejawnie zadeklarowanego konstruktora przenoszenia i operatora przypisania przenoszenia; musisz dostarczyć te funkcje (np. używając
= default
) lubswap
funkcję. - Nie obsługuje operatorów zwiększania i zmniejszania przyrostka.
List.h
List::last
tak naprawdę nie jest poprawnie zaimplementowany. O ile mogę się zorientować, nigdy nie jest ustawiony na nic innego niż nullptr
kod, jaki jest. W każdym razie nie powinno to być a unique_ptr
, ponieważ wszystko, na co wskazuje, jest już własnością innego unique_ptr
.
Więc przejdźmy last
do Node::Node<T>*
. Mamy następujące niezmienniki, które są prawdziwe przed i po każdym wyjść funkcyjnych członkiem: if _size == 0
, first==last==nullptr
. Inaczej,
first
wskazuje na pierwszy węzeł na liściefirst->previous == nullptr
- Biorąc pod uwagę osiągalny węzeł
n
,n->next
ma wartość null lubn->next.get() == n->next->previous
last
wskazuje ostatni osiągalny węzeł na liście.last.next
jest null._size
węzły są osiągalne.
Musimy napisać nasze funkcje składowe, aby te niezmienniki pozostały prawdziwe.
go_to
zwykle można osiągnąć poprzez zastosowanie się std::nextdo iteratora początkowego. To ma różnicę w zachowaniu, kiedy próbujesz przekroczyć koniec listy; użycie std::next
spowodowałoby w tym przypadku niezdefiniowane zachowanie. Jeśli chcesz mieć obecne zachowanie, możesz zaimplementować je za pomocą czegoś takiego jak
iterator go_to(const int n) const {
if (n >= _size) {
return end();
} else {
return std::next(begin(), n);
}
}
Kiedy używasz unique_ptr
do zarządzania pamięcią, generalnie nie powinieneś używać new
. Zamiast tego użyj, std::make_unique
jeśli używasz C ++ 14 lub nowszego (i napisz własne make_unique
w C ++ 11). Pozwala to poprawić bezpieczeństwo wyjątków w Twoim kodzie. Wypróbuj to dla 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;
}
Tutaj węzeł jest tworzony w sposób bezpieczny dla wyjątków. Nie ma szans na wyciek first
, ponieważ go nie udostępniamy (twój kod wyciekłby, first
gdyby alokacja się nie powiodła lub jeśli Node
konstruktor wyrzucił (z powodu T
wyrzucenia konstruktora przeniesienia)). Zakładając, że twoje operacje swap
i move
nie są rzucane, albo się push_front
powiedzie, a nowy element został wstawiony na początku, albo alokacja nie powiedzie się, push_front
zgłasza się, a struktura danych nie została zmieniona.
Jeśli push_back
nie używasz last
tutaj, nie ma powodu, aby last
w ogóle mieć .
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;
}
Ponownie zapewniamy, że niezmienniki klasy są zachowane, nawet jeśli rzucimy podczas konstruowania nowego węzła.
Myślę, że nie substitute
jest to rozsądna funkcja. Użytkownik listy powinien napisać *it = x;
i powinien wiedzieć, czy jego iterator jest prawidłowy, czy nie.
Normalna semantyka dla insert
to wstawianie wartości tuż przed przekazanym iteratorem, a nie tuż po. Pozwala to insert
na wstawianie w dowolnym miejscu listy i oznacza, że insert
ma sensowną semantykę, gdy end()
jest przekazywana jako iterator.
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());
}
Przenieś się class Node
i struct __iterator
doclass List
Widok Node::Node<T>
wewnątrz kodu jest bardzo dziwny . A Node
jest szczegółem implementacji twojego List
, więc powinien być zadeklarowany w środku class List
. To samo dotyczy __iterator
. Na przykład:
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() {...};
...
};
Zwróć uwagę, jak to wszystko pozwala uniknąć konieczności wprowadzania namespace
s lub __
przedrostków ( których powinieneś unikać ), aby je ukryć, i jak to zmniejsza liczbę przypadków, w których musisz jawnie pisać <T>
. Oczywiście teraz wszystko musi być zadeklarowane w środku List.h
, ale nie uważam tego za wadę.
Myślę, że powinieneś postępować zgodnie ze standardem C ++ insert
dla kontenerów , na przykład przekazując a begin
i end
iterator
template<typename T>
void insert(Iterator begin, Iterator begin2, Iterator end2);
void insert(Iterator begin, T value);