How to flatten iterators of nested containers?

Question

This is (yet) a(nother) follow up to James' answer to this question: Flattening iterator

How do I alter the flattenig_iterator such that it works recursively? Say I have more levels of nested containers and I don't want to be limited to a given nesting depth. I.e. flattening_iterator should work with

std::vector< std::vector < std::vector < int > > >

as well as with

std::vector< std::vector < std::vector < std::vector < int > > > >

In my actual code I have an array of objects which might or not contain such an array themselves.

edit:

After playing around with different ways of iterating through different kind of nested containers I learned something that might be interesting to others as well:

Accessing the container elements with nested loops executed 5 to 6 times faster than with the iterator solution.

Pros:

• elements can be complex objects, e.g. (like in my case) classes that contain containers.
• faster execution

Cons:

• Each container structure requires a new implementation of the loop
• standard library algorithms are not available

Other pros and cons?

Answer 1

Ok, so this isn't a full solution - but I ran out of time. So this currently implements not a full iterator but a cut down iterator-like class which defines something like this interface, and requires C++11. I've tested it on g++4.7:

template<typename NestedContainerType, typename Terminator>
class flatten_iterator
{
    bool complete();
    void advance();
    Terminator& current();
};

Where NestedContainerType is the nested container type (surprisingly), and Terminator is the type of the innermost thing that you're wanting to get out of the flatten.

The code below works, but this is certainly not extensively tested. Wrapping it up fully (assuming you're happy with forward advance only) shouldn't be too much work, in particular if you use boost::iterator_facade.

#include <list>
#include <deque>
#include <vector>

#include <iostream>

template<typename ContainerType, typename Terminator>
class flatten_iterator
{
public:
    typedef flatten_iterator<typename ContainerType::value_type, Terminator> inner_it_type;
    typedef typename inner_it_type::value_type value_type;

    flatten_iterator() {}
    
    flatten_iterator( ContainerType& container ) : m_it( container.begin() ), m_end( container.end() )
    {
        skipEmpties();
    }
    
    bool complete()
    {
        return m_it == m_end;
    }
    
    value_type& current()
    {
        return m_inner_it.current();
    }
    
    void advance()
    {
        if ( !m_inner_it.complete() )
        {
            m_inner_it.advance();
        }
        if ( m_inner_it.complete() )
        {
            ++m_it;
            skipEmpties();
        }
    }
    
private:
    void skipEmpties()
    {
        while ( !complete() )
        {
            m_inner_it = inner_it_type(*m_it);
            if ( !m_inner_it.complete() ) break;
            ++m_it;
        }
    }

private:
    inner_it_type                    m_inner_it;
    typename ContainerType::iterator m_it, m_end;
};


template<template<typename, typename ...> class ContainerType, typename Terminator, typename ... Args>
class flatten_iterator<ContainerType<Terminator, Args...>, Terminator>
{
public:
    typedef typename ContainerType<Terminator, Args...>::value_type value_type;
    
public:
    flatten_iterator() {}
    
    flatten_iterator( ContainerType<Terminator, Args...>& container ) :
        m_it( container.begin() ), m_end( container.end() )
    {
    }
    
    bool complete()
    {
        return m_it == m_end;
    }
    
    value_type& current() { return *m_it; }
    void advance() { ++m_it; }
    
private:
    typename ContainerType<Terminator, Args...>::iterator m_it, m_end;
};

And with the following test cases, it does what you would expect:

int main( int argc, char* argv[] )
{   
    typedef std::vector<int> n1_t;
    typedef std::vector<std::deque<short> > n2_t;
    typedef std::list<std::vector<std::vector<std::vector<double> > > > n4_t;
    typedef std::vector<std::deque<std::vector<std::deque<std::vector<std::list<float> > > > > > n6_t;
    
    n1_t n1 = { 1, 2, 3, 4 };
    n2_t n2 = { {}, { 1, 2 }, {3}, {}, {4}, {}, {} };
    n4_t n4 = { { { {1.0}, {},  {}, {2.0}, {} }, { {}, {} }, { {3.0} } }, { { { 4.0 } } } };
    n6_t n6 = { { { { { {1.0f}, {},  {}, {2.0f}, {} }, { {}, {} }, { {3.0f} } }, { { { 4.0f } } } } } };
    
    flatten_iterator<n1_t, int> i1( n1 );
    while ( !i1.complete() )
    {
        std::cout << i1.current() << std::endl;
        i1.advance();
    }
    
    flatten_iterator<n2_t, short> i2( n2 );
    while ( !i2.complete() )
    {
        std::cout << i2.current() << std::endl;
        i2.advance();
    }
    
    flatten_iterator<n4_t, double> i4( n4 );
    while ( !i4.complete() )
    {
        std::cout << i4.current() << std::endl;
        i4.advance();
    }
    
    flatten_iterator<n6_t, float> i6( n6 );
    while ( !i6.complete() )
    {
        std::cout << i6.current() << std::endl;
        i6.advance();
    }
}

So prints the following for each of the container types:

1
2
3
4

Note that it doesn't yet work with sets because there's some foo required to deal with the fact that set iterators return const references. Exercise for the reader... :-)