Iterator of Container of Container

Question

Based on this question I though I would pull together an iterator that iterated over a container of containers.

template<typename C>
class IteratorForContainerOfContainer
{
    public:
        using Container             = C;
        using ContainerContainer    = typename Container::value_type;
        using Contained             = typename ContainerContainer::value_type;

        using Level1Iter            = typename Container::iterator;
        using Level2Iter            = typename ContainerContainer::iterator;

        using iterator_category     = std::forward_iterator_tag;
        using value_type            = Contained;
        using difference_type       = std::size_t;
        using pointer               = value_type*;
        using reference             = value_type&;


        IteratorForContainerOfContainer(C& c)
            : outerLoop(std::begin(c))
            , outerEnd(std::end(c))
            , innerLoop(std::begin(*outerLoop))
            , innerEnd(std::end(*outerLoop))
        {
            nextValidPos();
        }
        IteratorForContainerOfContainer()
            : outerLoop()
            , outerEnd()
            , innerLoop()
            , innerEnd()
        {}


        IteratorForContainerOfContainer& operator++()
        {
            ++innerLoop;
            nextValidPos();
            return *this;
        }
        value_type& operator*()
        {
            return *innerLoop;
        }
        bool operator!=(IteratorForContainerOfContainer const& rhs) const
        {
            return outerLoop != rhs.outerLoop || innerLoop != rhs.innerLoop;
        }

        private:
            void nextValidPos()
            {
                while ((innerLoop == innerEnd) && (outerLoop != outerEnd)) {
                    ++outerLoop;
                    if (outerLoop != outerEnd) {
                        innerLoop = std::begin(*outerLoop);
                        innerEnd  = std::end(*outerLoop);
                    }
                }
                if (outerLoop == outerEnd) {
                    outerLoop   = Level1Iter();
                    outerEnd    = Level1Iter();
                    innerLoop   = Level2Iter();
                    innerEnd    = Level2Iter();
                }
            }
            Level1Iter          outerLoop;
            Level1Iter          outerEnd;
            Level2Iter          innerLoop;
            Level2Iter          innerEnd;
};

So an example of simple usage would be:

int main()
{
    using CC = std::vector<std::vector<int>>;
    using It = IteratorForContainerOfContainer<CC>;

    CC   data = {{1,2,3},{4,5,6},{7,8,9}};

     for(It loop(data);loop != It(); ++loop) {
        std::cout << *loop << " ";
    }
    std::cout << "\n";

}

Answer 1

If you try to get an IteratorForContainerOfContainer for an empty container, your constructor will run into Undefined Behavior when it tries to get the inner iterators because the outer container is empty, outerLoop will be the end iterator, and you can't dereference the end iterator.

You're using a default constructed object to double as an end iterator. Consider adding in a static method to return one, end(C &c), with appropriate changes to nextValidPos.

If you need to work with a const object, you won't be able to get one of these flattened iterators for it.

You don't define operator++(int), so using it++ won't compile.

Answer 2

Naming (a.k.a. "you probably don't care but..."):

• ContainerContainer Container. Aren't these backwards? (ContainerContainer is surely a container of containers...)
• Level1Iter, ContainerContainer, OuterEnd. That's 3 different prefixes for the same thing... maybe just use Outer and Inner everywhere.
• Use Value not Contained. The inner container is contained too, after all.

Other:

• using iterator_category = std::forward_iterator_tag; oh reaaaally? http://en.cppreference.com/w/cpp/concept/ForwardIterator (Not sure this is technically even an input iterator, since it's only got one increment operator).
• std::begin(foo) and std::end(foo) -> using std::begin; begin(foo);
• I think you're also going to run into problems with equality:
  • The value-initialized (default constructed) iterator isn't supposed to compare equal to an end iterator (it's a "singular value").
  • The equality operator shouldn't return true for two end iterators with different underlying containers (see the "multipass guarantee" section of the linked cppreference page).

---

EDIT:

You're quite right about being able to compare end iterators from different containers, and compare those end iterators with value-initialized iterators.

The relevant parts of the standard from n4659:

