Creating My Own Iterators

Creating my own Iterators

You should use Boost.Iterators. It contains a number of templates and concepts to implement new iterators and adapters for existing iterators. I have written an article about this very topic; it's in the December 2008 ACCU magazine. It discusses an (IMO) elegant solution for exactly your problem: exposing member collections from an object, using Boost.Iterators.

If you want to use the stl only, the Josuttis book has a chapter on implementing your own STL iterators.

Can we write our own iterator in Java?

Sure. An iterator is just an implementation of the java.util.Iterator interface. If you're using an existing iterable object (say, a LinkedList) from java.util, you'll need to either subclass it and override its iterator function so that you return your own, or provide a means of wrapping a standard iterator in your special Iterator instance (which has the advantage of being more broadly used), etc.

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.

Creating my own Iterators for non stl container

I never really used iterators before, is it correct ?

It's a good start. The idea is correct, but you are missing a few things. First, you don't have enough operators. Make sure you check the reference and provide every operator that you can sensibly provide (the only ones that may or may not be useful are random-access operators, because it could be harder to implement for this case). Second, you need to provide the iterator traits for your iterator class. This is usually done by creating the necessary nested typedefs in your iterator class (you could also specialize the std::iterator_traits template for your class, but I would say that this is only when you really cannot add the nested typedefs).

Can I inherit my MatrixIterator from std::iterator so stl would be able to understand it as a usual iterator ?

No, you should not, in general, inherit from the std::iterator class. The STL is a template library (generic programming (GP)) and therefore, does not use the base-class inheritance model as in OOP. The STL algorithms take iterators as template arguments, and will generically use them as required by the algorithm (or as possible by the iterator_category trait associated to the iterator type). This is generic programming, not object-oriented programming, it's apples and oranges.

Do you know a better way to do something similar ?

Well, one convenient way to do this is by using a class template like boost::iterator_facade (see ref) which provides a sort of automated "fill in the blanks" mechanism creating iterators. It uses the well-known and very useful Curiously Recurring Template Pattern (or CRTP for short). This is useful because implementing all the operators required for iterators can be quite verbose and repetitive, and the usually only really rely on just a few core operations (which is all you need to "fill in" when using a CRTP class like boost::iterator_facade).

When creating my own data structure, should I use iterators or indices to provide access from the outside?

I don't see why you couldn't get both, if this makes sense for your container.

std::vector has iterators and the at/operator[] methods to provide access with indexes.

The API of your container depends on the operations you want to make available to your clients.

Is the container iterable, i.e. is it possible to iterate over each elements? Then, you should provide an iterator.
Does it make sense to randomly access elements in your container, knowing their address? Then you can also provide the at(size_t)/operator[size_t] methods.
Does it make sense to randomly access elements in your container,
knowing a special "key"? The you should probably provide the at(key_type)/operator[key_type] methods.

As for your question regarding custom iterators or reuse of existing iterators:

If your container is basically a wrapper that adds some insertion/removal logic to an existing container, I think it is fine to publicly typedef the existing iterator, as a custom iterator may miss some features of the the existing iterator, may contain bugs, and will not add any significant feature over the existing iterator.

