Implementing custom iterators in C++11

Question

I am reading a book, and I started the Templates chapter. I have already read the chapter about iterators. For practicing, I am trying to implement a doubly-linked class using templates. Below is the header file of my class.

template<typename T>
class list
{
private:
    T* first_node;
    T* last_node;
    struct node_structure
    {
        T* previous;
        T* next;
        T content;
    };
public:
    list();
    void push_back( T& item );
    void push_front( T& item );
    void remove( size_t index );
    size_t size() const;
    T& get_node( size_t index );
    void clear();
    ~list();
};

I could have set two members:

T* begin();
T* end();

...to act like very basic iterators, but they are not iterators actually. So, I have a question:

How do I implement the custom iterator class to be used with all the arithmetic operations and to have begin(), cbegin(), end(), and cend()?

_{(I am aware that creating a list class will not be as efficient as std::list, but I am doing this just for sake of practicing.)}

No, stackoverflow is no code review site but there is one that is http://codereview.stackexchange.com — Stephan Dollberg, Mar 15 '14 at 17:10
I know that. that's why I mentioned the second question as optional, because if somebody answers it, I will not be needed to post the same entry on **CodeReview** — Victor, Mar 15 '14 at 17:12
It's two different questions so you definitely should. On a related note, you are not showing any implementation at all. So you might wanna implement it and then comeback to code review. — Stephan Dollberg, Mar 15 '14 at 17:13
Ok then, but now I need advice about the iterators for my class, the first question in my post. — Victor, Mar 15 '14 at 17:15
not if you want to use operations like next element (it++). See http://stackoverflow.com/questions/8054273/how-to-implement-an-stl-style-iterator-and-avoid-common-pitfalls for an answer — MikeMB, Mar 15 '14 at 17:27
Ah, my derp. `T*` could be a perfectly valid iterator for a `vector`-like container. But this is a linked list, and `T*` is indeed insufficient as an iterator. I stand corrected. — Magnus Hoff, Mar 15 '14 at 17:37
I'm a little confused here. Why do you have your node pointers as type `T`? Am I misreading this code? — motoku, Mar 15 '14 at 18:16

iavr · Accepted Answer · 2014-03-15T18:14:24.887

If you have a look at an implementation of <iterator>, you'll find something like __normal_iterator, which looks like:

template<typename I>
class iter
{
protected:
    I i;

    using tr = iterator_traits<I>;

public:
    using iterator_type     = I;
    using iterator_category = typename tr::iterator_category;
    using value_type        = typename tr::value_type;
    using difference_type   = typename tr::difference_type;
    using reference         = typename tr::reference;
    using pointer           = typename tr::pointer;

    iter() : i(I()) { }

    explicit iter(const I& i) : i(i) { }

    // Forward iterator requirements
    reference operator*() const { return *i; }

    pointer operator->() const { return i; }

    iter& operator++() { ++i; return *this; }

    iter operator++(int) { return iter(i++); }

    // Bidirectional iterator requirements
    iter& operator--() { --i; return *this; }

    iter operator--(int) { return iter(i--); }

    // Random access iterator requirements
    reference operator[](const difference_type& n) const { return i[n]; }

    iter& operator+=(const difference_type& n) { i += n; return *this; }

    iter operator+(const difference_type& n) const { return iter(i + n); }

    iter& operator-=(const difference_type& n) { i -= n; return *this; }

    iter operator-(const difference_type& n) const { return iter(i - n); }

    const I& base() const { return i; }
};

This is supposed to work on an ordinary pointer or iterator. All you have to do is use this as a template and adjust to what is needed by your custom container. If T is your value_type, then member functions normally return

begin() -> iter<T*>
cbegin() -> iter<const T*>
rbegin() -> std::reverse_iterator<iter<T*> >
crbegin() -> std::reverse_iterator<iter<const T*> >

However, since you have your node_structure, this is not entirely true and you need to elaborate a bit more.

of, it looks complex :)) I will see what I can do with it! Thank you — Victor, Mar 15 '14 at 18:12
that's another reason to appreciate what we get with `std::list`! — iavr, Mar 15 '14 at 18:17
read my last row in the post :D this is just for the sake of practicing — Victor, Mar 15 '14 at 18:18
@Victor Plus, there are binary comparison operators `==`, `!=`, as well as `<`, `<=` etc. for random access, that I forgot to mention. — iavr, Mar 15 '14 at 18:19
@Victor For practice, you could skip the type traits and limit yourself to operators `*()`, `++()` (not `++(int)`), and `!=`. That's enough to see it in action in a `for` loop. Also forget `rbegin()` etc. Just make `begin()` and `end()`. Have fun! — iavr, Mar 15 '14 at 18:22

Implementing custom iterators in C++11

1 Answers1

Linked