展平迭代器

Question

是否存在任何实现某种扁平化迭代器的现有迭代器实现（也许在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

我决定在扁平化迭代器概念上“改善”一点，尽管正如James所指出的，您被困在Ranges（最里面的容器除外）上，所以我只使用了range，直到获得了Flattened Range，任意深度。首先，我使用了建筑用砖：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 {&nbsp; &nbsp; using Iter = typename iterator<C>::type;public:&nbsp; &nbsp; using pointer = typename std::iterator_traits<Iter>::pointer;&nbsp; &nbsp; using reference = typename std::iterator_traits<Iter>::reference;&nbsp; &nbsp; using value_type = typename std::iterator_traits<Iter>::value_type;&nbsp; &nbsp; ForwardRange(): _begin(), _end() {}&nbsp; &nbsp; explicit ForwardRange(C& c): _begin(begin(c)), _end(end(c)) {}&nbsp; &nbsp; // Observers&nbsp; &nbsp; explicit operator bool() const { return _begin != _end; }&nbsp; &nbsp; reference operator*() const { assert(*this); return *_begin; }&nbsp; &nbsp; pointer operator->() const { assert(*this); return &*_begin; }&nbsp; &nbsp; // Modifiers&nbsp; &nbsp; ForwardRange& operator++() { assert(*this); ++_begin; return *this; }&nbsp; &nbsp; ForwardRange operator++(int) { ForwardRange tmp(*this); ++*this; return tmp; }private:&nbsp; &nbsp; Iter _begin;&nbsp; &nbsp; Iter _end;}; // class ForwardRange这是这里的建筑用砖，尽管实际上我们可以用其余的来做：template <typename C, size_t N>class FlattenedForwardRange {&nbsp; &nbsp; using Iter = typename iterator<C>::type;&nbsp; &nbsp; using Inner = FlattenedForwardRange<typename std::iterator_traits<Iter>::value_type, N-1>;public:&nbsp; &nbsp; using pointer = typename Inner::pointer;&nbsp; &nbsp; using reference = typename Inner::reference;&nbsp; &nbsp; using value_type = typename Inner::value_type;&nbsp; &nbsp; FlattenedForwardRange(): _outer(), _inner() {}&nbsp; &nbsp; explicit FlattenedForwardRange(C& outer): _outer(outer), _inner() {&nbsp; &nbsp; &nbsp; &nbsp; if (not _outer) { return; }&nbsp; &nbsp; &nbsp; &nbsp; _inner = Inner{*_outer};&nbsp; &nbsp; &nbsp; &nbsp; this->advance();&nbsp; &nbsp; }&nbsp; &nbsp; // Observers&nbsp; &nbsp; explicit operator bool() const { return static_cast<bool>(_outer); }&nbsp; &nbsp; reference operator*() const { assert(*this); return *_inner; }&nbsp; &nbsp; pointer operator->() const { assert(*this); return _inner.operator->(); }&nbsp; &nbsp; // Modifiers&nbsp; &nbsp; FlattenedForwardRange& operator++() { ++_inner; this->advance(); return *this; }&nbsp; &nbsp; FlattenedForwardRange operator++(int) { FlattenedForwardRange tmp(*this); ++*this; return tmp; }private:&nbsp; &nbsp; void advance() {&nbsp; &nbsp; &nbsp; &nbsp; if (_inner) { return; }&nbsp; &nbsp; &nbsp; &nbsp; for (++_outer; _outer; ++_outer) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; _inner = Inner{*_outer};&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (_inner) { return; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; _inner = Inner{};&nbsp; &nbsp; }&nbsp; &nbsp; ForwardRange<C> _outer;&nbsp; &nbsp; Inner _inner;}; // class FlattenedForwardRangetemplate <typename C>class FlattenedForwardRange<C, 0> {&nbsp; &nbsp; using Iter = typename iterator<C>::type;public:&nbsp; &nbsp; using pointer = typename std::iterator_traits<Iter>::pointer;&nbsp; &nbsp; using reference = typename std::iterator_traits<Iter>::reference;&nbsp; &nbsp; using value_type = typename std::iterator_traits<Iter>::value_type;&nbsp; &nbsp; FlattenedForwardRange(): _range() {}&nbsp; &nbsp; explicit FlattenedForwardRange(C& c): _range(c) {}&nbsp; &nbsp; // Observers&nbsp; &nbsp; explicit operator bool() const { return static_cast<bool>(_range); }&nbsp; &nbsp; reference operator*() const { return *_range; }&nbsp; &nbsp; pointer operator->() const { return _range.operator->(); }&nbsp; &nbsp; // Modifiers&nbsp; &nbsp; FlattenedForwardRange& operator++() { ++_range; return *this; }&nbsp; &nbsp; FlattenedForwardRange operator++(int) { FlattenedForwardRange tmp(*this); ++*this; return tmp; }private:&nbsp; &nbsp; ForwardRange<C> _range;}; // class FlattenedForwardRange显然，它有效

Answer 2

我到这里有点晚了，但是我刚刚发布了一个图书馆（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 loopfor (auto value : view) cout << value;该库仅是标头，没有任何依赖关系。需要C ++ 11。