展平迭代器

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 {

    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

这是这里的建筑用砖，尽管实际上我们可以用其余的来做：

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 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 loop

for (auto value : view) cout << value;

该库仅是标头，没有任何依赖关系。需要C ++ 11。