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

Question

I made a collection for which I want to provide an STL-style, random-access iterator. I was searching around for an example implementation of an iterator but I didn't find any. I know about the need for const overloads of [] and * operators. What are the requirements for an iterator to be "STL-style" and what are some other pitfalls to avoid (if any)?

Additional context: This is for a library and I don't want to introduce any dependency on it unless I really need to. I write my own collection to be able to provide binary compatibility between C++03 and C++11 with the same compiler (so no STL which would probably break).

Answer 1

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.

Answer 2

The iterator_facade documentation from Boost.Iterator provides what looks like a nice tutorial on implementing iterators for a linked list. Could you use that as a starting point for building a random-access iterator over your container?

If nothing else, you can take a look at the member functions and typedefs provided by iterator_facade and use it as a starting point for building your own.

Answer 3

Here is sample of raw pointer iterator.

You shouldn't use iterator class to work with raw pointers!

#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <assert.h>

template<typename T>
class ptr_iterator
    : public std::iterator<std::forward_iterator_tag, T>
{
    typedef ptr_iterator<T>  iterator;
    pointer pos_;
public:
    ptr_iterator() : pos_(nullptr) {}
    ptr_iterator(T* v) : pos_(v) {}
    ~ptr_iterator() {}

    iterator  operator++(int) /* postfix */         { return pos_++; }
    iterator& operator++()    /* prefix */          { ++pos_; return *this; }
    reference operator* () const                    { return *pos_; }
    pointer   operator->() const                    { return pos_; }
    iterator  operator+ (difference_type v)   const { return pos_ + v; }
    bool      operator==(const iterator& rhs) const { return pos_ == rhs.pos_; }
    bool      operator!=(const iterator& rhs) const { return pos_ != rhs.pos_; }
};

template<typename T>
ptr_iterator<T> begin(T *val) { return ptr_iterator<T>(val); }


template<typename T, typename Tsize>
ptr_iterator<T> end(T *val, Tsize size) { return ptr_iterator<T>(val) + size; }

Raw pointer range based loop workaround. Please, correct me, if there is better way to make range based loop from raw pointer.

template<typename T>
class ptr_range
{
    T* begin_;
    T* end_;
public:
    ptr_range(T* ptr, size_t length) : begin_(ptr), end_(ptr + length) { assert(begin_ <= end_); }
    T* begin() const { return begin_; }
    T* end() const { return end_; }
};

template<typename T>
ptr_range<T> range(T* ptr, size_t length) { return ptr_range<T>(ptr, length); }

And simple test

void DoIteratorTest()
{
    const static size_t size = 10;
    uint8_t *data = new uint8_t[size];
    {
        // Only for iterator test
        uint8_t n = '0';
        auto first = begin(data);
        auto last = end(data, size);
        for (auto it = first; it != last; ++it)
        {
            *it = n++;
        }

        // It's prefer to use the following way:
        for (const auto& n : range(data, size))
        {
            std::cout << " char: " << static_cast<char>(n) << std::endl;
        }
    }
    {
        // Only for iterator test
        ptr_iterator<uint8_t> first(data);
        ptr_iterator<uint8_t> last(first + size);
        std::vector<uint8_t> v1(first, last);

        // It's prefer to use the following way:
        std::vector<uint8_t> v2(data, data + size);
    }
    {
        std::list<std::vector<uint8_t>> queue_;
        queue_.emplace_back(begin(data), end(data, size));
        queue_.emplace_back(data, data + size);
    }
}

Answer 4

Thomas Becker wrote a useful article on the subject here.

There was also this (perhaps simpler) approach that appeared previously on SO: How to correctly implement custom iterators and const_iterators?

Answer 5

First of all you can look here for a list of the various operations the individual iterator types need to support.

Next, when you have made your iterator class you need to either specialize std::iterator_traits for it and provide some necessary typedefs (like iterator_category or value_type) or alternatively derive it from std::iterator, which defines the needed typedefs for you and can therefore be used with the default std::iterator_traits.

