Not maintaining iterator dereferenceability?

Question

Here is a first attempt at iterator of a doubly linked list:

dlist.h

#ifndef dlist_h
#define dlist_h

/* Node */
template <class Elem>
struct Link
{
    Link();
    Link (Link<Elem>* s, Link<Elem>* p, const Elem& v);
    Link (const Link<Elem>& src);

    Link<Elem>& operator= (const Link<Elem>& src);

    bool operator== (const Link<Elem>& src);
    bool operator!= (const Link<Elem>& src);

    void swap(Link<Elem>& src);

    Link* succ;
    Link* prev;
    Elem val;
};


//----------------------------------------------------------------------------
/* Doubly Linked List */
template <class Elem>
class List
{ 
public:
    class iterator;

    List();

    iterator begin() { return iterator(first, first, last); }
    iterator end() { return iterator(last, first, last); }

    void push_front(const Elem& v);
    Elem& front();

    size_t size(); 
    void print();

private:
    Link<Elem> *first;
    Link<Elem> *last;
};

//----------------------------------------------------------------------------
/* a range-checked bidirectional iterator */
template <class Elem>
class List<Elem>::iterator
{
public:
    iterator();                                         // default constructor
    iterator(Link<Elem>* c, Link<Elem>* b, Link<Elem>* e);                  
    iterator(const iterator& src);                      // copy constructor
    iterator operator= (const iterator& src);           // copy assignment 

    iterator& operator++();                             // incrementations
    iterator operator++(int);                           // postfix
    iterator& operator--();                             // decrementations
    iterator operator--(int);                           // postfix

    Elem& operator*();                                  // dereferenceable lvalue
    const Elem& operator*() const;                      // dereferenceable rvalue

    bool operator== (const iterator& b) const;          // equality comparisons
    bool operator!= (const iterator& b) const;

    void swap(iterator& src);

private:
    Link<Elem>* curr;
    Link<Elem>* begin;
    Link<Elem>* end;
};

#include "dlist.cpp"

#endif

dlist.cpp

//-----------------------------------------------------------------------------

template <class Elem>
Link<Elem>::Link()
    : succ(nullptr), prev(nullptr), val(Elem())
{

}

//-----------------------------------------------------------------------------

template <class Elem>
Link<Elem>::Link (Link<Elem>* s, Link<Elem>* p, const Elem& v)
    : succ(s), prev(p), val(v)
{

}

//-----------------------------------------------------------------------------

template <class Elem>
Link<Elem>::Link (const Link<Elem>& src)
   : succ(src.succ), prev(src.prev), val(src.val)
{

}

//-----------------------------------------------------------------------------
template <class Elem>
Link<Elem>& Link<Elem>::operator= (const Link<Elem>& src)
{
    Link<Elem> temp(src);
    swap(*this, temp);
    return *this;
}

//-----------------------------------------------------------------------------
template <class Elem>
bool Link<Elem>::operator== (const Link<Elem>& src)
{
    return succ = src.succ && prev = src.prev;
}

//-----------------------------------------------------------------------------

template <class Elem>
bool Link<Elem>::operator!= (const Link<Elem>& src)
{
    return !(*this == src);
}

//-----------------------------------------------------------------------------

template <class Elem>
void Link<Elem>::swap(Link<Elem>& src)
{
    std::swap(prev, src.prev);
    std::swap(succ, src.succ);
    std::swap(val, src.val);
}

//-----------------------------------------------------------------------------

template<class Elem>
void swap(Link<Elem>& lhs, Link<Elem>& rhs)
{
    lhs.swap(rhs);
}

//-----------------------------------------------------------------------------

template<class Elem> 
List<Elem>::List()
    : first(new Link<Elem>()), last(first)
{

}

//-----------------------------------------------------------------------------

template<class Elem>
void List<Elem>::push_front(const Elem& v)
{  
    first = new Link<Elem>(first, nullptr, v); 
}

//-----------------------------------------------------------------------------

template<class Elem>
Elem& List<Elem>::front()
{
    return first->val; 
}

//-----------------------------------------------------------------------------

template<class Elem>
size_t List<Elem>::size() 
{
    size_t count = 0;
    for (iterator p = begin(); p != end(); ++p)
    {
        ++count;     
    }
    return count;
}

//-----------------------------------------------------------------------------

template<class Elem>
void List<Elem>::print()
{
    for (iterator p = begin(); p != end(); ++p)
    {
         std::cout << *p <<' ';  
    }
}

//-----------------------------------------------------------------------------

template<class Elem>
List<Elem>::iterator::iterator()
    : curr(nullptr), begin(nullptr), end(nullptr)
{

}

//-----------------------------------------------------------------------------

template<class Elem>
List<Elem>::iterator::iterator(Link<Elem>* p, Link<Elem>* b, Link<Elem>* e)
    : curr(p), begin(b), end(e)
{

}

//-----------------------------------------------------------------------------

template<class Elem>
List<Elem>::iterator::iterator(const iterator& src)
    : curr(src.curr), begin(src.begin), end(src.end)
{

}

//-----------------------------------------------------------------------------

template<class Elem>
typename List<Elem>::iterator List<Elem>::iterator::operator= (const iterator& src)
{
    iterator temp(src);
    this->swap(temp);
    return *this;
}

//-----------------------------------------------------------------------------

template<class Elem>
typename List<Elem>::iterator& List<Elem>::iterator::operator++()
{
    if (curr == end)
    {
        throw std::out_of_range("List<Elem>::iterator::operator++(): out of range!\n");
    }

    curr = curr->succ;

    return *this; 
}

