Aplanador iterador

¿Existe alguna implementación de iterador existente (quizás en boost) que implemente algún tipo de iterador de acoplamiento?

Por ejemplo:

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

No conozco ninguna implementación en una gran biblioteca, 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 hay que saltearlos. 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, flattening_iterator necesita saber dónde está el final del rango externo para saber 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 usan para hacer que la construcción de flattening_iterator sea ​​más fácil.

 #include  // A forward iterator that "flattens" a container of containers. For example, // a vector> containing { { 1, 2, 3 }, { 4, 5, 6 } } is iterated as // a single range, { 1, 2, 3, 4, 5, 6 }. template  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  flattening_iterator flatten(Iterator it) { return flattening_iterator(it, it); } template  flattening_iterator flatten(Iterator first, Iterator last) { return flattening_iterator(first, last); } 

El siguiente es un apéndice de prueba mínimo:

 #include  #include  #include  #include  int main() { // Generate some test data: it looks like this: // { { 0, 1, 2, 3 }, { 4, 5, 6, 7 }, { 8, 9, 10, 11 } } std::vector> 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(std::cout, ", ")); } 

Como dije al principio, no lo he probado a fondo. Avíseme si encuentra algún error y estaré encantado de corregirlo.

Decidí “mejorar” un poco el concepto del iterador de aplanar, aunque como James señaló que estás atascado usando Ranges (excepto el contenedor más interno), simplemente utilicé los rangos de principio a fin y así obtuve un rango aplanado , con un profundidad arbitraria.

Primero utilicé un ladrillo de construcción:

 template  struct iterator { using type = typename C::iterator; }; template  struct iterator { using type = typename C::const_iterator; }; 

Y luego definió un concepto (muy mínimo) de ForwardRange :

 template  class ForwardRange { using Iter = typename iterator::type; public: using pointer = typename std::iterator_traits::pointer; using reference = typename std::iterator_traits::reference; using value_type = typename std::iterator_traits::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 

Este es nuestro ladrillo de construcción aquí, aunque de hecho podríamos conformarnos con el rest:

 template  class FlattenedForwardRange { using Iter = typename iterator::type; using Inner = FlattenedForwardRange::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(_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 _outer; Inner _inner; }; // class FlattenedForwardRange template  class FlattenedForwardRange { using Iter = typename iterator::type; public: using pointer = typename std::iterator_traits::pointer; using reference = typename std::iterator_traits::reference; using value_type = typename std::iterator_traits::value_type; FlattenedForwardRange(): _range() {} explicit FlattenedForwardRange(C& c): _range(c) {} // Observers explicit operator bool() const { return static_cast(_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 _range; }; // class FlattenedForwardRange 

Y aparentemente, funciona

puedes hacer uno usando la fachada del iterador en boost.

Escribí un producto de iterador que puede usar como plantilla quizás: http://code.google.com/p/asadchev/source/browse/trunk/work/cxx/iterator/product.hpp

Llegué un poco tarde aquí, pero acabo de publicar una biblioteca (multidim) para tratar ese problema. El uso es bastante simple: para usar su ejemplo,

 #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; 

La biblioteca es solo de encabezado y no tiene dependencias. Requiere C ++ 11 sin embargo.