Maintain Your Iterations – Iterators Customization – Part 3

So you know that iterators can make your code more maintainable and save you a lot of time. But what can you do when it comes to your own collections? How can you create an iterators-friendly collection to fit your legacy iterators-friendly code infrastructure?

Previous article on the series: Maintain Your Iterations – Insecure Iterations – Part 2

Iterators-Friendly Collection Requirements

Let’s start with the requirements of an iterators-friendly collection. As we discussed in the first article in this series, the following functions are necessary for an iterators-friendly collection:

cppreference – iterator

However, to apply them inside our collection, we have to create our own iterator structure. But what are the requirements for an iterator structure?

Iterator Structure Requirements

Any iterator should supply the types that can be accessed by std::iterator_traits:

As long as the iterator structure supplies those types, your iterator will be supported by any function that support the standard iterators. Until C++17, you could inherit from std::iterator template class, which generated those member types for us, but due to hard maintenance issues, it was declared deprecated in C++17 and the usage is highly not recommended.

This leaves us with two optional solutions:

1. For every iterator structure we’ll create, we’ll manually add those fields and hope to not mistake with the names.
2. We have to find a maintainable way to create a base iterators structure.

I always recommend you to choose the second option, because you never know who will be the next to create another iterator structure, and one day it might pay off.

An important attention before we create a base iterator class we need to pay to the fact that a base class like this one got deprecated in C++17, due to potential errors this one could lead to. Here is how it looked before C++17:

template<
    class Category,
    class T,
    class Distance = std::ptrdiff_t,
    class Pointer = T*,
    class Reference = T&
> struct iterator;

As you can see, we could create it with a lot of wrong ways, without getting a warning. Some ways, for example:

class my_iterator : public iterator<int, float> {};
class my_iterator1 : public iterator<std::random_access_iterator_tag, 
                     float, size_t, int, int> {};
class my_iterator2 : public iterator<int, std::random_access_iterator_tag> {};
// etc...

So we have to learn from previous mistakes, and we got some new features in C++20 that can help us with that. First, let’s define an iterator tag type:

template <typename T>
concept IteratorTag = std::is_base_of_v<std::input_iterator_tag, T> || 
                      std::is_base_of_v<std::output_iterator_tag, T>;

Now we can create an iterator base class (Pay attention that this class might not fit for any possible case, and for more specific cases, we’ll have to create a more customized class):

template <IteratorTag ItTag, typename T>
struct base_legacy_iterator {
    typedef ItTag	                        iterator_category;
    typedef T		                        value_type;
    typedef T*                              pointer;
    typedef T&	                            reference;
    typedef std::iter_difference_t<pointer> difference_type;
    // Iterator Concept: if (ItTag == random_access_iterator_tag) 
    // std::contiguous_iterator_tag; else ItTag;
    using iterator_concept = std::conditional<std::is_same_v<ItTag, 
          std::random_access_iterator_tag>, std::contiguous_iterator_tag, ItTag>;
};

Custom Iterator Implementation

Now that we have a basic iterator class, it’s time for us to create our custom iterator:

template <typename T>
class my_iterator : public base_legacy_iterator<std::random_access_iterator_tag, T> {
public:
    // A convenient access to inherited type members
    using base_it = base_legacy_iterator<std::random_access_iterator_tag, T>;

    // Ctors & Assign Operators & Dtor
    explicit my_iterator<T>(T* data = nullptr) : _data(data) {}
    my_iterator<T>(const my_iterator<T>&) = default;
    my_iterator<T>(my_iterator<T>&&) noexcept = default;
    my_iterator<T>& operator=(const my_iterator<T>&) = default;
    my_iterator<T>& operator=(my_iterator<T>&&) noexcept = default;
    my_iterator<T>& operator=(T* data) { _data = data; return *this; };
    ~my_iterator<T>() = default;

    // Is null
    explicit operator bool() const { return _data; }

    /* Required Operators For Iterator Category */
    
