for_each recursif dans methode d'une classe

Version imprimable

21/02/2016, 22h45
BPC__

for_each recursif dans methode d'une classe
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:

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:

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 !

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:

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

22/02/2016, 07h28
BPC__

D'accord merci je vais regarder ça !
22/02/2016, 11h38
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:

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:

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