二重リンクリストバックポインタ

Question

私はこの二重リンクリストを実装する必要があります。リストには、最初の有効な要素を指すフロントポインタと、最後の有効な要素を指すバックポインタが必要です。

私はT &バックを実装し、私は現在

#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 

編集機能していないしているiterator.What終わりを定義する必要がある場合、このコードで私の問題は、最後の数行である：追加--operator

を

Answer 1

back()イテレータの問題は、最初のように少し複雑です。 back()はend()と密接に関連していますが、end()の実装は正しく機能しません。あなたのイテレータクラスは実際に書かれているように、実際にはend()の値を表すようには設計されていません。

ただ、一瞬の間、あなたのend()イテレーターが素晴らしくいいことをふりまとめましょう。 back()の古典定義だ

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

：それが事実であれば、あなたのback()を単に書かことができます。それはそれです。 constバージョンは類似しています。

--演算子がまだ定義されていないということは大きな問題ではありません。それは副次的な問題です。既にコード化されている++演算子のように簡単に定義できます。その部分が完了したとしましょう。主要ないくつかの方法で失敗します

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

：大きな問題は、あなたの実際end()値です。 m_backは、二重リンクリストの最後の要素へのポインタです。 m_backは、最後の要素の次の次のメモリ位置になります。それは本当にあまり意味がありません、そしてさらに、それは次の単純な理由のために完全に間違っています。

また、リストが空の場合、m_backはnullなので、m_back+1は未定義の動作です！おっとっと。しかし、あなたが知っているように、空のコンテナのend()は完全に有効なイテレータでなければなりません。

ここで、iteratorが二重リンクリストの最後の要素を参照している状況を考えてみましょう。その場合、++演算子を使用してインクリメントすると、end()の値が得られます。それがそれだから。さあ、いったん立ち止まり、考えてみましょう。 operator++()が二重リンクされたリストの最後の要素を参照しているイテレータを「インクリメント」した後で、これが起こりますか？もちろん違います。

また、新しいノードがカスタムコンテナの末尾にあるpush_back（）の後に、イテレータの値が同じままである必要があるという基本的な公理も覚えておいてください。しかし、あなたのコードでそれが起こったら、全く新しいm_backを持っています。そして、m_back+1はまったく異なっています。以前の "m_back + 1"に何が起こったのですか？それは突然end()値以外のものに変わっています。実際には、二重リンクされたリストのどの部分も指していません。これは、リスト内の既存の要素の後ろのメモリ位置を指します。

あなたの質問にお答えしたback()の問題は、修正するのがかなり簡単です。しかし、ここで取り組まなければならない本当の問題は、イテレータの値をどのように設計する必要があるのか​​、どのようにするべきかです。あなたが今持っているものは正しく動作しません。