    // Required Compare Operators
    bool operator==(const my_iterator<T>& ref) const { return _data == ref._data; }
    bool operator!=(const my_iterator<T>& ref) const { return !(*this == ref); }
    typename base_it::difference_type operator-(const my_iterator<T>& ref) 
                      { return std::distance(ref._data, _data); }
    
    // Required Action Operators
    my_iterator<T>& operator+=(const typename base_it::difference_type& diff) 
    { _data += diff; return *this; }
    my_iterator<T>& operator-=(const typename base_it::difference_type& diff) 
    { _data -= diff; return *this; }
    my_iterator<T>& operator++() { ++_data; return *this; }
    my_iterator<T> operator++(int) { auto temp = *this; ++_data; return temp; }
    my_iterator<T>& operator--() { --_data; return *this; }
    my_iterator<T> operator--(int) { auto temp = *this; --_data; return temp; }
    my_iterator<T> operator+(const typename base_it::difference_type& diff) 
    { auto temp = *this; temp._data += diff; return temp; }
    my_iterator<T> operator-(const typename base_it::difference_type& diff) 
    { auto temp = *this; temp._data -= diff; return temp; }
    
    // Required Access Operators
    T& operator*() { return *_data; }
    const T& operator*() const  { return *_data; }
    T* operator->() const  { return _data; }

private:
    T* _data;
};

Special thanks for Enzo answer on Stack Overflow.

As you can see, there are six main parts in out iterator structure:

1. Ctors, Dtors, and assign operators implementations (Rule of five)
2. Is null boolean casting operator
3. Required compare operators of defined iterator category
4. Required action operators of defined iterator category
5. Required access operators of defined iterator category
6. Pointer to data with access to the next/previous items as required of defined iterator category

Custom Collection Implementation

Now that we have an iterator implementation, we can implement our collection. An important note: The iterator I created is answer the requirements for a random-access iterator, which means that the container should follow this guideline.

First, let’s create a new structure to contain in our collection.

template <typename T>
concept HasMul = requires() {
    { T() * T() };
};

template <HasMul T>
class my_item {
public:
    my_item(const T &a, const T &b) : value_a(a), value_b (b) {}

    T item() { return value_a * value_b; }
    void set_a(T a) { value_a = a; }
    void set_b(T b) { value_b = b; }

private:
    T value_a, value_b;
};

Now for our collection:

template <template <typename ...> typename Container, HasMul ItemT>
class my_item_collection {
public:

    /* Define iterators types & collection management types */

    typedef my_item<ItemT> item;
    typedef my_iterator<item> iterator;
    typedef my_iterator<const item> const_iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    typedef typename iterator::pointer pointer;
    typedef typename const_iterator::pointer const_pointer;
    typedef typename iterator::reference reference;
    typedef typename const_iterator::reference const_reference;
    typedef size_t size_type;

    /* Custom collection operations */

    void add_item(const ItemT &a, const ItemT &b) {
        items.emplace_back(a, b);
    }

    iterator get_item(size_t idx) {
        auto res = items.begin();
        return std::advance(res, idx);
    }

    /* Required Iterators Access Methods */

    iterator begin() { return iterator(&*items.begin()); }
    iterator end() { return iterator(&*items.end()); }
    [[nodiscard]] const_iterator cbegin() 
                  const { return const_iterator(&*items.cbegin()); }
    [[nodiscard]] const_iterator cend() 
      const { return const_iterator(&*items.cend()); }
    reverse_iterator rbegin() { return reverse_iterator(&*items.rbegin()); }
    reverse_iterator rend() { return reverse_iterator(&*items.rend()); }
    [[nodiscard]] const_reverse_iterator crbegin() 
      const { return const_reverse_iterator(&*items.rbegin()); }
    [[nodiscard]] const_reverse_iterator crend() 
      const { return const_reverse_iterator(&*items.rend()); }

    [[nodiscard]] bool empty() const { return items.empty(); }
    [[nodiscard]] size_type size() const { return items.size(); }

private:
    Container<my_item<ItemT>> items;
};

