how to build an iterator over two containers in a chained fashion

Question

I want to provide an iterator that iterates over contents of 2 containers.

For example, I would like to hide the fact that the nodes of a polyline are stored in two containers (for implementation purposes):

struct PolyLine {
private:
    vector<Point*> m_head_nodes;
    vector<Point*> m_tail_nodes;

public:
    Iterator begin();
    Iterator end();
};

Polyline poly; 
cout << "contents of poly:" << endl;
for(Point *p : poly) 
   cout << p << endl;

The iterator should iterate the m_head_nodes first, then the m_tail_nodes.

Q1: Could you demonstrate how to set up the Iterator object?

• How do you implement the operator++ at the point where you cross from the first container to the second?

Q2: what if, say the 2nd container was, say, a std::list ?

• What construct do you use to represent the current 'position' iterator?
• How do you represent the end() ?

---

I have tried an implementation like the following,

struct Iterator
{
    PolyLine &m_parent;
    vector<Point*>::iterator m_it;

    Iterator(PolyLine &parent_container)
        : m_parent(parent_container) {
    }

    Iterator& operator++() {
        if (m_it == m_parent.m_head_nodes.end())
            m_it = m_parent.m_tail_nodes.begin();
        else
            ++m_it;
        return *this;
    }

    Point * operator* () {
         return *m_it;
    }
};

bool operator== (Iterator &one, Iterator &other) {
    return one.m_it == other.m_it;
}

Iterator Polyline::begin() {
    Iterator o(this);
    o.m_it = m_head_nodes.begin();
    return o;
}

Iterator Polyline::end() {
    Iterator o(this);
    o.m_it = m_tail_nodes.end();
    return o;
}

but I am not keen on keeping a pointer to the PolyLine class.

Plus, I don't know what to keep as an m_it in case the 2nd container is a, say, std::list.

Answer 1

EDIT: Thank you Jarod42 for skilfully fixing the bug in my previous code, as indeed the operator++ logic was flawed. I also changed the storage of the iterators to std::array to avoid unnecessary heap allocation.

---

This solution requires C++17, it uses a variant iterator type to accommodate for any kind of iterator, and it allows you to chain any number different collections.

#include <variant>
#include <array>
#include <vector>
#include <list>
#include <deque>
#include <iostream>

template<typename ContainerFirstT, typename ...ContainerRestT>
struct Chain
{
    // Holds an iterator of any given container
    typedef typename std::variant<typename ContainerFirstT::iterator,
                                  typename ContainerRestT::iterator ...> IterT;
    // Array of variant container iterators
    typedef typename std::array<IterT, 1 + sizeof...(ContainerRestT)> IterArrayT;
    // Iterator of array of variant iterators
    typedef typename IterArrayT::const_iterator IterArrayIterT;
    // Iterated type
    typedef typename ContainerFirstT::value_type ValueT;

    // Begin and end iterator of each container
    IterArrayT begins;
    IterArrayT ends;

    struct ChainIter
    {
        // Begin and end of container being iterated
        IterArrayIterT beginIt;
        IterArrayIterT endIt;
        IterArrayIterT endItSentinel;
        // Iterator to current element of current container
        IterT current;

        ChainIter(IterArrayIterT beginIt, IterArrayIterT endIt, IterArrayIterT endItSentinel, IterT current)
        : beginIt{beginIt}
        , endIt{endIt}
        , endItSentinel{endItSentinel}
        , current{current}
        {
        }

        bool operator==(ChainIter& it) const
        {
            return (beginIt == it.beginIt &&
                    endIt == it.endIt &&
                    current == it.current);
        }
        bool operator!=(ChainIter& it) const
        {
            return !(*this == it);
        }

        ChainIter& operator++()
        {
            // Go to next element
            std::visit([](auto& it) { ++it; }, current);
            // While there are elements to iterate in the current container
            if (current == *endIt)
            {
                // When the container is finished move to the next one
                ++beginIt;
                ++endIt;
                if (endIt != endItSentinel)
                {
                    current = *beginIt;
                }
            }
            return *this;
        }

        ValueT& operator*()
        {
            // Get value of current iterator
            ValueT* value;
            std::visit([&value](auto it) { value = &(*it); }, current);
            return *value;
        }
    };

    Chain(ContainerFirstT& containerFirst, ContainerRestT& ...containerRest)
    : begins{containerFirst.begin(), containerRest.begin()...}
    , ends{containerFirst.end(), containerRest.end()...}
    {
    }

    ChainIter begin()
    {
        return ChainIter(begins.begin(), ends.begin(), ends.end(), begins.front());
    }