27.2.1 iterator.requirements.general p7

Iterators can also have singular values that are not associated with any sequence. [...] Results of most expressions are undefined for singular values; the only exceptions are destroying an iterator that holds a singular value, the assignment of a non-singular value to an iterator that holds a singular value, and, for iterators that satisfy the DefaultConstructible requirements, using a value-initialized iterator as the source of a copy or move operation.

Doesn't explicitly say you can't add equality between value-initialized and non value-initialized iterators.

27.2.5 forward.iterators p2

The domain of == for forward iterators is that of iterators over the same underlying sequence. However, value-initialized iterators may be compared and shall compare equal to other value-initialized iterators of the same type. [ Note: Value-initialized iterators behave as if they refer past the end of the same empty sequence. — end note ]

There's no "and" here but again, it doesn't say you can't add a comparison between value-initialized and end iterators. It also doesn't say you can't add == to compare iterators from different sequences.

So for a forward iterator it's fine.

But if you ever want to make this bidirectional, you need --a == --b then a == b, which won't be true with this implementation.

---

It seems easier to store a pointer to the outer container, and two iterators, combined with @1201ProgramAlarm's suggestion of the static end method:

#include <cassert>
#include <iterator>

template<typename C>
class IteratorForContainerOfContainer
{
public:
    using OuterContainer = C;
    using InnerContainer = typename OuterContainer::value_type;
    using Value = typename InnerContainer::value_type;

    using OuterIter = typename OuterContainer::iterator;
    using InnerIter = typename InnerContainer::iterator;

    using iterator_category = std::forward_iterator_tag;
    using value_type = Value;
    using difference_type = std::size_t;
    using pointer = value_type*;
    using reference = value_type&;

    explicit IteratorForContainerOfContainer(OuterContainer& c)
        : container(std::addressof(c))
    {
        begin();
    }

    IteratorForContainerOfContainer()
        : container(nullptr)
        , outer()
        , inner()
    {}

    IteratorForContainerOfContainer& operator++()
    {
        advance();

        return *this;
    }
    value_type& operator*()
    {
        using std::end;

        assert(container);
        assert(outer != end(*container));
        assert(inner != end(*outer));
        assert(inner != InnerIter());

        return *inner;
    }
    bool operator!=(IteratorForContainerOfContainer const& rhs) const
    {
        return container != rhs.container || outer != rhs.outer || inner != rhs.inner;
    }

    static IteratorForContainerOfContainer end(OuterContainer& c)
    {
        using std::end;

        auto result = IteratorForContainerOfContainer();
        result.container = std::addressof(c);
        result.outer = end(c);

        return result;
    }

private:

    void advanceUntilValid()
    {
        using std::begin;
        using std::end;

        assert(container);
        assert(outer != end(*container)); // advancing past the end is bad!

        while (inner == end(*outer))
        {
            std::advance(outer, 1);

            if (outer == end(*container))
            {
                inner = InnerIter();
                return;
            }

            inner = begin(*outer);
        }
    }

    void begin()
    {
        using std::begin;
        using std::end;

        assert(container);

        outer = begin(*container);

        if (outer == end(*container))
            return; // inner will never be valid (should be ok... I think... (singular values compare equal))

        inner = begin(*outer);

        advanceUntilValid();
    }

    void advance()
    {
        using std::begin;
        using std::end;

        assert(container);
        assert(outer != end(*container)); // advancing past the end is bad!
        assert(inner != end(*outer)); // should never be, because we always advance to the next valid value...

        std::advance(inner, 1);

        advanceUntilValid();
    }

    OuterContainer* container;
    OuterIter outer;
    InnerIter inner;
};

#include <iostream>
#include <vector>

int main()
{
    using CC = std::vector<std::vector<int>>;
    using It = IteratorForContainerOfContainer<CC>;

    CC data = { { 1, 2, 3 }, { }, { 4, 5, 6 }, { 7, 8, 9 } };

    for (It loop(data); loop != It::end(data); ++loop) {
        std::cout << *loop << " ";
    }

    std::cout << "\n";
}