Here we have four main sections:

1. Iterators types & collection management types definitions. In order to return iterators, we should keep the returned iterator type so when we want to use it outside the class and modify it by algorithm requirements, the access will be easier. Moreover, the std collection supplies this data, so in order to maintain our code without critical modifications, our collection should support it too.
2. Custom collection operations to management elements.
3. Required iterators access methods – In order to maintain our code, and to make our collection an iterators-friendly collection we should supply these methods. As an example, an important iterators feature that our collection supports using begin() and end() methods is range-based for-loops (or for-each loops).
4. Items container (it can be a simple pointers array, but it’s better to avoid heap memory management to avoid memory leakage as much as possible).

A collection usage example:

int main() {
    my_item_collection<std::vector, int> collection;
    collection.add_item(1, 2);
    collection.add_item(3, 4);
    collection.add_item(5, 6);

    for (auto &elem : collection) {
        std::cout << elem.item() << std::endl;
    }
    return EXIT_SUCCESS;
}

Now in order to maintain our code for new collections, we can take the first section and separate it to an independent generic structure:

template <template <typename ...> typename IteratorType, typename Item>
struct use_collection_custom_iterator {
    typedef IteratorType<Item> iterator;
    typedef IteratorType<const Item> const_iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    typedef typename iterator::pointer pointer;
    typedef typename const_iterator::pointer const_pointer;
    typedef typename iterator::reference reference;
    typedef typename const_iterator::reference const_reference;
    typedef size_t size_type;
};

This will shrink our collection only for the necessary custom sections, which depend on our container:

template <template <typename ...> typename Container, HasMul ItemT>
using my_collection_iterator = use_collection_iterator<Container, my_item<ItemT>>;

template <template <typename ...> typename Container, HasMul ItemT>
class my_item_collection : public my_collection_iterator<Container, ItemT> {
public:

    // A convenient access to inherited type members
    using base_types = my_collection_iterator<Container, ItemT>;

    /* Custom collection operations */

    void add_item(const ItemT &a, const ItemT &b) {
        items.emplace_back(a, b);
    }

    typename base_types::iterator get_item(size_t idx) {
        auto res = items.begin();
        return std::advance(res, idx);
    }

    /* Required Iterators Access Methods */

    typename base_types::iterator begin() 
    { return typename base_types::iterator(&*items.begin()); }
    typename base_types::iterator end() 
    { return typename base_types::iterator(&*items.end()); }
    [[nodiscard]] typename base_types::const_iterator cbegin() const 
    { return const_iterator(&*items.cbegin()); }
    [[nodiscard]] typename base_types::const_iterator cend() const 
    { return const_iterator(&*items.cend()); }
    typename base_types::reverse_iterator rbegin() 
    { return reverse_iterator(&*items.rbegin()); }
    typename base_types::reverse_iterator rend() 
    { return reverse_iterator(&*items.rend()); }
    [[nodiscard]] typename base_types::const_reverse_iterator crbegin() 
    const { return const_reverse_iterator(&*items.crbegin()); }
    [[nodiscard]] typename base_types::const_reverse_iterator crend() 
    const { return const_reverse_iterator(&*items.crend()); }

    [[nodiscard]] bool empty() const { return items.empty(); }
    [[nodiscard]] typename base_types::size_type size() const { return items.size(); }

private:
    Container<my_item<ItemT>> items;
};

However, it’s a lot of work for a collection that managing its items using a std container. Can we simplify it for such cases?

Simplify Custom Collection for std Container

std containers already implementing iterators inside them, whenever we use std containers to managing items inside our collection, we can use their iterators.

First, define an iterators-friendly container type:

template <template <typename ...> typename Container, typename T>
concept IteratorsFriendlyContainerType = requires (Container<T> container) {
    typename decltype(container)::pointer;
    typename decltype(container)::const_pointer;
    typename decltype(container)::reference;
    typename decltype(container)::const_reference;
    typename decltype(container)::iterator;
    typename decltype(container)::const_iterator;
    typename decltype(container)::reverse_iterator;
    typename decltype(container)::const_reverse_iterator;
    typename decltype(container)::size_type;
};

