展平迭代器

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

- George

---

它会打印出数字1到12，但由于在示例中使用了一个“无序”的集合，因此不一定按顺序。 - James McNellis

@James：是的，在这个例子中，我不在乎它们以什么顺序被打印出来。 - George

Answer 1

我不知道主要库中是否有任何实现，但这似乎是一个有趣的问题，所以我编写了一个基本的实现。我只在这里呈现的测试用例中进行了测试，因此不建议在没有进一步测试的情况下使用它。

这个问题比看起来更加棘手，因为一些“内部”容器可能为空，你必须跳过它们。这意味着向前移动 flattening_iterator 一个位置可能会使迭代器在“外部”容器中向前移动多个位置。因此，flattening_iterator 需要知道外部范围的结尾位置，以便它知道何时需要停止。

这个实现是一个正向迭代器。一个双向迭代器也需要跟踪外部范围的开头。 flatten函数模板用于使构建 flattening_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);
}

以下是一个最小的测试桩：

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

就像我一开始说的那样，我没有彻底测试过这个。 如果您发现任何错误，请告诉我，我很乐意纠正它们。

- James McNellis

---

非常感谢您抽出时间写下这篇文章。我还没有做太多的测试，但是我遇到的唯一问题就是gcc抱怨“typedef typename OuterIterator”应该是“typedef OuterIterator”。 - George

@George：啊，谢谢。那是一个复制粘贴错误，加上Visual C++松散的标准兼容性:-P。 - James McNellis

@George：提醒一下，operator==重载中有一个bug，只能在与结束迭代器比较时才能正常工作；我已经在编辑中进行了更正。 - James McNellis

谢谢你让我知道。另外，你能否看一下我上面的双向实现，并告诉我是否有更好的实现方式。谢谢。 - George

@James：希望有一天你能够发布你的迭代器库 :) - Matthieu M.

Answer 2

我决定在扁平化迭代器的概念上进行一些“改进”，尽管正如James所指出的那样，您只能使用范围（除了最内层容器），因此我全程使用范围，并因此获得了一个具有任意深度的“扁平化范围”。

首先，我使用了一个构建块：

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

显然，它运行正常

- Matthieu M.

---

小小的挑剔：我觉得将迭代器命名为“Range”有点令人困惑。 - Nobody moving away from SE

@Nobody：这可能是因为它实际上是一个范围而不是一个迭代器（尽管可以将其用作迭代器）。 它在单个对象中嵌入了要迭代的范围的“端点”，使其自给自足。 实际上很遗憾，但许多有趣的范围无法轻松地表示为迭代器对（或者至少没有冗余）。 - Matthieu M.

你是从实现者的角度来争论，看到了存储的对象。而我是从迭代器接口的角度来争论。我期望一个范围可以插入到 for(auto elem: range) 中。不管怎样，这只是命名问题。无论如何，工作做得很好。 - Nobody moving away from SE

@Nobody：实际上，我从两个角度进行了争论，如果您查看ideone示例，它并未像迭代器一样使用...因此，如果按原样使用，它将不适用于新的for循环。 - Matthieu M.

Answer 3

我有点晚到这里，但是我刚刚发布了一个多维库来解决这个问题。使用方法非常简单：以你的例子为例，

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

- Alberto M

Answer 4

你可以使用boost中的迭代器外观创建一个。

我编写了一个迭代器模板，也许你可以用作参考： http://code.google.com/p/asadchev/source/browse/trunk/work/cxx/iterator/product.hpp

- Anycorn

---

链接已经失效了...嗯，它会跳转到某个地方，但我没有找到迭代器。 - 463035818_is_not_a_number

Answer 5

除了Matthieu的答案之外，您还可以自动计算可迭代/容器的维度数量。但首先，我们必须设定一个规则，即何时某物是可迭代/容器：

template<class T, class R = void>
struct AliasWrapper {
    using Type = R;
};

template<class T, class Enable = void>
struct HasValueType : std::false_type {};

template<class T>
struct HasValueType<T, typename AliasWrapper<typename T::value_type>::Type> : std::true_type {};

template<class T, class Enable = void>
struct HasConstIterator : std::false_type {};

template<class T>
struct HasConstIterator<T, typename AliasWrapper<typename T::const_iterator>::Type> : std::true_type {};

template<class T, class Enable = void>
struct HasIterator : std::false_type {};

template<class T>
struct HasIterator<T, typename AliasWrapper<typename T::iterator>::Type> : std::true_type {};

template<class T>
struct IsIterable {
    static constexpr bool value = HasValueType<T>::value && HasConstIterator<T>::value && HasIterator<T>::value;
};

我们可以按如下方式计算维度：

template<class T, bool IsCont>
struct CountDimsHelper;

template<class T>
struct CountDimsHelper<T, true> {
    using Inner = typename std::decay_t<T>::value_type;
    static constexpr int value = 1 + CountDimsHelper<Inner, IsIterable<Inner>::value>::value;
};

template<class T>
struct CountDimsHelper<T, false> {
    static constexpr int value = 0;
};

template<class T>
struct CountDims {
    using Decayed = std::decay_t<T>;
    static constexpr int value = CountDimsHelper<Decayed, IsIterable<Decayed>::value>::value;
};

我们可以创建一个视图包装器，其中包含一个begin（）和end（）函数。

template<class Iterable, int Dims>
class Flatten {
public:
    using iterator = FlattenIterator<Iterable, Dims>;

private:
    iterator _begin{};
    iterator _end{};

public:
    Flatten() = default;

    template<class I>
    explicit Flatten(I&& iterable) :
        _begin(iterable),
        _end(iterable)
    {}

    iterator begin() const {
        return _begin;
    }

    iterator end() const {
        return _end;
    }
};

为了让对象Flatten的创建更加容易，我们定义了一个辅助函数：

template<class Iterable>
Flatten<std::decay_t<Iterable>, CountDims<Iterable>::value - 1> flatten(Iterable&& iterable) {
    return Flatten<std::decay_t<Iterable>, CountDims<Iterable>::value - 1>(iterable);
}

使用方法：

std::vector<std::vector<int>> vecs = {{1,2,3}, {}, {4,5,6}};

for (int i : flatten(vecs)) {
    // do something with i
}

- Marc Dirven