CODEWITHSUNDEEP
c++iteratordoubly-linked-list
Lin0523
Lin0523

Reputation: 171

Doubly linked list back pointer

I have to implement this doubly linked list. The list needs a front pointer pointing to the first valid element and a back pointer pointing to the last valid element.

My problem with this code is with the last few lines when I have to implement T& back and define the end iterator.What I have currently is not working

#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: added --operator

Upvotes: 1

Views: 261

Answers (1)

Sam Varshavchik
Sam Varshavchik

Reputation: 118300

Your problem with the back() iterator is a bit more complex than it seems at first. back() is closely related to end(), however your end() implementation is not going to work correctly, which I'll explain in a moment. Your iterator class is not really designed to represent the end() value very well, as it's currently written.

But let's pretend, for just one moment, that your end() iterator was nice and good. If that were the case, your back() could simply written as:

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

That's the classical definition of back(). That's what it is. The const version is going to be analogous.

The fact that you do not have the -- operator defined yet is not a big deal. That's a side issue, you can easily define it like the ++ operator, that you're already coded. Let's consider that part done. The major problem is your actual end() value:

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

That's a major fail in several ways. m_back is a pointer to the last element in a doubly-linked list. m_back is going to be the next memory location after the last element. Which really is not very meaningful, and furthermore it is completely wrong for the following simple reason.

Additionally, when your list is empty, m_back is null, so m_back+1 is undefined behavior! Oops. But, as you know, end() of an empty container must be a perfectly valid iterator.

Now, consider the situation where your iterator is referencing the last element in the doubly-linked list. In that situation, incrementing it with the ++ operator should give you the end() value. Because that's what it is. Now, stop and think for a moment. Is that's what's going to happen, after your operator++() finishes "incrementing" the iterator that's referencing the last element in your doubly-linked list? Of course not.

Also, keep in mind the fundamental axiom that your end() iterator's value should remain the same after a new node is push_back()ed to the end of your custom container. But when that happens in your code, you're going to have a completely new m_back. And m_back+1 is now completely different. What happened to your prior "m_back+1"? It's suddenly morphed into something other than the end() value. In fact, it doesn't point to any part of the doubly-linked list at all. It points to the memory location that's after some existing element in the list.

So, the issue with your back(), that you asked about, is pretty easy to fix. But your real problem here, that you need to address, is how you need to design your end() iterator value, and what should it be. What you have now is not going to work correctly.

Upvotes: 1

Related Questions