Discussion :

[BPC__]

bonjour/bonsoir,

Je cherche à savoir si il est possible d'utiliser for_each pour parcourir un vecteur de liste chainée recursivement. Je m'explique, j'ai une classe MaClasse et une liste chainée tel que :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
struct MaStruct{
  int      value;
  std::vecteur<struct MaStruct *> *next;
};
 
class MaClasse{
 private:
 struct MaStruct    *elem;
 
  void   show_val(const struct MaStruct &);
};

Et je cherche à faire un truc du genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
void MaClasse::show_val(const struct MaStruct & elem)
{
        for_each(elem.next->begin(), elem.next->end(), this->show_val);
        std::cout << elem.value << std::endl;
}

Mais impossible de le faire fonctionner, quelqu'un aurais une Piste/idée ? Sachant que je ne souhaite pas utiliser for ou un autre type de boucle mais vraiment for_each.

Merci d'avance !

[jo_link_noir]

Il te faut un itérateur récursive. J'en ai un super compliqué sur mon github (un jour je ferrais un truc plus jolie).

Une version simplifiée ressemble à:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iterator>
 
template<class It1, class It2>
class recursive_iterator
{
  It1 it1;
  It1 last1;
  It2 it2;
  It2 last2;
 
  template<class C>
  static C & empty_cont() {
    static C cont;
    return cont;
  }
 
public:
  template<class C>
  explicit recursive_iterator(C & c)
  : it1(begin(c))
  , last1(end(c))
  , it2(c.empty() ? begin(empty_cont<typename C::value_type>()) : begin(*it1))
  , last2(c.empty() ? end(empty_cont<typename C::value_type>()) : end(*it1))
  {}
 
  // pour end
  template<class C>
  recursive_iterator(C & c, int)
  : it1(end(c))
  {}
 
  recursive_iterator & operator++() {
    if (++it2 == last2) {
      while (++it1 != last1 && it1->empty()) {
      }
      if (it1 != last1) {
        it2 = begin(*it1);
        last2 = end(*it1);
      }
    }
    return *this;
  }
 
  typename std::iterator_traits<It2>::value_type operator*() {
    return *it2;
  }
 
  typename std::iterator_traits<It2>::pointer operator->() {
    return it2.operator->();
  }
 
  bool operator==(recursive_iterator const & other) const {
     return it1 == other.it1;
  }
 
  bool operator!=(recursive_iterator const & other) const {
     return !(*this == other);
  }
};
 
template<class C, class... Int>
recursive_iterator<typename C::iterator, typename C::value_type::iterator>
make_recursive_iterator(C & c, Int... for_end_it) {
  return recursive_iterator<typename C::iterator, typename C::value_type::iterator>{c, for_end_it...};
}
 
 
namespace std {
  template<class It1, class It2>
  struct iterator_traits<recursive_iterator<It1, It2>>
  : iterator_traits<It2>
  {
    using iterator_category = std::forward_iterator_tag;
  };
}
 
 
#include <iostream>
#include <algorithm>
#include <list>
#include <vector>
 
int main() {
  std::vector<std::list<int>> cont{{1,2,3},{},{4,5,6},{},{},{0}};
 
  std::for_each(
    make_recursive_iterator(cont),
    make_recursive_iterator(cont, 1),
    [](int i){ std::cout << i << '\n'; }
  );
}

[BPC__]

D'accord merci je vais regarder ça !

[koala01]

Salut,

Mais avant toute chose, tu ferais bien de virer tes pointeurs... : std::vector de lui-même de tout ce qui a trait à la gestion dynamique de la mémoire (comme toutes les collections proposées par la bibliothèque standard, d'ailleurs) , et, pour autant que ta structure est copiable, il n'y a aucune raison de la maintenir sous la forme d'un pointeur à l'intérieur de la collection.

Au pire, si ta classe n'est pas copiable, il faudra alors prendre le pli d'utiliser des pointeurs intelligents, comme std::unique_ptr!

Mais, au final, ta structure MaStruct pourrait parfaitement ressembler à quelque chose comme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
struct MaStruct{
int value;
std::vector<MaStruct> nexts;
}

(note au passage que, sous cette forme, ce n'est pas une liste chainée que tu crées ici, mais bien d'avantage un arbre N-aire, que tu utilises les pointeurs ou non !)

Enfin, depuis que C++11 est arrivé, on dispose de deux fonctionnalités géniales, les range-based loops et l'inférence de type. Et, comme il est possible d'appeler carrément ta fonction de manière récursive, ta fonction print_value peut être aussi simple que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
void show_val(MaStruct const & s){
    std::cout<<s.value<<"\n";
    for(auto const & it : s.nexts){
       show_val(it);
   }
}

Tu n'as donc même plus à t'emm..der avec les itérateurs, depuis que cette fonctionnalité est apparue