No sé de cualquier aplicación en una biblioteca importante, pero parecía un problema interesante así que escribí una implementación básica. Solo lo he probado con el caso de prueba que presento aquí, por lo que no recomiendo usarlo sin más pruebas.
El problema es un poco más complicado de lo que parece porque algunos de los contenedores "internos" pueden estar vacíos y debe omitirlos. Esto significa que avanzar el flattening_iterator en una posición puede hacer avanzar el iterador en el contenedor "exterior" en más de una posición. Debido a esto, el flattening_iterator necesita saber dónde está el final del rango externo para que sepa cuándo debe detenerse.
Esta implementación es un iterador directo. Un iterador bidireccional también necesitaría hacer un seguimiento del comienzo del rango externo. Las plantillas de función flatten se utilizan para hacer que la construcción de flattening_iterator sea un poco más fácil.
#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);
}
El siguiente es un talón de prueba mínima:
#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, ", "));
}
Como dije al principio, no he probado esto a fondo. Avíseme si encuentra algún error y estaré encantado de corregirlo.
Imprimirá los números del 1 al 12, pero no necesariamente en orden, ya que está utilizando un conjunto _unordered_ en el ejemplo, ¿verdad? –
@James: Sí, en el ejemplo no me importa en qué orden están impresos. – George