Custom Iterator in C++

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.

See Also: standard library reference

EDIT: std::iterator is deprecated since C++17. See a relating discussion here.

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);
}

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.

Creating an custom iterator for a class that iterates through an array of pointers

Solved by changing some types from the structure.
Because It is an array of pointers, it needs to have:

• value_type should be a T* because every element from the array is a
  pointer

• pointer should be a T** because it points to an array of pointers

• and reference should be a T*& because is a reference through a
  pointer element from the array.

Also, with some help from MatG, the for(auto it: this) should be changed to for(auto it: *this), because we need to use the dereferenced value of this class.
Please correct me if I'm wrong

#pragma once
#include<iostream>
using namespace std;
template<class T>
class Array
{
private:

    T** List; // lista cu pointeri la obiecte de tipul T*

    int Capacity; // dimensiunea listei de pointeri

    int Size; // cate elemente sunt in lista

public:
    

    struct Iterator {

        using iterator_category = std::forward_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = T*;
        using pointer = T **;  // or also value_type*
        using reference = T *&;  // or also value_type&
        Iterator(pointer ptr) : m_ptr(ptr) {}

        reference operator*() const { return *m_ptr; }
        pointer operator->() { return m_ptr; }

        // Prefix increment
        Iterator& operator++() { m_ptr++; return *this; }

        // Postfix increment
        Iterator operator++(int) { Iterator tmp = *this; ++(*this); return tmp; }

        friend bool operator== (const Iterator& a, const Iterator& b) { return a.m_ptr == b.m_ptr; };
        friend bool operator!= (const Iterator& a, const Iterator& b) { return a.m_ptr != b.m_ptr; };

    private:
        pointer m_ptr;
    };

    Iterator begin() { return Iterator(&List[0]); }
    Iterator end() { return Iterator(&List[Size]); }

    Array(); // Lista nu e alocata, Capacity si Size = 0

    ~Array(); // destructor

    Array(int capacity); // Lista e alocata cu 'capacity' elemente

    Array(const Array<T> &otherArray); // constructor de copiere

    T& operator[] (int index); // arunca exceptie daca index este out of range

    const Array<T>& operator+=(T *newElem); // adauga un element de tipul T la sfarsitul listei si returneaza this

    const Array<T>& Insert(int index, const T &newElem); // adauga un element pe pozitia index, retureaza this. Daca index e invalid arunca o exceptie

    const Array<T>& Delete(int index); // sterge un element de pe pozitia index, returneaza this. Daca index e invalid arunca o exceptie

    bool operator=(const Array<T> &otherArray);

    int GetSize();

    int GetCapacity();

    void realocateMemory();

    void printArray();

    bool isIndexValid(int);
};

template<class T>
bool Array<T>::isIndexValid(int index)
{
    //if (index < 0 || index > Size)
    //  throw Exceptions::InvalidIndex;
    return true;
}

template<class T>
void Array<T>::realocateMemory()
{
    T* helper = new T[Size];
    for (int i = 0;i < Size;i++)
        helper[i] = *List[i];

    delete[] List;
    Capacity *= 2;
    List = new T*[Capacity];
    for (int i = 0;i < Size;i++)
        List[i] = new T(helper[i]);
    delete[] helper;
}

template<class T>
int Array<T>::GetSize()
{
    return Size;
}

template<class T>
int Array<T>::GetCapacity()
{
    return Capacity;
}

template<class T>
Array<T>::Array() {
    Capacity = 1;
    Size = 0;
    List = new T*[Capacity];
}

template<class T>
Array<T>::Array(int cap) {
    Capacity = cap;
    List = new T*[Capacity];
}

template<class T>
Array<T>::~Array() {
    Capacity = 0;
    Size = 0;
    delete []List;
}

template<class T>
Array<T>::Array(const Array<T> &otherArray)
{
    delete[]List;
    Size = otherArray.GetSize();
    Capacity = otherArray.GetCapacity();
    List = new T*[Capacity];
    int poz = 0;
    for (auto it : otherArray)
        List[poz++] = it;

}

template<class T>
T& Array<T>::operator[] (int index)
{
    if (!isIndexValid(index))
        throw Exceptions::InvalidIndex;
    return List[index];
}

template<class T>
const Array<T>& Array<T>::operator+=(T *newElem) {
    if (Size == Capacity)
        realocateMemory();
    List[Size++] = newElem;
    return *this;
}

template<class T>
bool Array<T>::operator=(const Array<T> &otherArray)
{
    delete[] List;
    Capacity = otherArray.GetCapacity();
    Size = otherArray.GetSize();
    List = new T*[Capacity];

    for (int i = 0;i < Size;i++)
        List[i] = otherArray[i];    
    return true;
}

template<class T>
const Array<T>& Array<T>::Insert(int index, const T &newElem)
{

    if (Size == Capacity)
        realocateMemory();

    //shift one position to right
    for (int i = Size;i > index;i--)
        List[i] = List[i - 1];

    List[index] = new T(newElem);
    Size++;
    return *this;
}

template<class T>
const Array<T>& Array<T>::Delete(int index)
{
    for (int i = index;i < Size - 1;i++)
        List[i] = List[i + 1];
    Size--;
}

template<class T>
void Array<T>::printArray()
{
    for (int i = 0;i < Size;i++)
        std::cout << *List[i] << ' ';

    cout << "\n---------------------------------------\n";
    for (auto it : *this)
        std::cout <<*it << ' ';

    cout << "\n---------------------------------------\n";
}

Implementing custom iterators in C++11

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.

Iterator for custom container

Looking at your code again, satisfying forward iterator requirements would be tricky, because you essentially generate the lines on the fly. Hence I suggest making an input iterator.

operator++ should just increment m_ptr, nothing unusual. But you might want to store an std::vector iterator instead of a pointer (then, if you enable iterator debuggning for standard containers, it will extend to your iterators).

Then you have two options:

1. Store the current Line inside of the iterator. Then * and -> return a reference and a pointer to it respectively. ++ will need to update this Line after incrementing the pointer/iterator.

2. Return the Line from operator* by value, and change using reference to Line to match the return type. This is unusal, but allowed for input iterators.

   Then operator-> becomes tricky. It can't return a pointer (because there's no Line to point to), so it has to return a helper class by value, which in turn would store a Line (again by value), and overload -> to return a pointer to it. You probably should also change using pointer to match the type of this helper class.

---

Related Topics