Custom Iterator in C++

Question

I have a class TContainer that is an aggregate of several stl collections pointers to TItems class.

I need to create an Iterator to traverse the elements in all the collections in my TContainer class abstracting the client of the inner workings.

What would be a good way to do this?. Should I crate a class that extends an iterator (if so, what iterator class should I extend), should I create an iterator class that is an aggregate of iterators?

I only need a FORWARD_ONLY iterator.

I.E, If this is my container:

typedef std::vector <TItem*> ItemVector;
class TContainer {
   std::vector <ItemVector *> m_Items;
};

What would be a good Iterator to traverse all the items contained in the vectors of the m_Items member variable.

Answer 1

Adding to the answer that suggests using Boost.iterator's iterator_facade in order to implement custom iterators, I have written a standalone, header-only library that mimics (the important) parts of what Boost.iterator provides. The benefit being that there is no Boost dependency (nor any other dependency except C++17).

A distinct feature of my library is that by using it, your iterators will always follow the standard's requirement on the iterator's interface and nothing more. This makes sure that downstream users won't depend on an implementation detail of the current iterator implementation (that might be removed/changed in the future). This should help to increase portability and maintainability.

You can find the library at https://github.com/Krzmbrzl/iterators.

Here's an example of how to create a custom iterator with this library:

#include <iterators/iterator_facade.hpp>

#include <cstddef>
#include <iostream>
#include <iterator>

struct MyCore {
    // Declare what iterator category we are aiming for
    using  target_iterator_category = std::input_iterator_tag;

    // These functions are required for all iterator cores

    MyCore(int *ptr) : m_ptr(ptr) {}
    MyCore(const MyCore &) = default;
    MyCore &operator=(const MyCore &) = default;

    int &dereference() const { return *m_ptr; }

    void increment() { m_ptr += 1; }

    bool equals(const MyCore &other) const { return m_ptr == other.m_ptr; }

private:
    int * m_ptr = nullptr;
};

using MyIterator = iterators::iterator_facade< MyCore >;


// Example usage
int main() {
    int numbers[3] = { 1, 2, 3 };

    MyIterator iter(MyCore{numbers});

    std::cout << *iter << "\n";
    iter++;
    std::cout << *iter << "\n";
    ++iter;
    std::cout << *iter << "\n";

    return 0;
}

Answer 2

This is the simplest code I was able to produce (for custom iterators). Note that I'm only beginning to explore this area. This calls built-in upper_bound function to perform binary search on an integer function, x^2 as an example.

#include <algorithm>
#include <iostream>

using namespace std;

class Iter
{
  public:
  int x;
  Iter() { x = -1; }
  Iter(int a) { x = a; }

  bool operator!=(Iter &i2) const { return x != i2.x; }
  void operator++() { x++; }
  void operator+=(int b) { x += b; }
  int operator-(const Iter &i2) const { return x - i2.x; }
  int operator*() const {
    cout << "calculating for x " << x << endl;
    return x*x;
  }

  typedef random_access_iterator_tag iterator_category;
  typedef int value_type;
  typedef int difference_type;
  typedef int* pointer;
  typedef int& reference;
};

main ()
{
  ios::sync_with_stdio(false);
  cout << upper_bound(Iter(0), Iter(100), 40).x << endl;
}

// :collapseFolds=1:folding=explicit:

And this is how the output looks like:

calculating for x 50
calculating for x 25
calculating for x 12
calculating for x 6
calculating for x 9
calculating for x 8
calculating for x 7
7

Answer 3

First let's generalize a little bit:

typedef int value_type;
typedef std::vector<value_type*> inner_range;
typedef std::vector<inner_range*> outer_range;

Now the iterator:

struct my_iterator : std::iterator_traits<inner_range::iterator> 
{
    typedef std::forward_iterator_tag iterator_category;

    my_iterator(outer_range::iterator const & outer_iterator, 
                outer_range::iterator const & outer_end)
    : outer_iterator(outer_iterator), outer_end(outer_end)
    { 
        update();
    }

    my_iterator & operator++()
    {
        ++inner_iterator;
        if(inner_iterator == inner_end)
        {
            ++outer_iterator;
            update();
        }
        return *this;
    }

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

    bool operator==(my_iterator const & rhs) const
    {   
        bool lhs_end = outer_iterator == outer_end;
        bool rhs_end = rhs.outer_iterator == rhs.outer_end;
        if(lhs_end && rhs_end)
            return true;
        if(lhs_end != rhs_end)
            return false;
        return outer_iterator == rhs.outer_iterator 
            && inner_iterator == rhs.inner_iterator;
    }

private:

    outer_range::iterator outer_iterator, outer_end;
    inner_range::iterator inner_iterator, inner_end;

    void update()
    {
        while(outer_iterator != outer_end)
        {
            inner_iterator = (*outer_iterator)->begin();
            inner_end = (*outer_iterator)->end();
            if(inner_iterator == inner_end)
                ++outer_iterator;
            else
                break;
        }
    }    
};

This class assumes than the outer iterators contain pointers to the inner ranges, which was a requirement in your question. This is reflected in the update member, in the arrows before begin() and end(). You can replace these arrows with dots if you want to use this class in the more common situation where the outer iterator contains the inner ranges by value. Note BTW that this class is agnostic to the fact that the inner range contains pointers, only clients of the class will need to know that.

The code could be shorter if we use boost::iterator_facade but it's not necessary to add a boost dependency for something so simple. Besides, the only tricky parts are the equality and increment operations, and we have to code those anyway.

I've left the following boiler-plate members as "exercises for the reader":

• postfix increment iterator
• operator!=
• default constructor
• operator->

Another interesting exercise is to turn this into a template which works with arbitrary containers. The code is basically the same except that you have to add typename annotations in a few places.

Example of use:

int main()
{
    outer_type outer;
    int a = 0, b = 1, c = 2;
    inner_type inner1, inner2;
    inner1.push_back(&a);
    inner1.push_back(&b);
    inner2.push_back(&c);
    outer.push_back(&inner1);
    outer.push_back(&inner2);

    my_iterator it(outer.begin(), outer.end());
                e(outer.end(), outer.end());
    for(; it != e; ++it)
        std::cout << **it << "\n";
}

Which prints:

0 1 2

Answer 4

If you have access to Boost, using iterator_facade is the most robust solution, and it's pretty simple to use.

Answer 5

Check the Views Template Library.

Especially check

1. Union View presenting two containers concatenated.
2. Concatenation View presenting a collection of containers concatenated.

Answer 6

An iterator is just a class that supports a certain interface. At minimum, you will want to be able to:

• increment and/or decrement it
• dereference it to get the object it "points" to
• test it for equality and inequality
• copy and assign it

Once you have a class that can do that sensibly for your collection, you will need to modify the collection to have functions that return iterators. At minimum you will want

• a begin() function that returns an instance of your new iterator type positioned at the first element
• an end() function that returns an iterator which is (possibly notionally) positioned at one past the end of the items in your container

Answer 7

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.