Itérateur horizontal

Y at-il une implémentation d’iterator existante (peut-être sous boost) qui implémente une sorte d’iterator d’aplatissement?

Par exemple:

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 

Je ne connais aucune implémentation dans une bibliothèque majeure, mais cela semblait être un problème intéressant, alors j’ai écrit une implémentation de base. Je l’ai seulement testé avec le cas de test que je présente ici, je ne recommande donc pas de l’utiliser sans test supplémentaire.

Le problème est un peu plus délicat qu’il n’y parait car certains conteneurs “internes” peuvent être vides et vous devez les ignorer. Cela signifie que l’avancement de flattening_iterator d’une position peut réellement faire avancer l’iterator dans le conteneur “externe” de plusieurs positions. De ce fait, flattening_iterator doit savoir où se trouve la fin de la plage externe pour savoir quand il doit s’arrêter.

Cette implémentation est un iterator avant. Un iterator bidirectionnel devrait également suivre le début de la plage externe. Les modèles de fonction d’ flatten permettent de simplifier la construction de 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); } 

Ce qui suit est un talon de test minimal:

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

Comme je l’ai dit au début, je n’ai pas testé cela de manière approfondie. Faites-moi savoir si vous trouvez des bugs et je serai heureux de les corriger.

J’ai décidé d’améliorer un peu le concept de l’iterator d’aplatissement, bien que, comme l’a noté James, vous utilisez des plages (sauf pour le conteneur le plus interne), alors je me suis contenté de profondeur arbitraire.

J’ai d’abord utilisé une brique de construction:

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

Et ensuite défini un concept (très minimal) 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 

Ceci est notre brique de construction ici, même si en fait nous pourrions nous contenter du 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 

Et apparemment, ça marche

vous pouvez en faire une en utilisant la façade de l’iterator en boost.

J’ai écrit un produit iterator que vous pouvez utiliser comme modèle, par exemple: http://code.google.com/p/asadchev/source/browse/trunk/work/cxx/iterator/product.hpp

J’arrive un peu tard, mais je viens de publier une bibliothèque (multidim) pour traiter ce problème. L’utilisation est assez simple: pour utiliser votre exemple,

 #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 bibliothèque est uniquement en-tête et ne comporte aucune dépendance. Nécessite C ++ 11 cependant.