6
\$\begingroup\$

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";

}
\$\endgroup\$
  • \$\begingroup\$ nested_range would be a great name for the iterator pair. Is there a reason you didn’t write range first? People could use range for loop then. I guess you had different usage in mind. \$\endgroup\$ – Incomputable Feb 1 '18 at 20:51
  • 3
    \$\begingroup\$ This operation is known as flattening ranges, IYAM \$\endgroup\$ – sehe Feb 2 '18 at 0:50
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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";
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I care a lot about naming. \$\endgroup\$ – Martin York Feb 6 '18 at 0:17
  • \$\begingroup\$ Its a forward iterator (you can use it do multi passes over the container). BUT it definitely does not have all the requirements for an iterator I was waiting for that to be called out. \$\endgroup\$ – Martin York Feb 6 '18 at 0:20
  • \$\begingroup\$ There is no requirement that end iterators from different containers need to be not equivalent. Equality and inequality comparison is defined over all iterators for the same underlying sequence and the value initialized-iterators. \$\endgroup\$ – Martin York Feb 6 '18 at 0:29
  • \$\begingroup\$ ForwardIterator iterators must be default constructable. Since these have no value associated and are comparable with iterators from a sequence this means they are end iterators. \$\endgroup\$ – Martin York Feb 6 '18 at 0:31
  • \$\begingroup\$ @MartinYork You might be right, I'm not sure... but this bit says: A value-initialized ForwardIterator behaves like the past-the-end iterator of **some unspecified empty container** which implies you can't compare it with an iterator from an actual container. I read the sentence you've quoted as meaning that value-initialized iterators have equality with other value-initialized iterators, not necessarily with iterators that are associated with an actual container. See also: stackoverflow.com/questions/1190112/…. \$\endgroup\$ – user673679 Feb 6 '18 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.