Сглаживание итератора

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

Я не знаю, какая-либо реализация в крупной библиотеке, но это выглядело как интересная проблема, так что я написал основную реализацию. Я только тестировал его с тестовым примером, который я здесь представляю, поэтому я не рекомендую использовать его без дальнейшего тестирования.

Проблема немного сложнее, чем кажется, потому что некоторые из «внутренних» контейнеров могут быть пустыми, и вам нужно пропустить их. Это означает, что продвижение 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, ", ")); 
} 

Как я уже сказал в начале, я не проверял это тщательно. Дайте мне знать, если вы найдете какие-либо ошибки, и я буду рад их исправить.

Answer 2

вы можете сделать один с помощью итератора фасад в наддува.

Я написал итератор продукт, который вы можете использовать в качестве шаблона, возможно: http://code.google.com/p/asadchev/source/browse/trunk/work/cxx/iterator/product.hpp

Answer 3

Я решил немного «улучшить» концепцию итератора сплющивания, хотя, как отметил Джеймс, вы застряли с использованием диапазонов (за исключением внутреннего контейнера), поэтому я просто использовал диапазоны сквозного и, следовательно, получил сплющенный диапазон, с произвольной глубиной.

Сначала я использовал строительный кирпич:

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 

И, по-видимому, it works

Answer 4

Я приезжаю немного поздно здесь, но я только что опубликовал a library (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.