How to flatten iterators of nested containers?

I'll quickly outline a solution:

1. Write a is_container trait that detects begin() and end() members, or possibly some more complex rules;
2. Write a all_flattening_iterator<T> template that is just a flattening_iterator<all_flattening_iterator<typename T::value_type>>;
3. Write a specialization of all_flattening_iterator<T> for when T is not a container (use a default template bool parameter) that is just a regular iterator.

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... :-)

I arrive a little late here, but I have just published a library (multidim) to deal with such problem. Check out my answer to the related question for details.

My solution takes inspiration from Alex Wilson's idea of using "telescopically nested" iterators. It adds some more functionality though (e.g. support for read-only container such as sets, backwards iteration, random access) and offers a more pleasant interface, as it auto-detects the type of the "leaf" elements.