Iterador de nivelamento

Existe alguma implementação do iterador existente (talvez em reforço) que implementa algum tipo de iterador de nivelamento?

Por exemplo:

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 

Não conheço nenhuma implementação em uma biblioteca principal, mas parecia um problema interessante, então escrevi uma implementação básica. Eu só testei com o caso de teste que apresento aqui, então não recomendo usá-lo sem mais testes.

O problema é um pouco mais complicado do que parece, porque alguns dos contêineres “internos” podem estar vazios e você precisa pular sobre eles. Isso significa que o avanço do flattening_iterator em uma posição pode, na verdade, fazer avançar o iterador para o contêiner “externo” em mais de uma posição. Por causa disso, o flattening_iterator precisa saber onde o fim do intervalo externo é para que ele saiba quando precisa parar.

Essa implementação é um iterador avançado. Um iterador bidirecional também precisaria acompanhar o início do intervalo externo. Os modelos de function flatten são usados ​​para facilitar a construção do 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); } 

A seguir, um esboço de teste 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 eu disse no começo, eu não testei isso completamente. Deixe-me saber se você encontrar algum bug e eu ficarei feliz em corrigi-los.

Decidi “melhorar” um pouco o conceito do iterador de achatamento, embora, como notado por James, você esteja usando Ranges (exceto o contêiner mais interno), então eu usei intervalos e assim obtive um intervalo achatado , com um profundidade arbitrária.

Primeiro eu usei um tijolo de construção:

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

E então definimos um conceito (muito 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 é o nosso tijolo de construção aqui, embora na verdade nós pudéssemos nos contentar com o 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 aparentemente, funciona

você pode fazer um usando a fachada do iterador no impulso.

Eu escrevi o produto iterador que você pode usar como modelo talvez: http://code.google.com/p/asadchev/source/browse/trunk/work/cxx/iterator/product.hpp

Chego um pouco atrasado aqui, mas acabei de publicar uma biblioteca (multidim) para lidar com esse problema. O uso é bastante simples: para usar o seu exemplo,

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

A biblioteca é somente de header e não possui dependencies. Requer C ++ 11 embora.