Double Linked List dengan smart pointers: masalah dengan metode penyisipan
Saya mencoba menerapkan Templated Double Linked List, mengikuti buku Stroustrup "Principles and Practice using C ++", Bab 20.4. Alih-alih petunjuk mentah, saya ingin menggunakan petunjuk unik . Kode tersebut diatur sebagai berikut:
- header Node.h dimana struct
Nodediimplementasikan: aunique_pointerdigunakan untuk node berikutnya, dan yang mentah untuk node sebelumnya - header Iterator.h tempat
Iteratordiimplementasikan - header List.h tempat kelas
Listdiimplementasikan - a main.cpp tempat metode diuji
Saya telah melihat bahwa ada pertanyaan lain yang cukup mirip, seperti ini tetapi saya tidak tahu apakah desain metode penyisipan saya: iterator insert(iterator p, const T& x)oke . Secara khusus, saya mendapatkan kesalahan segmentasi jika saya menelepon auto it3 = insert(--p,4). Apakah ini oke, atau haruskah saya memperbaikinya?
Ini Node.h saya
#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 */
Lalu, inilah 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 */
Inilah 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;
}
};
Terakhir, inilah file main.cpp dengan tes:
#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 :
Versi yang diperbaiki dari 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;
}
Jawaban
Anda memiliki sejumlah masalah dengan manajemen memori dalam daftar terkait ini. Hal utama yang perlu diingat adalah yang unique_ptrmenunjukkan kepemilikan suatu objek. Penggunaan release, resetdan pada tingkat lebih rendah getadalah kode bau: tidak selalu salah, tetapi sering merupakan indikasi bahwa kelas sedang digunakan secara tidak benar. Biasanya Anda harus menggunakan swapdan memindahkan tugas sebagai gantinya. Saya akan memanggil ini saat saya mengerjakan file.
Catatan singkat: Saya belum menguji atau bahkan mengkompilasi kode berikut; ini mungkin mengandung beberapa kesalahan.
Node.h
Ini sebagian besar baik-baik saja. Konstruktor "copy" ( Node(std::unique_ptr<Node>&)) mungkin harus dibuang. Tidaklah masuk akal untuk menyalin node dan semua turunannya. Bahkan jika Anda menginginkan perilaku itu, implementasi ini bermasalah. Ini menghapus semua tautan sebelumnya, sehingga Anda memiliki daftar tertaut tunggal yang berpura-pura menjadi daftar tertaut ganda.
Iterator.h
Kelas iterator Anda kurang tepat. Ini tidak berfungsi sebagai enditerator. Secara khusus, --l.end()menunjukkan perilaku tidak terdefinisi karena itu merujuk pada pointer nol. Dalam praktiknya, kelas iterator cenderung membutuhkan referensi ke koleksi asalnya.
Selain itu, iterator ini tidak memenuhi persyaratan iterator dua arah (saya tahu Anda menandainya sebagai iterator maju, tetapi iterator juga tidak memenuhi persyaratan tersebut). Secara khusus, ini melanggar:
- "lvalues of type It memuaskan Swappable"; Saya sedikit berkarat di sini tetapi saya cukup yakin destruktor yang dideklarasikan pengguna Anda mencegah konstruktor pemindahan yang dideklarasikan secara implisit dan memindahkan operator penugasan agar tidak dihasilkan; Anda harus menyediakan fungsi tersebut (misalnya menggunakan
= default) atauswapfungsi. - Ini tidak mendukung operator kenaikan dan penurunan postfix.
List.h
List::lasttidak benar-benar diterapkan dengan benar. Sejauh yang saya bisa mengerti, itu tidak pernah benar-benar diatur ke apa pun selain nullptroleh kode apa adanya. Bagaimanapun, ini tidak boleh menjadi unique_ptr, karena apa pun yang ditunjukkannya sudah dimiliki oleh orang lain unique_ptr.
Jadi mari kita ubah lastmenjadi Node::Node<T>*. Kami memiliki invariants berikut yang benar sebelum dan setelah setiap keluar fungsi anggota: Jika _size == 0, first==last==nullptr. Jika tidak,
firstmenunjuk ke simpul pertama dalam daftarfirst->previous == nullptr- Diberikan node yang dapat dijangkau
n,n->nextbernilai null ataun->next.get() == n->next->previous lastmenunjuk ke simpul terakhir yang dapat dijangkau dalam daftar.last.nextadalah nol._sizenode dapat dijangkau.
Kita perlu menulis fungsi anggota kita agar invarian ini tetap benar.
go_tobiasanya akan dicapai melalui penerapan std::nextke iterator awal. Itu memiliki perbedaan perilaku ketika Anda mencoba melewati akhir daftar; menggunakan std::nextakan menghasilkan perilaku tidak terdefinisi dalam kasus itu. Jika Anda menginginkan perilaku saat ini, Anda dapat menerapkannya dengan sesuatu seperti
iterator go_to(const int n) const {
if (n >= _size) {
return end();
} else {
return std::next(begin(), n);
}
}
Saat Anda menggunakan unique_ptruntuk mengelola memori, Anda biasanya tidak menggunakan new. Sebagai gantinya, gunakan std::make_uniquejika Anda menggunakan C ++ 14 atau yang lebih baru (dan tulis sendiri make_uniquedi C ++ 11). Ini memungkinkan Anda untuk meningkatkan keamanan pengecualian kode Anda. Coba ini untuk 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;
}
Di sini, node dibuat dengan cara yang aman untuk pengecualian. Tidak ada kemungkinan bocor first, karena kami tidak melepaskannya (kode Anda akan bocor firstjika alokasi gagal atau jika konstruktor terlempar Node(karena Tkonstruktor bergerak melempar)). Dengan asumsi operasi Anda swapdan movetidak ada pelemparan, push_frontberhasil, dan elemen baru telah dimasukkan di awal, atau alokasi gagal, push_frontlemparan, dan struktur data belum diubah.
Adapun push_back, jika Anda tidak menggunakan di lastsini, tidak ada alasan lastsama sekali.
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;
}
Sekali lagi, kita memastikan bahwa invarian kelas tetap, bahkan jika kita melempar saat membangun node baru.
Menurut saya ini bukan substitutefungsi yang masuk akal. Pengguna daftar Anda harus menulis *it = x;dan mereka harus tahu apakah iterator mereka valid atau tidak.
Semantik normal untuk insertadalah memasukkan nilai tepat sebelum iterator diteruskan, bukan setelahnya. Hal ini memungkinkan insertuntuk menyisipkan di posisi mana pun dalam daftar dan itu berarti insertmemiliki semantik yang masuk akal saat end()diteruskan sebagai 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());
}
Pindah class Nodedan struct __iteratormasukclass List
Sangat aneh melihat Node::Node<T>di dalam kode. A Nodeadalah detail implementasi Anda List, jadi harus dideklarasikan di dalam class List. Hal yang sama berlaku untuk __iterator. Sebagai contoh:
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() {...};
...
};
Perhatikan bagaimana semua ini menghindari keharusan untuk memasukkan namespaces atau __prefiks ( yang harus Anda hindari ) untuk menyembunyikannya, dan bagaimana ini mengurangi berapa kali Anda harus menulis secara eksplisit <T>. Tentu saja, sekarang semuanya harus dideklarasikan di dalam List.h, tetapi saya tidak melihatnya sebagai kekurangan.
Saya pikir Anda harus mengikuti standar C ++ insertuntuk kontainer dengan meneruskan a begindan enditerator, misalnya
template<typename T>
void insert(Iterator begin, Iterator begin2, Iterator end2);
void insert(Iterator begin, T value);