Hello,

Je m'amuse à faire une petite bibliothèque C++ d'itérateurs, dans le genre de ce qui existe en Java (Streams) mais plutot dans le style de ceux de Rust. J'ai un problème pour écrire une classe, les templates - que je ne comprends pas bien en dehors des cas très simples - me font mal à la tête.

En bref, un générateur est un objet qui a une fonction membre next(), qui retourne des éléments d'une séquence. Plus exactement, il retourne des optionnels contenant les valeurs des éléments, et quand il n'y en a plus, il retourne un Optionnel vide.

Un exemple : iterateur qui retourne les valeurs d'un intervalle

class IterateurIntervalle : public Iterator<int>
{
private:
    int current, end;

public:
    IterateurIntervalle(int start, int end)
        : current{start}, end{end}
    {    }

    std::optional<int> next()
    {
        if (current >= end) {
            return {};
        } else {
            return {current++};
        }
};

Exemple d'utilisation

void test_intervalle(void)
{
    IterateurIntervalle i{3, 5};
    i.foreach ([](auto n)
               { std::cout << n << std::endl; });
}

Foreach prend comme paramètre une action à appliquer. Elle est définie dans la classe mère

template <typename T>
class Iterator
{
public:
    virtual std::optional<T> next() = 0;

public:

    void foreach (std::function<void(const T &)> f)
    {
        while (std::optional<T> x = next()) {
            f(x.value());
        };
    }
};

Jusque là tout va bien.

Dans la classe Iterator, on ajoute des fonctions qui créent de nouveaux itérateurs. Comme ça on peut les chaines. Exemple, si on veut filtrer par un prédicat pour n'avoir que des nombres pairs, on fait un truc comme ça

   IterateurIntervalle j{1, 10}
       .filter([](auto n)
                      { return (n & 1) == 0; })
       .foreach([](int x)
               { std::cout << x << std::endl; });

 La magie : dans Iterator il y a une fonction filter qui produit un itérateur qui sait filter

template <typename T>
class FilteringIterator;


template <typename T>
class Iterator
{
public:
      // ...
    FilteringIterator<T> filter(std::function<bool(const T &)> predicate)
    {
        return {*this, predicate};
    }
};

et qui est défini comme suit : 

template <typename T>
class FilteringIterator : public Iterator<T>
{
    Iterator<T> &source;
    std::function<bool(const T &)> predicate;

public:
    FilteringIterator(Iterator<T> &source,
                      std::function<bool(const T)> predicate)
        : source{source},
          predicate{predicate}
    {
    }

    std::optional<T> next() override
    {
        while (auto n = source.next())
            if (predicate(n.value()))
                return n;
        return {};
    }
};

Et je vous passe les détails pour d'autres trucs du même genre.

Là où je coince, c'est sur un truc plus compliqué, flat_map

Exemple d'utilisation pour rexpliquer

    IterateurIntervalle{1, 4}
        .flat_map([](int n) {
            return IterateurIntervalle{1,n};
        })       
        .foreach( [](int n){
            std::cout << n << " ";      
        });
       

Le  premier itérateur produit les nombres de 1 à 4, et le flat_map prend ces nombres 1 par 1 pour générer et exploiter de nouveaux itérateurs. La séquence attendue, ça devrait être 1 1 2 1 2 3 1 2 3 4

La je coince grave sur la définition à coups de templates qui marcherait avec des lambdas comme paramètres (comme dans l'exemple)

En gros, ça devrait ressembler à ça

template <class T>
class Iterateur {
  ...

  template <class R>
  FlatMapIterator<R, T, ???> flat_map (std::function<std::optional<R>(T) mapping) {
   ...
}
   return { *this, mapping };
};


template  <R,....>
class FlatMapIterator : public Iterator<R> 
{

   std::optional<R> next() {
      ....
   }
};

mais je patine lamentablement sur les déductions de type, avec les std::invoke_result et meta programmation pour essyaer de choper le type des arguments des lambdas.

Quelqu'un peut aider ?

-
Edité par michelbillaud 20 octobre 2021 à 17:24:42

Si la fonction passée à flat_map() retourne un itérateur, son paramètre ne peut pas être de type std::function&ltstd::optional&l;R>(T), mais std::function<Iterator(T)>. Sauf que pour connaître le type de l'itérateur, il faut le déduire du type réel de la fonction.

Je ferrais quelque chose comme:

template <class F>
auto flat_map(F&& f) -> FlatMapIterator<T, F>
{
  return {std::forward<F>(f)};
}


template  <class T, class F>
class FlatMapIterator : public Iterator<R>
{
   using IteratorResult = decltype(F(std::declval<T&>()));
   using R = IteratorResult::ElementType;  // ElementType est à mettre dans Iterator<T>

public:
   std::optional<R> next() {
      ....
   }
};

-
Edité par jo_link_noir 21 octobre 2021 à 23:13:48

Merci je vais regarder ça. Ca me fout un mal de tronche ce truc...:-)

En fait le paramètre de flat_map, pour un iterateur it1 qui fournit des éléments de type T c'est une fonction f qui prend un T et produit un itérateur it2 d'un autre type R.

Les types en résumé

• Iterator<T> it1
• std::function< Iterator<R>(T)>  f
• Iterator<R> it2 = it1.flat_map(f)

-
Edité par michelbillaud 22 octobre 2021 à 13:40:40