Aplatissement de l'itérateur

Question

Existe-t-il une implémentation d'itérateur existante (peut-être en boost) qui implémente une sorte d'itérateur d'aplatissement ?

Par exemple :

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

Je ne connais pas d'implémentation dans une bibliothèque majeure, mais cela semblait être un problème intéressant, alors j'ai écrit une implémentation de base. Je ne l'ai testé qu'avec le cas de test que je présente ici, donc je ne recommande pas de l'utiliser sans tests supplémentaires.

Le problème est un peu plus délicat qu'il n'y paraît, car certains des conteneurs "intérieurs" peuvent être vides et vous devez les ignorer. Cela signifie qu'en avançant le flattening_iterator d'une position peut en fait faire avancer l'itérateur dans le conteneur "externe" de plus d'une position. Pour cette raison, la fonction flattening_iterator doit savoir où se trouve la fin de la plage extérieure afin de savoir quand il doit s'arrêter.

Cette implémentation est un itérateur avant. Un itérateur bidirectionnel devrait également garder la trace du début de la plage extérieure. Le site flatten Les modèles de fonctions sont utilisés pour rendre la construction flattening_iterator s un peu plus facile.

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

Ce qui suit est un stub de test minimal :

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

Comme je l'ai dit au début, je ne l'ai pas testé à fond. Faites-moi savoir si vous trouvez des bogues et je serai heureux de les corriger.

Answer 2

J'ai décidé d'"améliorer" un peu le concept d'itérateur d'aplatissement, bien que, comme l'a noté James, vous êtes coincé en utilisant des plages (sauf pour le conteneur le plus interne), donc j'ai juste utilisé des plages de part en part et ainsi obtenu une gamme réduite avec une profondeur arbitraire.

J'ai d'abord utilisé une brique de construction :

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

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

Et ensuite, nous avons défini un (très minimal) ForwardRange concept :

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

C'est notre brique de construction ici, bien qu'en fait nous pourrions faire avec juste le reste :

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

Et apparemment, ça marche

Answer 3

J'arrive un peu tard ici, mais je viens de publier une bibliothèque (multidim) pour faire face à ce problème. L'utilisation est très simple : il suffit d'utiliser votre exemple,

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

La bibliothèque n'est qu'un en-tête et n'a pas de dépendances. Nécessite cependant C++11.

Answer 4

Vous pouvez en créer un en utilisant la façade iterator de boost.

J'ai écrit un produit itérateur que vous pouvez peut-être utiliser comme modèle : http://code.google.com/p/asadchev/source/browse/trunk/work/cxx/iterator/product.hpp

Answer 5

En complément de la réponse de Matthieu, vous pouvez compter automatiquement le nombre de dimensions de l'itérable/conteneur. Mais d'abord nous devons établir une règle pour savoir quand quelque chose est un itérable/conteneur :

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

Nous pouvons compter les dimensions comme suit :

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

Nous pouvons alors créer un wrapper de vue, qui contient une begin() et end() fonction.

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

Pour que la création de l'objet Flatten un peu plus facile, nous définissons une fonction d'aide :

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

Utilisation :

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

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