/ 猿问

# 展平迭代器

2019-09-21 15:23:53

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 回答

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

}

reference operator*()  const { return *inner_it_;  }

pointer   operator->() const { return &*inner_it_; }

flattening_iterator& operator++()

{

++inner_it_;

if (inner_it_ == outer_it_->end())

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:

{

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

}

template <typename C>

struct iterator { using type = typename C::iterator; };

template <typename C>

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

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

}

// 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:

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

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

• 3 回答
• 0 关注
• 181 浏览

0/150