    ChainIter end()
    {
        return ChainIter(begins.end(), ends.end(), ends.end(), ends.back());
    }
};

// Convenience factory
template<typename ...ContainersT>
Chain<ContainersT ...> make_chain(ContainersT& ...containers)
{
    return Chain<ContainersT ...>(containers...);
}

// Example
int main()
{
    std::vector<int> v = {1, 2, 3};
    std::list<int> l = {4, 5};
    std::deque<int> d = {6, 7, 8, 9};
    auto chain = make_chain(v, l, d);
    for (auto elem : chain)
    {
        std::cout << elem << std::endl;
    }
    return 0;
}

Output:

1
2
3
4
5
6
7
8
9

Answer 2

• An alternative to implement custom iterator (which is really verbose) is to provide a method to iterate over all elements:

struct PolyLine {
private:
    vector<Point*> m_head_nodes;
    vector<Point*> m_tail_nodes;

public:
    template <typename F>
    void VisitAllPoints(F&& f)
    {
        for (Point* p : m_head_nodes) {
            f(p);
        }
        for (Point* p : m_tail_nodes) {
            f(p);
        }
    }
};

And call it:

PolyLine pol = /*..*/;

pol.VisitAllPoints([](Point* p){ /*..*/});

• Else, range-v3 library provides concatview (which is lazy):

struct PolyLine {
private:
    vector<Point*> m_head_nodes;
    vector<Point*> m_tail_nodes;

public:
    auto allPoints() const { return ranges::view::concat(m_head_nodes, m_tail_nodes); }
    auto allPoints() { return ranges::views::concat(m_head_nodes, m_tail_nodes); }
};

That you can use:

PolyLine pol = /*..*/;

for (Point* p : pol.allPoints()) {
    /*..*/
}

Answer 3

Does something like this work for you (obviously it's a bashed out in 10 min kinda solution so don't expect the committee to insta-ship it in c++20 or something lol - it's just to give some ideas):

#include <iostream>
#include <array>
#include <vector>
#include <deque>
#include <algorithm>


template<typename Pointee0, typename Pointee1, typename It0, typename It1> struct ChainedIter;

template<typename Pointee, typename It0, typename It1>
class ChainedIter<Pointee, Pointee, It0, It1> {
    It0 it0, begin0, end0;
    It1 it1, begin1, end1;
public:
    ChainedIter(It0 begin0, It0 end0, It1 begin1, It1 end1):
        it0{begin0}, begin0{begin0}, end0{end0},
        it1{begin1}, begin1{begin1}, end1{end1} {}
    bool operator==(ChainedIter& rhs) const {
        return it0 == rhs.it0 && it1 == rhs.it1;
    }
    bool operator!=(ChainedIter& rhs) const {
        return !(*this == rhs);
    }
    ChainedIter* operator++() {
        if(it0 != end0) ++it0;
        else ++it1;
        return this;
    }
    Pointee& operator*() {
        if(it0 != end0) return *it0;
        else return *it1; // UB if it1 == end1
    }
    ChainedIter end() {
        auto newChainedIter = *this;
        newChainedIter.it0 = newChainedIter.end0;
        newChainedIter.it1 = newChainedIter.end1;
        return newChainedIter;

    }
    ChainedIter begin() {
        auto newChainedIter = *this;
        newChainedIter.it0 = newChainedIter.begin0;
        newChainedIter.it1 = newChainedIter.begin1;
        return newChainedIter;

    }
};

template<typename Cont1, typename Cont0>
decltype(auto) createIter(Cont0& cont0, Cont1& cont1) {
    auto begin0 = cont0.begin();
    auto end0 = cont0.end();
    auto begin1 = cont1.begin();
    auto end1 = cont1.end();
    return ChainedIter<
           typename Cont0::value_type,
           typename Cont1::value_type,
           typename Cont0::iterator,
           typename Cont1::iterator> {begin0, end0, begin1, end1};
}

int main() {
    std::vector<size_t> v(4, 20);
    std::deque<size_t> d(3, 200);

    auto iter = createIter(v, d);
    std::for_each(iter.begin(), iter.end(), [](const auto& elt) {
        std::cout << elt << ' ';
    });
    std::cout << std::endl;
}

I tried to make it work with different container types as long as they both are templated on the same object (which made sense as a kneejerk but maybe it can be enhanced to allow convertible types etc.). As seen in main() it works with vector as well as a deque.

My compiler version is:

$ g++ --version
g++ (GCC) 9.1.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

So maybe I could use template guides of C++17 to not depend on that additional function for type deduction convenience, but this itself took more than 10 mins for me to type and then some more to sort out compile bugs; plus I'm sure it's got loads of other horrible-for-production stuff anyway :P