How to Implement an Stl-Style Iterator and Avoid Common Pitfalls

How to implement an STL-style iterator and avoid common pitfalls?

http://www.cplusplus.com/reference/std/iterator/ has a handy chart that details the specs of § 24.2.2 of the C++11 standard. Basically, the iterators have tags that describe the valid operations, and the tags have a hierarchy. Below is purely symbolic, these classes don't actually exist as such.

iterator {
    iterator(const iterator&);
    ~iterator();
    iterator& operator=(const iterator&);
    iterator& operator++(); //prefix increment
    reference operator*() const;
    friend void swap(iterator& lhs, iterator& rhs); //C++11 I think
};

input_iterator : public virtual iterator {
    iterator operator++(int); //postfix increment
    value_type operator*() const;
    pointer operator->() const;
    friend bool operator==(const iterator&, const iterator&);
    friend bool operator!=(const iterator&, const iterator&); 
};
//once an input iterator has been dereferenced, it is 
//undefined to dereference one before that.

output_iterator : public virtual iterator {
    reference operator*() const;
    iterator operator++(int); //postfix increment
};
//dereferences may only be on the left side of an assignment
//once an output iterator has been dereferenced, it is 
//undefined to dereference one before that.

forward_iterator : input_iterator, output_iterator {
    forward_iterator();
};
//multiple passes allowed

bidirectional_iterator : forward_iterator {
    iterator& operator--(); //prefix decrement
    iterator operator--(int); //postfix decrement
};

random_access_iterator : bidirectional_iterator {
    friend bool operator<(const iterator&, const iterator&);
    friend bool operator>(const iterator&, const iterator&);
    friend bool operator<=(const iterator&, const iterator&);
    friend bool operator>=(const iterator&, const iterator&);

    iterator& operator+=(size_type);
    friend iterator operator+(const iterator&, size_type);
    friend iterator operator+(size_type, const iterator&);
    iterator& operator-=(size_type);  
    friend iterator operator-(const iterator&, size_type);
    friend difference_type operator-(iterator, iterator);

    reference operator[](size_type) const;
};

contiguous_iterator : random_access_iterator { //C++17
}; //elements are stored contiguously in memory.

You can either specialize std::iterator_traits<youriterator>, or put the same typedefs in the iterator itself, or inherit from std::iterator (which has these typedefs). I prefer the second option, to avoid changing things in the std namespace, and for readability, but most people inherit from std::iterator.

struct std::iterator_traits<youriterator> {        
    typedef ???? difference_type; //almost always ptrdiff_t
    typedef ???? value_type; //almost always T
    typedef ???? reference; //almost always T& or const T&
    typedef ???? pointer; //almost always T* or const T*
    typedef ???? iterator_category;  //usually std::forward_iterator_tag or similar
};

Note the iterator_category should be one of std::input_iterator_tag, std::output_iterator_tag, std::forward_iterator_tag, std::bidirectional_iterator_tag, or std::random_access_iterator_tag, depending on which requirements your iterator satisfies. Depending on your iterator, you may choose to specialize std::next, std::prev, std::advance, and std::distance as well, but this is rarely needed. In extremely rare cases you may wish to specialize std::begin and std::end.

Your container should probably also have a const_iterator, which is a (possibly mutable) iterator to constant data that is similar to your iterator except it should be implicitly constructable from a iterator and users should be unable to modify the data. It is common for its internal pointer to be a pointer to non-constant data, and have iterator inherit from const_iterator so as to minimize code duplication.

My post at Writing your own STL Container has a more complete container/iterator prototype.

C++ iterator in for loop pitfalls?

Ordering comparisons such as <, >, <=, >= will work for random-access iterators, but many other iterators (such as bidirectional iterators on linked lists) only support equality testing (== and !=). By using != you can later replace the container without needing to change as much code, and this is especially important for template code which needs to work with many different container types.

How to correctly implement custom iterators and const_iterators?

Choose type of iterator which fits your container: input, output, forward etc.
Use base iterator classes from standard library. For example, std::iterator with random_access_iterator_tag.These base classes define all type definitions required by STL and do other work.
To avoid code duplication iterator class should be a template class and be parametrized by "value type", "pointer type", "reference type" or all of them (depends on implementation). For example:
```
// iterator class is parametrized by pointer type
template <typename PointerType> class MyIterator {
    // iterator class definition goes here
};

typedef MyIterator<int*> iterator_type;
typedef MyIterator<const int*> const_iterator_type;
```
Notice iterator_type and const_iterator_type type definitions: they are types for your non-const and const iterators.

Custom Iterator in C++

When I did my own iterator (a while ago now) I inherited from std::iterator and specified the type as the first template parameter. Hope that helps.

For forward iterators user forward_iterator_tag rather than input_iterator_tag in the following code.

This class was originally taken from istream_iterator class (and modified for my own use so it may not resemble the istram_iterator any more).