disclaimer: I know some people don't like cplusplus.com that much, but they provide some really useful information on this.

Answer 6

I was/am in the same boat as you for different reasons (partly educational, partly constraints). I had to re-write all the containers of the standard library and the containers had to conform to the standard. That means, if I swap out my container with the stl version, the code would work the same. Which also meant that I had to re-write the iterators.

Anyway, I looked at EASTL. Apart from learning a ton about containers that I never learned all this time using the stl containers or through my undergraduate courses. The main reason is that EASTL is more readable than the stl counterpart (I found this is simply because of the lack of all the macros and straight forward coding style). There are some icky things in there (like #ifdefs for exceptions) but nothing to overwhelm you.

As others mentioned, look at cplusplus.com's reference on iterators and containers.

Answer 7

I was trying to solve the problem of being able to iterate over several different text arrays all of which are stored within a memory resident database that is a large struct.

The following was worked out using Visual Studio 2017 Community Edition on an MFC test application. I am including this as an example as this posting was one of several that I ran across that provided some help yet were still insufficient for my needs.

The struct containing the memory resident data looked something like the following. I have removed most of the elements for the sake of brevity and have also not included the Preprocessor defines used (the SDK in use is for C as well as C++ and is old).

What I was interested in doing is having iterators for the various WCHAR two dimensional arrays which contained text strings for mnemonics.

typedef struct  tagUNINTRAM {
    // stuff deleted ...
    WCHAR   ParaTransMnemo[MAX_TRANSM_NO][PARA_TRANSMNEMO_LEN]; /* prog #20 */
    WCHAR   ParaLeadThru[MAX_LEAD_NO][PARA_LEADTHRU_LEN];   /* prog #21 */
    WCHAR   ParaReportName[MAX_REPO_NO][PARA_REPORTNAME_LEN];   /* prog #22 */
    WCHAR   ParaSpeMnemo[MAX_SPEM_NO][PARA_SPEMNEMO_LEN];   /* prog #23 */
    WCHAR   ParaPCIF[MAX_PCIF_SIZE];            /* prog #39 */
    WCHAR   ParaAdjMnemo[MAX_ADJM_NO][PARA_ADJMNEMO_LEN];   /* prog #46 */
    WCHAR   ParaPrtModi[MAX_PRTMODI_NO][PARA_PRTMODI_LEN];  /* prog #47 */
    WCHAR   ParaMajorDEPT[MAX_MDEPT_NO][PARA_MAJORDEPT_LEN];    /* prog #48 */
    //  ... stuff deleted
} UNINIRAM;

The current approach is to use a template to define a proxy class for each of the arrays and then to have a single iterator class that can be used to iterate over a particular array by using a proxy object representing the array.

A copy of the memory resident data is stored in an object that handles reading and writing the memory resident data from/to disk. This class, CFilePara contains the templated proxy class (MnemonicIteratorDimSize and the sub class from which is it is derived, MnemonicIteratorDimSizeBase) and the iterator class, MnemonicIterator.

The created proxy object is attached to an iterator object which accesses the necessary information through an interface described by a base class from which all of the proxy classes are derived. The result is to have a single type of iterator class which can be used with several different proxy classes because the different proxy classes all expose the same interface, the interface of the proxy base class.

The first thing was to create a set of identifiers which would be provided to a class factory to generate the specific proxy object for that type of mnemonic. These identifiers are used as part of the user interface to identify the particular provisioning data the user is interested in seeing and possibly modifying.

const static DWORD_PTR dwId_TransactionMnemonic = 1;
const static DWORD_PTR dwId_ReportMnemonic = 2;
const static DWORD_PTR dwId_SpecialMnemonic = 3;
const static DWORD_PTR dwId_LeadThroughMnemonic = 4;

The Proxy Class

The templated proxy class and its base class are as follows. I needed to accommodate several different kinds of wchar_t text string arrays. The two dimensional arrays had different numbers of mnemonics, depending on the type (purpose) of the mnemonic and the different types of mnemonics were of different maximum lengths, varying between five text characters and twenty text characters. Templates for the derived proxy class was a natural fit with the template requiring the maximum number of characters in each mnemonic. After the proxy object is created, we then use the SetRange() method to specify the actual mnemonic array and its range.

// proxy object which represents a particular subsection of the
// memory resident database each of which is an array of wchar_t
// text arrays though the number of array elements may vary.
class MnemonicIteratorDimSizeBase
{
    DWORD_PTR  m_Type;

public:
    MnemonicIteratorDimSizeBase(DWORD_PTR x) { }
    virtual ~MnemonicIteratorDimSizeBase() { }

    virtual wchar_t *begin() = 0;
    virtual wchar_t *end() = 0;
    virtual wchar_t *get(int i) = 0;
    virtual int ItemSize() = 0;
    virtual int ItemCount() = 0;

    virtual DWORD_PTR ItemType() { return m_Type; }
};

template <size_t sDimSize>
class MnemonicIteratorDimSize : public MnemonicIteratorDimSizeBase
{
    wchar_t    (*m_begin)[sDimSize];
    wchar_t    (*m_end)[sDimSize];

public:
    MnemonicIteratorDimSize(DWORD_PTR x) : MnemonicIteratorDimSizeBase(x), m_begin(0), m_end(0) { }
    virtual ~MnemonicIteratorDimSize() { }

    virtual wchar_t *begin() { return m_begin[0]; }
    virtual wchar_t *end() { return m_end[0]; }
    virtual wchar_t *get(int i) { return m_begin[i]; }

    virtual int ItemSize() { return sDimSize; }
    virtual int ItemCount() { return m_end - m_begin; }

    void SetRange(wchar_t (*begin)[sDimSize], wchar_t (*end)[sDimSize]) {
        m_begin = begin; m_end = end;
    }

};

The Iterator Class

The iterator class itself is as follows. This class provides just basic forward iterator functionality which is all that is needed at this time. However I expect that this will change or be extended when I need something additional from it.

class MnemonicIterator
{
private:
    MnemonicIteratorDimSizeBase   *m_p;  // we do not own this pointer. we just use it to access current item.
    int      m_index;                    // zero based index of item.
    wchar_t  *m_item;                    // value to be returned.

public:
    MnemonicIterator(MnemonicIteratorDimSizeBase *p) : m_p(p) { }
    ~MnemonicIterator() { }

    // a ranged for needs begin() and end() to determine the range.
    // the range is up to but not including what end() returns.
    MnemonicIterator & begin() { m_item = m_p->get(m_index = 0); return *this; }                 // begining of range of values for ranged for. first item
    MnemonicIterator & end() { m_item = m_p->get(m_index = m_p->ItemCount()); return *this; }    // end of range of values for ranged for. item after last item.
    MnemonicIterator & operator ++ () { m_item = m_p->get(++m_index); return *this; }            // prefix increment, ++p
    MnemonicIterator & operator ++ (int i) { m_item = m_p->get(m_index++); return *this; }       // postfix increment, p++
    bool operator != (MnemonicIterator &p) { return **this != *p; }                              // minimum logical operator is not equal to
    wchar_t * operator *() const { return m_item; }                                              // dereference iterator to get what is pointed to
};

The proxy object factory determines which object to created based on the mnemonic identifier. The proxy object is created and the pointer returned is the standard base class type so as to have a uniform interface regardless of which of the different mnemonic sections are being accessed. The SetRange() method is used to specify to the proxy object the specific array elements the proxy represents and the range of the array elements.

CFilePara::MnemonicIteratorDimSizeBase * CFilePara::MakeIterator(DWORD_PTR x)
{
    CFilePara::MnemonicIteratorDimSizeBase  *mi = nullptr;

    switch (x) {
    case dwId_TransactionMnemonic:
        {
            CFilePara::MnemonicIteratorDimSize<PARA_TRANSMNEMO_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_TRANSMNEMO_LEN>(x);
            mk->SetRange(&m_Para.ParaTransMnemo[0], &m_Para.ParaTransMnemo[MAX_TRANSM_NO]);
            mi = mk;
        }
        break;
    case dwId_ReportMnemonic:
        {
            CFilePara::MnemonicIteratorDimSize<PARA_REPORTNAME_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_REPORTNAME_LEN>(x);
            mk->SetRange(&m_Para.ParaReportName[0], &m_Para.ParaReportName[MAX_REPO_NO]);
            mi = mk;
        }
        break;
    case dwId_SpecialMnemonic:
        {
            CFilePara::MnemonicIteratorDimSize<PARA_SPEMNEMO_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_SPEMNEMO_LEN>(x);
            mk->SetRange(&m_Para.ParaSpeMnemo[0], &m_Para.ParaSpeMnemo[MAX_SPEM_NO]);
            mi = mk;
        }
        break;
    case dwId_LeadThroughMnemonic:
        {
            CFilePara::MnemonicIteratorDimSize<PARA_LEADTHRU_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_LEADTHRU_LEN>(x);
            mk->SetRange(&m_Para.ParaLeadThru[0], &m_Para.ParaLeadThru[MAX_LEAD_NO]);
            mi = mk;
        }
        break;
    }

    return mi;
}

Using the Proxy Class and Iterator

The proxy class and its iterator are used as shown in the following loop to fill in a CListCtrl object with a list of mnemonics. I am using std::unique_ptr so that when the proxy class i not longer needed and the std::unique_ptr goes out of scope, the memory will be cleaned up.

What this source code does is to create a proxy object for the array within the struct which corresponds to the specified mnemonic identifier. It then creates an iterator for that object, uses a ranged for to fill in the CListCtrl control and then cleans up. These are all raw wchar_t text strings which may be exactly the number of array elements so we copy the string into a temporary buffer in order to ensure that the text is zero terminated.

    std::unique_ptr<CFilePara::MnemonicIteratorDimSizeBase> pObj(pFile->MakeIterator(m_IteratorType));
    CFilePara::MnemonicIterator pIter(pObj.get());  // provide the raw pointer to the iterator who doesn't own it.

    int i = 0;    // CListCtrl index for zero based position to insert mnemonic.
    for (auto x : pIter)
    {
        WCHAR szText[32] = { 0 };     // Temporary buffer.

        wcsncpy_s(szText, 32, x, pObj->ItemSize());
        m_mnemonicList.InsertItem(i, szText);  i++;
    }

Answer 8

And now a keys iterator for range-based for loop.

template<typename C>
class keys_it
{
    typename C::const_iterator it_;
public:
    using key_type        = typename C::key_type;
    using pointer         = typename C::key_type*;
    using difference_type = std::ptrdiff_t;

    keys_it(const typename C::const_iterator & it) : it_(it) {}

    keys_it         operator++(int               ) /* postfix */ { return it_++         ; }
    keys_it&        operator++(                  ) /*  prefix */ { ++it_; return *this  ; }
    const key_type& operator* (                  ) const         { return it_->first    ; }
    const key_type& operator->(                  ) const         { return it_->first    ; }
    keys_it         operator+ (difference_type v ) const         { return it_ + v       ; }
    bool            operator==(const keys_it& rhs) const         { return it_ == rhs.it_; }
    bool            operator!=(const keys_it& rhs) const         { return it_ != rhs.it_; }
};

template<typename C>
class keys_impl
{
    const C & c;
public:
    keys_impl(const C & container) : c(container) {}
    const keys_it<C> begin() const { return keys_it<C>(std::begin(c)); }
    const keys_it<C> end  () const { return keys_it<C>(std::end  (c)); }
};

template<typename C>
keys_impl<C> keys(const C & container) { return keys_impl<C>(container); }

Usage:

std::map<std::string,int> my_map;
// fill my_map
for (const std::string & k : keys(my_map))
{
    // do things
}

That's what i was looking for. But nobody had it, it seems.

You get my OCD code alignment as a bonus.

As an exercise, write your own for values(my_map)