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

It would print the numbers 1 through 12, but not necessarily in order since you're using an unordered set in the example, right? — James McNellis
@James: Yes, in the example I don't care what order they are printed in. — George

James McNellis James McNellis · Accepted Answer · 2010-09-02T03:08:08

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.

Flattening iterator

5 Answers