Akıllı işaretçilerle Çift Bağlantılı Liste: ekleme yöntemiyle ilgili sorunlar
Stroustrup'un "C ++ kullanarak İlkeler ve Uygulama", Bölüm 20.4 kitabını izleyerek bir Şablonlu Çift Bağlantılı Liste uygulamaya çalışıyorum. Ham işaretçiler yerine benzersiz işaretçiler kullanmak istiyorum . Kod şu şekilde düzenlenmiştir:
- yapının
Nodeuygulandığı Node.h başlığı : aunique_pointersonraki düğüm için kullanılır ve önceki düğüm için ham - Üstbilgi Iterator.h
Iteratoruygulandığı yer - sınıfın
Listuygulandığı List.h başlık - yöntemlerin test edildiği bir main.cpp
Orada gibi diğer oldukça benzer sorular, olduklarını gördüğüm bu bir ama : my insert yönteminin tasarımı ise bilmiyorum iterator insert(iterator p, const T& x)tamamdır . Özellikle ararsam bir segmentasyon hatası alıyorum auto it3 = insert(--p,4). Bu tamam mı yoksa bunu düzeltmeli miyim?
İşte benim 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 */
Öyleyse, işte Yineleyici.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 */
List.h başlığı burada
#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;
}
};
Son olarak, testlerin bulunduğu main.cpp dosyası:
#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;
}
DÜZENLE :
Düzeltilmiş versiyonu 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;
}
Yanıtlar
Bu bağlantılı listede hafıza yönetimi ile ilgili bir takım problemleriniz var. Hatırlanması gereken en önemli şey unique_ptr, bir nesnenin sahipliğini göstermesidir. Kullanımı release, resetve daha az bir ölçüde get, her zaman yanlış değil, ancak genellikle sınıf yanlış bir şekilde kullanılıyor olduğu bir gösterge: bir kod koku. Genellikle swapbunun yerine taşıma atamasını kullanmalısınız. Dosyaları incelerken bunları söyleyeceğim.
Hızlı bir not: Aşağıdaki kodu test etmedim ve hatta derlemedim; bazı hatalar içerebilir.
Node.h
Bu çoğunlukla iyidir. "Kopya" yapıcısı ( Node(std::unique_ptr<Node>&)) muhtemelen kaldırılmalıdır. Bir düğümü ve tüm soyundan gelenleri kopyalamak gerçekten mantıklı değil. Bu davranışı isteseniz bile, bu uygulama hatalı. Önceki tüm bağlantıları kaldırır, böylece çift bağlantılı bir liste gibi görünen tekil bağlantılı bir listeniz olur.
Iterator.h
Yineleyici sınıfınız pek doğru değil. endYineleyici olarak çalışmaz . Özellikle, --l.end()boş göstericiye başvurduğu için tanımsız davranış sergiler. Pratikte, yineleyici sınıfları, geldikleri koleksiyona bir başvuruya ihtiyaç duyma eğilimindedir.
Ayrıca, bu yineleyici çift yönlü yineleyicinin gereksinimlerini karşılamıyor (bunu ileri yineleyici olarak işaretlediğinizi biliyorum, ancak bu gereksinimleri de karşılamıyor). Özellikle aşağıdakileri ihlal eder:
- "Takas edilebilir türdeki değerler"; Burada biraz paslandım ama eminim kullanıcı tarafından beyan edilen yıkıcı, dolaylı olarak bildirilen hareket oluşturucuyu ve taşıma atama operatörünün oluşturulmasını engelledi; ya bu işlevleri (örneğin kullanarak
= default) ya da birswapişlevi sağlamalısınız . - Sonek artırma ve azaltma operatörlerini desteklemez.
List.h
List::lastgerçekten doğru uygulanmadı. Anlayabildiğim kadarıyla, aslında nullptrkod tarafından olduğu gibi hiçbir şeye ayarlanmadı . Her durumda, bu gerektiğini değil bir olmak unique_ptrzaten başka aittir işaret şey çünkü unique_ptr.
Öyleyse lasta olarak değiştirelim Node::Node<T>*. If: Biz önce ve her üye işlev çıkar sonra doğruysa aşağıdaki değişmezleri vardır _size == 0, first==last==nullptr. Aksi takdirde,
firstlistedeki ilk düğümü gösterirfirst->previous == nullptr- Ulaşılabilir bir düğüm verilen
n,n->nextnull veyan->next.get() == n->next->previous lastlistedeki ulaşılabilir son düğümü gösterir.last.nextboş._sizedüğümlere ulaşılabilir.
Bu değişmezlerin doğru kalması için üye fonksiyonlarımızı yazmamız gerekiyor.
go_togenellikle başlangıç std::nextyineleyicisine başvurarak elde edilir . Bu, listenin sonunu geçmeye çalıştığınızda bir davranış farklılığına sahiptir; kullanılması std::nextbu durumda tanımsız davranışa neden olur. Mevcut davranışı istiyorsanız, bunu aşağıdaki gibi bir şeyle uygulayabilirsiniz:
iterator go_to(const int n) const {
if (n >= _size) {
return end();
} else {
return std::next(begin(), n);
}
}
unique_ptrBelleği yönetmek için kullandığınızda , genellikle kullanmamalısınız new. Bunun yerine, std::make_uniqueC ++ 14 veya sonraki bir sürümünü kullanıyorsanız kullanın (ve make_uniqueC ++ 11'de kendinizinkini yazın). Bu, kodunuzun istisna güvenliğini artırmanıza olanak tanır. Şunun için deneyin 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;
}
Burada düğüm, istisnai olmayan bir şekilde oluşturulur. Sızdırma şansı yok first, çünkü onu serbest bırakmıyoruz ( firstayırma başarısız olursa veya Nodekurucu atarsa kodunuz sızar ( Thamle oluşturucunun atması nedeniyle )). Sizin swapve moveatmama operasyonlarınız olduğunu varsayarsak , ya push_frontbaşarılı olur ve yeni eleman başlangıçta eklenir ya da tahsis başarısız olur, fırlatılır push_frontve veri yapısı değişmez.
Gelince push_back, lastburada kullanmıyorsanız, sahip olmanız için hiçbir neden yok last.
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;
}
Yine, yeni düğümü oluştururken fırlatsak bile sınıfın değişmezlerinin geçerli olmasını sağlıyoruz.
substituteMakul bir işlev olduğunu düşünmüyorum . Listenizin kullanıcısı yazmalı *it = x;ve yineleyicinin geçerli olup olmadığını bilmelidir.
Normal anlambilim , yineleyicinin hemen sonrasına değil, içeri girmesinden inserthemen önce bir değer eklemektir. Bu insert, listedeki herhangi bir konuma eklemeye izin verir ve yineleyici olarak geçildiğinde insertmantıklı anlamlara sahip olduğu anlamına gelir end().
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());
}
Taşı class Nodeve struct __iteratoriçineclass List
Node::Node<T>Kodun içini görmek çok tuhaf . A Node, sizin bir uygulama detayıdır List, bu yüzden içeride beyan edilmelidir class List. Aynısı için de geçerli __iterator. Örneğin:
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() {...};
...
};
Tüm bunların, onları gizlemek için ( kaçınmanız gereken ) namespaces veya __önekler eklemeye ihtiyaç duymaktan nasıl kaçındığına ve bunun, açıkça yazmak zorunda olduğunuz sayıyı nasıl azalttığına dikkat edin . Elbette, şimdi her şeyin içeride ilan edilmesi gerekiyor , ama bunu bir dezavantaj olarak görmüyorum.<T>List.h
Örneğin inserta beginve endyineleyici geçerek konteynerler için C ++ standardını izlemeniz gerektiğini düşünüyorum.
template<typename T>
void insert(Iterator begin, Iterator begin2, Iterator end2);
void insert(Iterator begin, T value);