Flattening iterator
I arrive a little late here, but I have just published a library (multidim) to deal with such problem. The usage is quite simple: to use your example,
#include "multidim.hpp"
// ... create "s" as in your example ...
auto view = multidim::makeFlatView(s);
// view offers now a flattened view on s
// You can now use iterators...
for (auto it = begin(view); it != end(view); ++it) cout << *it << endl;
// or a simple range-for loop
for (auto value : view) cout << value;
The library is header-only and has no dependencies. Requires C++11 though.
you can make one using iterator facade in boost.
I wrote iterator product which you can use as a template perhaps: http://code.google.com/p/asadchev/source/browse/trunk/work/cxx/iterator/product.hpp
I decided to "improve" a bit on the flattening iterator concept, though as noted by James you are stuck using Ranges (except for the inner most container), so I just used ranges through and through and thus obtained a flattened range, with an arbitrary depth.
First I used a building brick:
template <typename C>
struct iterator { using type = typename C::iterator; };
template <typename C>
struct iterator<C const> { using type = typename C::const_iterator; };
And then defined a (very minimal) ForwardRange concept:
template <typename C>
class ForwardRange {
using Iter = typename iterator<C>::type;
public:
using pointer = typename std::iterator_traits<Iter>::pointer;
using reference = typename std::iterator_traits<Iter>::reference;
using value_type = typename std::iterator_traits<Iter>::value_type;
ForwardRange(): _begin(), _end() {}
explicit ForwardRange(C& c): _begin(begin(c)), _end(end(c)) {}
// Observers
explicit operator bool() const { return _begin != _end; }
reference operator*() const { assert(*this); return *_begin; }
pointer operator->() const { assert(*this); return &*_begin; }
// Modifiers
ForwardRange& operator++() { assert(*this); ++_begin; return *this; }
ForwardRange operator++(int) { ForwardRange tmp(*this); ++*this; return tmp; }
private:
Iter _begin;
Iter _end;
}; // class ForwardRange
This is our building brick here, though in fact we could make do with just the rest:
template <typename C, size_t N>
class FlattenedForwardRange {
using Iter = typename iterator<C>::type;
using Inner = FlattenedForwardRange<typename std::iterator_traits<Iter>::value_type, N-1>;
public:
using pointer = typename Inner::pointer;
using reference = typename Inner::reference;
using value_type = typename Inner::value_type;
FlattenedForwardRange(): _outer(), _inner() {}
explicit FlattenedForwardRange(C& outer): _outer(outer), _inner() {
if (not _outer) { return; }
_inner = Inner{*_outer};
this->advance();
}
// Observers
explicit operator bool() const { return static_cast<bool>(_outer); }
reference operator*() const { assert(*this); return *_inner; }
pointer operator->() const { assert(*this); return _inner.operator->(); }
// Modifiers
FlattenedForwardRange& operator++() { ++_inner; this->advance(); return *this; }
FlattenedForwardRange operator++(int) { FlattenedForwardRange tmp(*this); ++*this; return tmp; }
private:
void advance() {
if (_inner) { return; }
for (++_outer; _outer; ++_outer) {
_inner = Inner{*_outer};
if (_inner) { return; }
}
_inner = Inner{};
}
ForwardRange<C> _outer;
Inner _inner;
}; // class FlattenedForwardRange
template <typename C>
class FlattenedForwardRange<C, 0> {
using Iter = typename iterator<C>::type;
public:
using pointer = typename std::iterator_traits<Iter>::pointer;
using reference = typename std::iterator_traits<Iter>::reference;
using value_type = typename std::iterator_traits<Iter>::value_type;
FlattenedForwardRange(): _range() {}
explicit FlattenedForwardRange(C& c): _range(c) {}
// Observers
explicit operator bool() const { return static_cast<bool>(_range); }
reference operator*() const { return *_range; }
pointer operator->() const { return _range.operator->(); }
// Modifiers
FlattenedForwardRange& operator++() { ++_range; return *this; }
FlattenedForwardRange operator++(int) { FlattenedForwardRange tmp(*this); ++*this; return tmp; }
private:
ForwardRange<C> _range;
}; // class FlattenedForwardRange
And apparently, it works
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.