为了账号安全,请及时绑定邮箱和手机立即绑定

展平迭代器

/ 猿问

展平迭代器

C++
泛舟湖上清波郎朗 2019-09-21 15:23:53

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


查看完整描述

3 回答

?
慕标5265247

我不知道主要库中的任何实现,但是它看起来像是一个有趣的问题,因此我编写了一个基本实现。我仅使用此处介绍的测试用例对其进行了测试,因此,建议您在没有进行进一步测试的情况下使用它。


这个问题比看起来有些棘手,因为某些“内部”容器可能是空的,您必须跳过它们。这意味着将其向前推进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, ", "));

}

就像我刚开始所说的那样,我还没有对它进行彻底的测试。如果您发现任何错误,请告诉我,我们将很乐意予以纠正。


查看完整回答
反对 回复 2019-09-21
?
波斯汪

我决定在扁平化迭代器概念上“改善”一点,尽管正如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

显然,它有效


查看完整回答
反对 回复 2019-09-21
?
烙印99

我到这里有点晚了,但是我刚刚发布了一个图书馆(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。


查看完整回答
反对 回复 2019-09-21

添加回答

回复

举报

0/150
提交
取消
意见反馈 邀请有奖 帮助中心 APP下载
官方微信