Flattening iterator

Question

Is there any existing iterator implementation (perhaps in boost) which implement some sort of flattening iterator?

For example:

unordered_set<vector<int> > s;  s.insert(vector<int>()); s.insert({1,2,3,4,5}); s.insert({6,7,8}); s.insert({9,10,11,12});  flattening_iterator<unordered_set<vector<int> >::iterator> it( ... ), end( ... ); for(; it != end; ++it) {     cout << *it << endl; } //would print the numbers 1 through 12 

Answer 1

I don't know of any implementation in a major library, but it looked like an interesting problem so I wrote a basic implementation. I've only tested it with the test case I present here, so I don't recommend using it without further testing.

The problem is a bit trickier than it looks because some of the "inner" containers may be empty and you have to skip over them. This means that advancing the flattening_iterator by one position may actually advance the iterator into the "outer" container by more than one position. Because of this, the flattening_iterator needs to know where the end of the outer range is so that it knows when it needs to stop.

This implementation is a forward iterator. A bidirectional iterator would also need to keep track of the beginning of the outer range. The flatten function templates are used to make constructing flattening_iterators a bit easier.

#include <iterator>  // A forward iterator that "flattens" a container of containers.  For example, // a vector<vector<int>> containing { { 1, 2, 3 }, { 4, 5, 6 } } is iterated as // a single range, { 1, 2, 3, 4, 5, 6 }. template <typename OuterIterator> class flattening_iterator { public:      typedef OuterIterator                                outer_iterator;     typedef typename OuterIterator::value_type::iterator inner_iterator;      typedef std::forward_iterator_tag                iterator_category;     typedef typename inner_iterator::value_type      value_type;     typedef typename inner_iterator::difference_type difference_type;     typedef typename inner_iterator::pointer         pointer;     typedef typename inner_iterator::reference       reference;      flattening_iterator() { }     flattening_iterator(outer_iterator it) : outer_it_(it), outer_end_(it) { }     flattening_iterator(outer_iterator it, outer_iterator end)          : outer_it_(it),            outer_end_(end)     {          if (outer_it_ == outer_end_) { return; }          inner_it_ = outer_it_->begin();         advance_past_empty_inner_containers();     }      reference operator*()  const { return *inner_it_;  }     pointer   operator->() const { return &*inner_it_; }      flattening_iterator& operator++()     {         ++inner_it_;         if (inner_it_ == outer_it_->end())             advance_past_empty_inner_containers();         return *this;     }      flattening_iterator operator++(int)     {         flattening_iterator it(*this);         ++*this;         return it;     }      friend bool operator==(const flattening_iterator& a,                             const flattening_iterator& b)     {         if (a.outer_it_ != b.outer_it_)             return false;          if (a.outer_it_ != a.outer_end_ &&              b.outer_it_ != b.outer_end_ &&             a.inner_it_ != b.inner_it_)             return false;          return true;     }      friend bool operator!=(const flattening_iterator& a,                            const flattening_iterator& b)     {         return !(a == b);     }  private:      void advance_past_empty_inner_containers()     {         while (outer_it_ != outer_end_ && inner_it_ == outer_it_->end())         {             ++outer_it_;             if (outer_it_ != outer_end_)                  inner_it_ = outer_it_->begin();         }     }      outer_iterator outer_it_;     outer_iterator outer_end_;     inner_iterator inner_it_; };  template <typename Iterator> flattening_iterator<Iterator> flatten(Iterator it) {     return flattening_iterator<Iterator>(it, it); }  template <typename Iterator> flattening_iterator<Iterator> flatten(Iterator first, Iterator last) {     return flattening_iterator<Iterator>(first, last); } 

The following is a minimal test stub:

#include <algorithm> #include <iostream> #include <set> #include <vector>  int main() {     // Generate some test data:  it looks like this:     // { { 0, 1, 2, 3 }, { 4, 5, 6, 7 }, { 8, 9, 10, 11 } }     std::vector<std::vector<int>> v(3);     int i(0);     for (auto it(v.begin()); it != v.end(); ++it)     {         it->push_back(i++); it->push_back(i++);         it->push_back(i++); it->push_back(i++);     }      // Flatten the data and print all the elements:     for (auto it(flatten(v.begin(), v.end())); it != v.end(); ++it)     {         std::cout << *it << ", ";     }     std::cout << "\n";      // Or, since the standard library algorithms are awesome:     std::copy(flatten(v.begin(), v.end()), flatten(v.end()),                std::ostream_iterator<int>(std::cout, ", ")); } 

Like I said at the beginning, I haven't tested this thoroughly. Let me know if you find any bugs and I'll be happy to correct them.