//-----------------------------------------------------------------------------

template<class Elem>
typename List<Elem>::iterator List<Elem>::iterator::operator++(int)
{
    if (curr == end)
    {
        throw std::out_of_range("List<Elem>::iterator::operator++(): out of range!\n");
    }

    Link<Elem>* old = curr;
    curr = curr->succ;
    return old; 
}

//-----------------------------------------------------------------------------

template<class Elem>
typename List<Elem>::iterator& List<Elem>::iterator::operator--()
{ 
    if (curr == begin)
    {
        throw std::out_of_range("List<Elem>::iterator::operator--(): out of range!\n");
    }

    curr = curr->prev;

    return *this; 
}

//-----------------------------------------------------------------------------

template<class Elem>
typename List<Elem>::iterator List<Elem>::iterator::operator--(int)
{ 
    if (curr == begin)
    {
        throw std::out_of_range("List<Elem>::iterator::operator--(): out of range!\n");
     }

     iterator old(*this);
     curr = curr->prev; 
     return old; 
 }

//-----------------------------------------------------------------------------

template<class Elem>
Elem& List<Elem>::iterator::operator*() 
{ 
    return curr->val; 
}   

//-----------------------------------------------------------------------------

template<class Elem>
const Elem& List<Elem>::iterator::operator*() const
{  
    return curr->val;
}

//-----------------------------------------------------------------------------

template<class Elem> 
bool List<Elem>::iterator::operator== (const iterator& b) const
{ 
    return curr == b.curr; 
} 

//-----------------------------------------------------------------------------

template<class Elem>
bool List<Elem>::iterator::operator!= (const iterator& b) const
{ 
    return curr != b.curr; 
}

//-----------------------------------------------------------------------------

template<class Elem>
void List<Elem>::iterator::swap(iterator& src)
{
    std::swap(curr, src.curr); 
    std::swap(begin, src.begin);
    std::swap(end, src.end);
}

//-----------------------------------------------------------------------------

template<class Elem>
void swap(typename List<Elem>::iterator& lhs, typename List<Elem>::iterator& rhs)
{
    lhs.swap(rhs);
}

main.cpp

 #include <iostream>
 #include "dlist.h"
 /* simple test for iterator */ 

int main() 
{
    List<int> l;
    l.push_front(1);
    l.push_front(2);
    l.push_front(3);
    l.push_front(4);
    l.push_front(5);

    // default constructor, copy assignment
    List<int>::iterator p = l.begin();

    // lvalue dereferencing 
    *p = 100;

    // incrementation, rvalue dereferencing
    List<int>::iterator i;
    for (i = l.begin(); i != l.end(); ++i)
    {
        std::cout << *i <<' ';
    }

    if (i == l.end() && i != l.begin())
    {
        std::cout <<"\ncomparison correct!\n";
    }

    // postfix and prefix decrementation; maintain dereferenceability

    List<int>::iterator ii = l.end();
    --ii;
    for (; ii != l.begin(); ii--)
    {
        std::cout << *ii <<' ';
    } 

    return 0;
}

When it reaches the last for loop the decrement operator-- somehow invalidates the ii iterator and I can't figure it out despite a thorough^IMO debugging.

Here is a runnable sample.

You never set any link's prev pointer, they are always null. `operator--` will always assign `curr = curr->prev;` which is essentially `curr = nullptr;`. — François Andrieux, Feb 24 '17 at 19:30
Erratum : you assign `prev` once, accidentally in `Link::operator==`. — François Andrieux, Feb 24 '17 at 19:31
Why does your `iterator` need 3 pointers? Only `curr` should be enough. — tnt, Feb 24 '17 at 19:52
I see. However, std::list::iterator only needs 1 pointer because std::list is circular. Since you have a default node I think you can use it as your end() iterator. You don't need `begin` or `end` to check the validity of `curr`. If `curr` is not null then it is valid. So you need only 1 pointer in iterator. — tnt, Feb 24 '17 at 21:05
I strongly suggest deriving your iterator class from [boost::iterator_facade](http://www.boost.org/doc/libs/release/libs/iterator/doc/iterator_facade.html). It avoids much of the boilerplate like having to write both pre- and postfix operators and makes your iterator standard compliant. — zett42, Feb 25 '17 at 00:00

score 2 · Accepted Answer · answered Feb 24 '17 at 21:02

The problem is your push_front method, you forgot to link first->succ->prev back to new node, hence your doubly linked list is basically a singly linked list

The first i-- succeed because last points to a default node, but curr->prev is a nullptr since you forgot to link back, so the next i-- will deref the nullptr curr cause the error.

Fix your push_front method:

template<class Elem>
void List<Elem>::push_front(const Elem& v)
{
    first = new Link<Elem>(first, nullptr, v);
    first->succ->prev = first; //link back
}

score 1 · Answer 2 · edited May 23 '17 at 12:25

Your constructor for Link does not properly update the elements given as arguments. Inserting an element between two elements breaks the previous link.

This is a more appropriate constructor :

template <class Elem>
Link<Elem>::Link(Link<Elem>* s, const Elem& v)
    : succ(s), prev(s->prev), val(v)
{
    // Update next and previous nodes to make them aware of this
    s->prev = this;
    if(prev) prev->succ = this;
}

If you update List::push_front to use this constructor instead, you will find that your code compiles and runs.

You should consider making methods const when appropriate to avoid mistakes (or to spot existing onw them in the case of bool operator== (const Link<Elem>& src) const). Link.

Not maintaining iterator dereferenceability?

2 Answers2