Çift bağlanan liste geri göstergesi

Question

Bu iki bağlı listeyi uygulamak zorundayım. Liste, ilk geçerli öğeye işaret eden bir ön işaretçiye ve son geçerli öğeye işaret eden bir arka işaretçiye ihtiyaç duyar.

geri T & uygulamak ve şu anda

#ifndef List_dllist_h 
#define List_dllist_h 
#include <iterator> 

template <class T> 
class DList 
{ 
struct Node 
{ 
    Node(const T& x,Node* y = 0):m_data(x),m_next(y),m_prev(y){} 
    T m_data; 
    Node* m_next; 
    Node* m_prev; 
}; 

Node* m_head; 
Node* m_back; 

public: 

class iterator 
{ 
    Node* m_rep; 
public: 
    friend class DList; 

    inline iterator(Node* x=0):m_rep(x){} 
    inline iterator(const iterator& x):m_rep(x.m_rep) {} 
    inline iterator& operator=(const iterator& x) 
    { 
     m_rep=x.m_rep; return *this; 
    } 
    inline iterator& operator++() 
    { 
     m_rep = m_rep->m_next; return *this; 
    } 
    inline iterator operator++(int) 
    { 
     iterator tmp(*this); m_rep = m_rep->m_next; return tmp; 
    } 
    inline iterator& operator--() 
    { 
     m_rep= m_rep->m_prev; return *this; 
    } 
    inline iterator operator--(int) 
    { 
     iterator tmp(*this); m_rep= m_rep->m_prev; return tmp; 
    } 
    inline T& operator*() const { return m_rep->m_data; } 
    inline Node* operator->() const { return m_rep; } 
    inline bool operator==(const iterator& x) const 
    { 
     return m_rep == x.m_rep; 
    } 
    inline bool operator!=(const iterator& x) const 
    { 
     return m_rep != x.m_rep; 
    } 

    }; 


DList() : m_head(0), m_back(0) {} 
~DList() { clear(); } 


inline T& front() { return *begin(); } 
inline const T& front() const { return *begin(); } 


inline T& back() { return *--end(); } 
inline const T& back() const { return *--end(); } 

inline iterator begin() { return iterator(m_head); } 
inline iterator end() { return iterator(m_back); } 



}; 
#endif 

Edit çalışmıyor olması iterator.What sonunu tanımlamak zorunda olduğunda bu kodla Benim sorunum son birkaç satır ile olan

: --operator

eklendi

Answer 1

back() yineleyiciniz ile olan sorununuz, ilk bakışta göründüğünden biraz daha karmaşıktır. back()end() ile yakından ilişkilidir, ancak end() uygulamanız doğru çalışmıyor, bir an sonra açıklayacağım. Yineleyici sınıfınız, şu anda yazıldığı için end() değerini gerçekten iyi temsil edecek şekilde tasarlanmamıştır.

Ama sadece bir an için, end() yineleyicinizin güzel ve güzel olduğunu varsayalım. back() klasik tanımı var

inline T& back() { return *--end(); } 

: Eğer öyle olsaydı, senin back() basitçe olarak yazılır olabilir. İşte budur. const sürümü benzer olacaktır.

Henüz tanımlı -- operatörüne sahip olmadığınız gerçeği büyük bir sorun değil. Bu bir yan sorun, zaten kodladığınız ++ operatör gibi kolayca tanımlayabilirsiniz. O kısmı bitti düşünelim. önemli birkaç şekilde başarısız olduğunu

inline iterator end() { return iterator(m_back +1); } 

: büyük sorun gerçek end() değerdir. m_back, iki bağlantılı bir listedeki son öğenin işaretçisidir. m_back, son öğeden sonraki bir sonraki bellek konumu olacak. Hangi gerçekten çok anlamlı değildir ve ayrıca aşağıdaki basit sebepten dolayı tamamen yanlıştır.

Ayrıca, listeniz boş olduğunda, m_back boş, m_back+1 tanımsız bir davranış! Hata. Ancak, bildiğiniz gibi, boş bir kabın end() mükemmel bir yineleyici olması gerekir.

Şimdi, iterator öğesinin çift bağlantılı listedeki son öğeye başvurduğu durumu düşünün. Bu durumda, ++ operatörü ile arttırmak size end() değerini vermelidir. Çünkü bu böyle. Şimdi dur ve bir an düşünün. operator++(), iki katına çıkan listenizdeki son öğeye referans veren yineleyici "arttırma" işleminden sonra ne olacak? Tabii ki değil. Ayrıca, end() yineleyici değerinizin, yeni bir düğüm push_back() özel kapsayıcınızın sonuna eklendikten sonra aynı kalması gereken temel aksiyomu da unutmayın. Ancak bu kodunuzda olduğunda, tamamen yeni bir m_back'a sahip olacaksınız. Ve m_back+1 şimdi tamamen farklı. Önceki "m_back + 1" e ne oldu? Aniden, end() değerinden başka bir şeye dönüştü. Aslında, iki taraflı listenin herhangi bir bölümüne işaret etmez. Listedeki mevcut bir elemanın ardından hafıza konumuna işaret eder.

back() ile ilgili, sorduğunuz sorunun düzeltilmesi oldukça kolaydır. Ama burada sormanız gereken gerçek probleminiz, end() yineleyici değerinizi nasıl tasarlamanız gerektiği ve ne olması gerektiği. Şu an sahip olduğunuz şey doğru şekilde çalışmayacak.