template<typename T>
class <PLOP>_iterator
         :public std::iterator<std::input_iterator_tag,       // type of iterator
                               T,ptrdiff_t,const T*,const T&> // Info about iterator
{
    public:
        const T& operator*() const;
        const T* operator->() const;
        <PLOP>__iterator& operator++();
        <PLOP>__iterator operator++(int);
        bool equal(<PLOP>__iterator const& rhs) const;
};

template<typename T>
inline bool operator==(<PLOP>__iterator<T> const& lhs,<PLOP>__iterator<T> const& rhs)
{
    return lhs.equal(rhs);
}

Check this documentation on iterator tags:

http://www.sgi.com/tech/stl/iterator_tags.html

Having just re-read the information on iterators:

http://www.sgi.com/tech/stl/iterator_traits.html

This is the old way of doing things (iterator_tags) the more modern approach is to set up iterator_traits<> for your iterator to make it fully compatible with the STL.

Implementation my own List and iterator STL C++

In the operator++ of the iterator and const_iterator you need to add

_ptr = ptr_->next

and I would rather not implement

self_type operator++(int junk)

in the iterator class. List iterators typically can only advance one step forward.

Also, in the const_iterator, make sure you only return const pointers, so that the compiler will issue an error if the caller tries to use the const_iterator to mutate the list.

How can I implement various iterator categories in an elegant and efficient way?

I think you should use CRTP (https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern).
Like this:

template <typename T, typename ItT>
struct iiterator_t {
    typedef T value_type;
    typedef T& reference;
    typedef T* pointer;

    typedef ItT iterator_type;

    virtual iterator_type& operator=(const iterator_type&) = 0;
    virtual iterator_type& operator++() = 0;
    virtual reference operator*() const = 0;
};

template <typename T, typename ItT>
struct iterator_impl_t :  virtual public iiterator_t<T, ItT>{
    typedef T value_type;
    typedef T& reference;
    typedef T* pointer;

    typedef ItT iterator_type;

    iterator_type& operator=(const iterator_type &rhs)
    {
        p = static_cast<const iterator_impl_t&>(rhs).p;
        return dynamic_cast<iterator_type&>(*this);
    }

    iterator_type& operator++()
    {
        ++p;
        return dynamic_cast<iterator_type&>(*this);
    }

    reference operator*() const
    {
        return *p;
    }

private:
    pointer p;
};

template <typename T, typename ItT>
struct iinput_iterator_t : public virtual iiterator_t<T, ItT> {
    typedef T value_type;
    typedef T& reference;
    typedef T* pointer;

    typedef ItT iterator_type;

    virtual iterator_type operator++(int) = 0;
};


template <typename T, typename ItT>
struct input_iterator_impl_t :
    public virtual iinput_iterator_t<T, ItT>,
    public virtual iterator_impl_t<T, ItT>
{
    typedef T value_type;
    typedef T& reference;
    typedef T* pointer;

    typedef ItT iterator_type;

    iterator_type operator++(int)
    {
        iterator_type result(dynamic_cast<const iterator_type &>(*this));
        ++dynamic_cast<iterator_impl_t<T, ItT> &>(*this);
        return result;
    }
};


template <typename T>
struct iterator :
    public virtual iterator_impl_t<T, iterator<T> >
{
};


template <typename T>
struct input_iterator :
    public virtual input_iterator_impl_t<T, input_iterator<T>>
{
};

int main(int , char** )
{
    iterator<int> i;
    iterator<int> i2 = ++i;
    input_iterator<int> inpi;
    input_iterator<int> inpi2 = inpi++;
    return 0;
 }

STL-style algorithm: returning via OutputIterator

You may be looking for something like this:

template <typename InputIt, 
          typename OutputIt, 
          typename BinaryPredicate, 
          typename Merge>
void merge_adjacent(InputIt first, 
                    InputIt last, 
                    OutputIt out, 
                    BinaryPredicate pred, 
                    Merge merge)
{
    if (first == last) return;
    auto accum = *first++;
    while (first != last) {
        auto cur = *first++;
        if (pred(cur, accum)) {
            accum = merge(accum, cur);
        } else {
            *out++ = accum;
            accum = cur;
        }
    }
    *out++ = accum;
}

Demo. Not tested very thoroughly, I only confirmed it worked on your example. I think I'm staying within the capabilities of InputIterator and OutputIterator, but I haven't tested that either.

Error trying to implement STL iterators

Your error is in your understanding of pointers, you can't assign anything to an uninitialized pointer. so you can't assign a reference to an uninitialized pointer in your constructor:

*container = x;  // container is uninitialized, so this function will generate an AccessViolation

Instead you should use it as

container = std::addressof(x);

In this case you initialize your pointer with address of the reference that passed to you, but in your case you are trying to copy the reference to address that your pointer is pointing to it and since your pointer is not initialized, you are trying to write to an unknown location of the memory.

In best case you get an AccessDenied or something like that but you can also cause strange errors if it happen to write to a memory that is writable to your program. For example you may override value of one or more of your variables

How to Implement an Stl-Style Iterator and Avoid Common Pitfalls