双向链表后向指针

Question

我必须实现这个双向链表。该列表需要一个指向第一个有效元素的前指针和一个指向最后一个有效元素的后指针。

我对这段代码的问题是最后几行，当我必须实现 T&back 并定义结束时 iterator.What 我目前没有工作

#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

编辑：添加了 --operator

Answer 1

back() 迭代器的问题比乍看起来要复杂一些。 back() 与 end() 密切相关，但是您的 end() 实现将无法正常工作，稍后我将对此进行解释。您的迭代器 class 并不是真正设计来很好地表示 end() 值，因为它目前是这样写的。

但是让我们假装一下，您的 end() 迭代器非常好。如果是这样的话，你的 back() 可以简单地写成：

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

这是 classback() 的逻辑定义。就是这样。 const 版本将是类似的。

您还没有定义 -- 运算符这一事实并不是什么大问题。这是一个附带问题，您可以像已经编码的 ++ 运算符一样轻松定义它。让我们考虑完成的部分。主要问题是您的实际 end() 值：

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

这在几个方面都是一个重大失败。 m_back 是指向双向链表中最后一个元素的指针。 m_back 将成为最后一个元素之后的下一个内存位置。这确实意义不大，而且完全错误，原因很简单。

此外，当您的列表为空时，m_back 为空，因此 m_back+1 是未定义的行为！哎呀。但是，如您所知，空容器的 end() 必须是完全有效的迭代器。

现在，考虑一下您的 iterator 引用双向链表中最后一个元素的情况。在这种情况下，使用 ++ 运算符递增它应该会得到 end() 值。因为它就是这样。现在，停下来想一想。在您的 operator++() 完成 "incrementing" 引用双向链表中最后一个元素的迭代器之后，会发生这种情况吗？当然不是。

此外，请记住一个基本公理，即在将新节点 push_back()ed 到自定义容器的末尾后，您的 end() 迭代器的值应保持不变。但是当您的代码中发生这种情况时，您将拥有一个全新的 m_back。而 m_back+1 现在完全不同了。你之前的 "m_back+1" 怎么了？它突然变成了 end() 值以外的东西。事实上，它根本不指向双向链表的任何部分。它指向列表中某个现有元素之后的内存位置。

因此，您询问的 back() 问题很容易解决。但是你真正需要解决的问题是你需要如何设计你的 end() 迭代器值，它应该是什么。你现在拥有的东西不会正常工作。

双向链表后向指针

Doubly linked list back pointer

c++

iterator

doubly-linked-list