Now for the member types, we can create a generic structure as we did for custom containers:

template <template <typename ...> typename Container, typename T>
requires IteratorsFriendlyContainerType<Container, T>
struct use_collection_iterator {
    typedef typename Container<T>::pointer pointer;
    typedef typename Container<T>::const_pointer const_pointer;
    typedef typename Container<T>::reference reference;
    typedef typename Container<T>::const_reference const_reference;
    typedef typename Container<T>::iterator iterator;
    typedef typename Container<T>::const_iterator const_iterator;
    typedef typename Container<T>::reverse_iterator reverse_iterator;
    typedef typename Container<T>::const_reverse_iterator const_reverse_iterator;
    typedef typename Container<T>::size_type size_type;
};

Pay attention that we just got rid from our custom made iterators for cases that we decided to use std containers, or any container which already supports iterators.

template <template <typename ...> typename Container, HasMul ItemT>
using my_collection_iterator = use_collection_iterator<Container, my_item<ItemT>>;

template <template <typename ...> typename Container, HasMul ItemT>
class my_item_collection : public my_collection_iterator<Container, ItemT> {
public:

    // A convenient access to inherited type members
    using base_types = my_collection_iterator<Container, ItemT>;

    /* Custom collection operations */

    void add_item(const ItemT &a, const ItemT &b) {
        items.emplace_back(a, b);
    }

    typename base_types::iterator get_item(size_t idx) {
        auto res = items.begin();
        return std::advance(res, idx);
    }

    /* Required Iterators Access Methods */

    typename base_types::iterator begin() { return items.begin(); }
    typename base_types::iterator end() { return items.end(); }
    [[nodiscard]] typename base_types::const_iterator cbegin() const 
                  { return items.cbegin(); }
    [[nodiscard]] typename base_types::const_iterator cend() const 
                  { return items.cend(); }
    typename base_types::reverse_iterator rbegin() { return items.rbegin(); }
    typename base_types::reverse_iterator rend() { return items.rend(); }
    [[nodiscard]] typename base_types::const_reverse_iterator crbegin() const 
                  { return items.crbegin(); }
    [[nodiscard]] typename base_types::const_reverse_iterator crend() const 
                  { return items.crend(); }

    [[nodiscard]] bool empty() const { return items.empty(); }
    [[nodiscard]] typename base_types::size_type size() const { return items.size(); }

private:
    Container<my_item<ItemT>> items;
};

Another change that you can see here is that we also simplified our required iterators access methods implementations. We no longer need to cast pointers to our own custom iterator implementation. And the following code will compile just fine:

int main() {
    my_item_collection<std::list, int> list_collection;
    my_item_collection<std::vector, int> vector_collection;
    list_collection.add_item(1, 2);
    list_collection.add_item(3, 4);
    list_collection.add_item(5, 6);

    vector_collection.add_item(7, 8);
    vector_collection.add_item(9, 10);
    vector_collection.add_item(11, 12);

    for (auto &elem : list_collection) {
        std::cout << elem.item() << std::endl;
    }

    for (auto &elem : vector_collection) {
        std::cout << elem.item() << std::endl;
    }
    return EXIT_SUCCESS;
}

Conclusion

This is the last part of the iterators series. In this three-parts series, we covered the importance of iterators, how to use them in order to maintain our iterations in the code without needing to touch legacy loops whenever we change our container, and today, we covered also cases when we need to create our own containers or collections and we saw how we can still work with legacy iterators code with our custom collections.

Feel free to share in the comments if you have a more generic way of doing it.

• GitHub Repository with the examples in this article

Posts in this Series

• Maintain Your Iterations – The Iterators Secret – Part 1
• Maintain Your Iterations – Insecure Iterations – Part 2
• > Maintain Your Iterations – Iterators Customization – Part 3