展平迭代器

是否有任何现有的迭代器实现（也许在boost）实现某种平坦化迭代器？

例如：

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

Answer 1

我不知道在一个主要的图书馆有什么实现，但是看起来像一个有趣的问题，所以我写了一个基本的实现。 我只用我在这里提供的testing用例来testing它，所以我不build议在没有进一步testing的情况下使用它。

问题比看起来有点棘手，因为一些“内部”容器可能是空的，你必须跳过它们。 这意味着将flattening_iterator推进一个位置可能实际上将迭代器推进到“外”容器的多个位置。 因此， flattening_iterator需要知道外部范围的结束位置，以便知道何时需要停止。

这个实现是一个前向迭代器。 双向迭代器也需要跟踪外部范围的开始。 flatten函数模板用于使构buildflattening_iterator更容易一些。

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

以下是最小的testing存根：

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

就像我刚开始说的，我没有彻底地testing过。 让我知道如果你发现任何错误，我会很乐意纠正它们。

Answer 2

我决定在flattening iterator的概念上做一些改进，虽然正如James所指出的那样，你使用了Ranges（除了最内层的容器），所以我只是使用range和through来获得一个平坦的范围 ，任意深度。

首先，我使用了build筑砖：

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

然后定义一个（非常小的） ForwardRange概念：

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

这是我们在这里的build筑砖，但实际上我们可以做的只是其余部分：

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

显然， 它的工作

Answer 3

你可以在boost中使用迭代器外观。

我写了可以用作模板的迭代器产品： http : //code.google.com/p/asadchev/source/browse/trunk/work/cxx/iterator/product.hpp

Answer 4

我迟到了，但是我刚刚出版了一个图书馆（multidim）来处理这个问题。 用法很简单：使用你的例子，

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

这个库只是头文件而且没有依赖关系。 不过需要C ++ 11。