Doppelt verkettete Liste zurück Zeiger

Question

Ich muss diese doppelt verkettete Liste implementieren. Die Liste benötigt einen vorderen Zeiger, der auf das erste gültige Element zeigt, und einen hinteren Zeiger, der auf das letzte gültige Element zeigt.

mit diesem Code Mein Problem mit den letzten Zeilen ist, wenn ich T implementieren müssen & zurück und definieren das Ende iterator.What ich derzeit haben, ist nicht

#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 

bearbeiten arbeiten: hinzugefügt --operator

Answer 1

Ihr Problem mit dem back() Iterator ist ein bisschen komplexer als es zunächst scheint. back() ist eng verwandt mit end(), aber Ihre end() Implementierung wird nicht richtig funktionieren, was ich gleich erklären werde. Ihre Iterator-Klasse ist nicht wirklich darauf ausgelegt, den Wert end() sehr gut darzustellen, wie es derzeit geschrieben wird.

Aber lassen Sie uns für einen Moment vorgeben, dass Ihr end() Iterator war nett und gut.

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

Das ist die klassische Definition von back() ist: Wenn das der Fall wäre, könnte Ihre back() einfach als geschrieben. Das ist es. Die const Version wird analog sein.

Die Tatsache, dass Sie den Operator -- noch nicht definiert haben, ist keine große Sache. Das ist ein Nebenproblem, Sie können es leicht wie den Operator ++ definieren, den Sie bereits codiert haben. Betrachten wir diesen Teil als erledigt. Das Hauptproblem ist Ihr tatsächlicher end() Wert:

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

Das ist ein wichtiger auf verschiedene Weise fehlschlagen. m_back ist ein Zeiger auf das letzte Element in einer doppelt verknüpften Liste. m_back wird der nächste Speicherort nach dem letzten Element sein. Was wirklich nicht sehr sinnvoll ist, und außerdem ist es völlig falsch aus dem folgenden einfachen Grund. Wenn Ihre Liste leer ist, ist m_back null, also m_back+1 ist undefiniertes Verhalten! Hoppla. Aber wie Sie wissen, muss end() eines leeren Containers ein perfekt gültiger Iterator sein.

Betrachten Sie nun die Situation, in der Ihr iterator auf das letzte Element in der doppelt verketteten Liste verweist. In diesem Fall sollte die Erhöhung mit dem Operator ++ Ihnen den Wert end() geben. Weil es das ist. Jetzt hör auf und denke einen Moment nach. Ist das der Fall, nachdem Ihr operator++() den Iterator "inkrementiert", der auf das letzte Element in Ihrer doppelt verknüpften Liste verweist? Natürlich nicht. Denken Sie auch an das grundlegende Axiom, dass Ihr Iterator-Wert end() gleich bleiben soll, nachdem ein neuer Knoten push_back() an das Ende Ihres benutzerdefinierten Containers editiert wurde.

Aber wenn das in deinem Code passiert, wirst du eine komplett neue m_back haben. Und m_back+1 ist jetzt völlig anders. Was ist mit deinem vorherigen "m_back + 1" passiert? Es wird plötzlich zu etwas anderem als dem end() Wert gemorpht. Tatsächlich zeigt es überhaupt keinen Teil der doppelt verknüpften Liste. Es zeigt auf den Speicherort, der nach einem vorhandenen Element in der Liste ist.

Also, das Problem mit Ihrem back(), dass Sie gefragt haben, ist ziemlich einfach zu beheben. Aber Ihr wirkliches Problem hier, das Sie ansprechen müssen, ist, wie Sie Ihren end() Iteratorwert entwerfen müssen, und was sollte es sein. Was Sie jetzt haben, wird nicht richtig funktionieren.