On the other hand, if you iterate in a non-standard fashion (for instance, I implemented once a recursive_unordered_map that accepted a parent recursive_unordered_map at construction and would iterate both on its own unordered_map and on its parent's (and its parent's parent's...). I had to implement a custom iterator for this.

How to build a basic iterator?

Iterator objects in python conform to the iterator protocol, which basically means they provide two methods: __iter__() and __next__().

The __iter__ returns the iterator object and is implicitly called
at the start of loops.
The __next__() method returns the next value and is implicitly called at each loop increment. This method raises a StopIteration exception when there are no more value to return, which is implicitly captured by looping constructs to stop iterating.

Here's a simple example of a counter:

class Counter:
    def __init__(self, low, high):
        self.current = low - 1
        self.high = high

    def __iter__(self):
        return self

    def __next__(self): # Python 2: def next(self)
        self.current += 1
        if self.current < self.high:
            return self.current
        raise StopIteration

for c in Counter(3, 9):
    print(c)

This will print:

This is easier to write using a generator, as covered in a previous answer:

def counter(low, high):
    current = low
    while current < high:
        yield current
        current += 1

for c in counter(3, 9):
    print(c)

The printed output will be the same. Under the hood, the generator object supports the iterator protocol and does something roughly similar to the class Counter.

David Mertz's article, Iterators and Simple Generators, is a pretty good introduction.

How to create a custom Iterator in Java?

A minimal example would be to return an empty iterator, whose hasNext() always returns false and next() will throw NoSuchElementException.

public Iterator<Foo> iterator() {
    return new Iterator<Foo>() {
        public boolean hasNext() { 
            return false;
        }
        public Foo next() {
            throw new NoSuchElementException();
        }
    };
}

Of course most iterators have states. For example you can iterate from 0 to the integer value the Foo instance holds.

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Foo implements Iterable<Foo> {
    private final int value;

    public Foo(final int value) {
        this.value = value;
    }

    @Override
    public Iterator<Foo> iterator() {
        return new Iterator<Foo>() {
            private Foo foo = new Foo(0);

            @Override
            public boolean hasNext() {
                return foo.value < Foo.this.value;
            }

            @Override
            public Foo next() {
                if (!hasNext()) throw new NoSuchElementException();

                Foo cur = foo;
                foo = new Foo(cur.value+1);
                return cur;
            }
        };
    }

    public static void main(String[] args) {
        Foo foo = new Foo(10);
        for (Foo f: foo) {
            System.out.println(f.value);
        }
    }
}

Creating an Iterator with C++20 Concepts for custom container

By and large, the C++20 way of defining iterators does away with explicitly tagging the type, and instead relies on concepts to just check that a given type happens to respect the iterator category's requirements.

This means that you can now safely duck-type your way to victory while supporting clean overload resolution and error messages:

struct my_iterator {
  // No need for tagging or anything special, just implement the required interface.
};

If you want to ensure that a given type fulfills the requirements of a certain iterator category, you static_assert the concept on that type:

#include <iterator>

static_assert(std::forward_iterator<my_iterator>);

Enforcing that a function only accepts a certain iterator category is done by using the concept in your template arguments.

#include <iterator>

template<std::forward_iterator Ite, std::sentinel_for<Ite> Sen>
void my_algorithm(Ite begin, Sen end) {
 // ...
}

std::sentinel_for<> is now used for the end iterator instead of using Ite twice. It allows to optionally use a separate type for the end iterator, which is sometimes convenient, especially for input iterators.

For example:

struct end_of_stream_t {};
constexpr end_of_stream_t end_of_stream{};

struct my_input_iterator {
  // N.B. Not a complete implementation, just demonstrating sentinels.
  some_stream_type* data_stream;

  bool operator==(end_of_stream_t) const { return data_stream->empty(); }
};

template<std::input_iterator Ite, std::sentinel_for<Ite> Sen>
void my_algorithm(Ite begin, Sen end) {
  while(begin != end) {
    //...
  }
}

void foo(some_stream_type& stream) {
  my_algorithm(my_input_iterator{&stream}, end_of_stream);
}

Defining iterator of my own container

The C++ specification on what exactly an STL container is mandates that any STL container type have several different fields available. Some, like begin() and end(), are functions, while others, like iterator, are types. These restrictions also apply to iterators. This allows C++ template functions to introspect on their types of their arguments to look up more properties. For example, all STL iterator types must define an iterator_category field containing a type encoding their capabilities. This way, the STL algorithms can have different implementations of different functions based on the power of the iterators they accept. A class example is the distance function, which takes two iterators and returns the number of spaces between them. If the input is a lowly ForwardIterator or BidirectionalIterator this works by marching the iterators forward and counting how many steps were took, which runs in O(n). If the input is a RandomAccessIterator, then the iterators can just be subtracted to get the result in O(1).

Prior to C++17, the recommendation was to include the <iterator> header and inherit from std::iterator to automatically generate the necessary nested types you’d need (reference, pointer, etc.). That type is now deprecated, and so you’ll need to manually either add typedefs or specialize std::iterator_traits to export this information.

As for what operators you need to overload, at a bare minimum you need to get ++ (prefix and postfix), ==, !=, * (pointer dereference), and -> defined. All iterator types support this. For bidirectional iterators or higher, you should also have -- defined (prefix and postfix). Finally, for random-access iterators, you should support [], +, +=, - (back up many steps and subtract two iterators), -=, <, >, <=, and >=.

Hope this helps!

iterator creation in my own class c++11

At least if I understand your question correctly, you want something like:

class myclass { 
    std::string str;
public:
    std::string::iterator begin() { return str.begin(); }
    std::string::iterator end() { return str.end(); }
};

void func(myclass &m) { 
    for (auto a : m)
        // ...
}