Iteratore di appiattimento

Esiste un’implementazione iteratore esistente (forse in boost) che implementa una sorta di iteratore di appiattimento?

Per esempio:

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 

Non conosco alcuna implementazione in una libreria importante, ma sembrava un problema interessante, quindi ho scritto un’implementazione di base. L’ho provato solo con il test case che ho presentato qui, quindi non consiglio di usarlo senza ulteriori test.

Il problema è un po ‘più complicato di quanto sembri perché alcuni dei contenitori “interni” potrebbero essere vuoti e devi saltarli sopra. Ciò significa che far avanzare l’ flattening_iterator di una posizione può effettivamente far avanzare l’iteratore nel contenitore “esterno” di più di una posizione. Per questo flattening_iterator , l’unità di flattening_iterator bisogno di sapere dove si trova la fine dell’intervallo esterno in modo che sappia quando deve fermarsi.

Questa implementazione è un iteratore diretto. Un iteratore bidirezionale dovrebbe anche tenere traccia dell’inizio dell’intervallo esterno. I modelli di funzione flatten vengono utilizzati per semplificare la costruzione di flattening_iterator .

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

Quello che segue è uno stub di prova minimo:

 #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, ", ")); } 

Come ho detto all’inizio, non l’ho testato a fondo. Fammi sapere se trovi qualche bug e sarò felice di correggerli.

Ho deciso di “migliorare” un po ‘il concetto di iteratore di appiattimento, anche se come notato da James sei bloccato usando i Ranges (tranne che per il contenitore interno più interno), quindi ho appena usato gli intervalli e ho ottenuto una gamma appiattita , con un profondità arbitraria.

Per prima cosa ho usato un mattone da costruzione:

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

E poi definito un concetto ForwardRange (molto minimale):

 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 

Questo è il nostro mattone da costruzione qui, anche se in realtà potremmo arrangiarci con il resto:

 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 

E a quanto pare, funziona

puoi farne uno usando la facciata dell’iteratore in boost.

Ho scritto un prodotto iteratore che puoi utilizzare come modello: http://code.google.com/p/asadchev/source/browse/trunk/work/cxx/iterator/product.hpp

Arrivo un po ‘in ritardo qui, ma ho appena pubblicato una libreria (multidim) per affrontare questo problema. L’utilizzo è abbastanza semplice: per usare il tuo esempio,

 #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 libreria ha solo intestazione e non ha dipendenze. Tuttavia richiede il C ++ 11.