Сглаживающий итератор

Question

Существует ли какая-либо существующая реализация итератора (возможно, в надстройке), которая реализует какой-то итератор сглаживания?

Например:

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

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

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

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 3

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

Answer 4

Вы можете сделать один, используя итератор фасад в Boost.

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

Answer 5

В дополнение к ответу Матье вы можете автоматически подсчитать количество измерений итерируемого объекта / контейнера. Но сначала мы должны установить правило, когда что-то является итерируемым / контейнером:

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
}