How to smooth nested container iterators?

Question

This (so far) a) (further) follows James's answer to this question: Iterator compression

How do I change flattenig_iterator so that it works recursively? Let's say I have more levels of nested containers, and I do not want to be limited to a given nesting depth. That is, flattening_iterator should work with

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

as well as

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

In my actual code, I have an array of objects that may or may not contain such an array.

change

After playing with different iteration methods through various types of nested containers, I learned something that might be interesting to others:

Access to container elements with nested loops is 5-6 times faster than with an iterator solution.

Pros:

• Items
• can be complex objects, for example. (e.g. in my case) that contain containers.
• faster execution

Minuses:

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

Other pros and cons?

Answer 1

Okay, so this is not a complete solution, but I did not have enough time. Thus, currently it implements not a full iterator, but a shorthand class, similar to an iterator, which defines something like this interface and requires C ++ 11. I tested it on g ++ 4.7:

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

Where NestedContainerType is the type of the enclosed container (unexpectedly), and Terminator is the type of the innermost thing you want to get out of anti-aliasing.

The code below works, but this, of course, is not verified. Wrapping completely (if you are only happy with moving forward) should not 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; public: 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 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(); } } 

Thus, for each type of container, the following is displayed:

 1 2 3 4 

Note that it does not work with set yet, because some foo are needed to deal with the fact that set iterators return const references. Exercise for the reader ... :-)

Answer 2

I will quickly outline the solution:

• Write an is_container character that detects the begin() and end() members, or possibly more complex rules;
• Write a template all_flattening_iterator<T> , which is just flattening_iterator<all_flattening_iterator<typename T::value_type>> ;
• Write the specialization all_flattening_iterator<T> if T not a container (use the default template parameter bool ), which is just a regular iterator.

Answer 3

I come here a little late, but I just published a library (multidim) to solve this problem. For more details, see my answer to the corresponding question .

My solution draws inspiration from the idea of using "telescopically nested" iterators. It adds some more functionality (for example, support for a read-only container, such as set s, reverse iteration, random access) and offers a more pleasant interface, because it automatically determines the type of sheet elements.