SFINAE, iterateurs de map et C++03

Version imprimable

Bonjour à tous.

J'ai une question assez délicate à gérer.
Pour d'obscures raisons d'architecture tordue, j'ai plusieurs séries de choses ainsi conçues:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 typedef ... Bidule; class Machin { private: list<Bidule> bidules; public: list<Bidule>::const_iterator bidules_begin() const; list<Bidule>::const_iterator bidules_end() const; }; class GrosMachin { private: list<Machin> machins; public: list<Machin>::const_iterator machins_begin() const; list<Machin>::const_iterator machins_end() const; };
Et bien évidemment, la majorité de mon code est de la forme:
Code:

1 2 3 4 5 6 7 8 GrosMachin g; for (... it_m = g.machins_begin(); it_m != g.machins_end(); ++it_m) { //PAS de code ici for (... it_b = it_m.bidules_begin(); it_b != it_m.end(); ++it_b) { //traiter le Bidule *it_b } //Pas de code ici non plus }
Comme il n'y a jamais de code qui n'est pas dans la boucle interne, j'essaie d'écrire une template d'iterateur masquant la double structure.
Pour l'essentiel, je l'ai, il "suffit" d'avoir un operateur++ tel que:
Code:

1 2 3 4 5 6 7 8 deep_iterator & operator++() { unlazy(); if (++inner_it == inner_end()) { ++outer_it; state = pending_begin; } return *this; }
Avec la subtilité que le state permet de ne pas stocker le outer.end() dans l'iterateur.

Logiquement, pour accéder aux bonnes fonctions begin et end, je passe par une classe de trait/police
Code:

1 2 3 4 5 6 7 8 9 10 11 template <typename T> struct IterableTraits { typedef typename T::iterator iterator; typedef typename T::const_iterator const_iterator; static const_iterator begin(T const& t) {return t.begin();} static iterator begin(T & t) {return t.begin();} static const_iterator end(T const& t) {return t.end();} static iterator end(T & t) {return t.end();} };
Comme ca, il suffit de la surcharger pour mon cas particulier, et tout marche tout seul.
J'envisage éventuellement d'avoir en template les pointeurs de fonctions vers begin et end, plutot que des statiques. à méditer...

Par contre, j'ai un gros soucis sur un autre point.
J'ai plusieurs cas de map<string, map<string, Truc> >, où l'on veut parcourir l'ensemble des Truc.
Et là, ca devient délicat, car ma template d'itérateur doit subitement devenir capable de discriminer les map (et multimap) des autres types, parce qu'il ne faut pas utiliser [c]*it[c] mais it->second.

La solution qui me semble la moins violente, c'est de passer par une template auxilliaire, qui ferait le bon choix. Et c'est là que je suis perdu.

A priori, la différence entre les deux genres d'accès, c'est qu'il existe un typename It::value_type::second_type.

Je tourne et retourne mon problème, sans parvenir à lui trouver une solution fonctionnelle.

J'ai essayé des choses comme:
Code:

1 2 3 4 5 6 7 //SFINAE :D template<typename It> typename It::value_type::second_type & iterator_value(It const& it) {return it->second;} template<typename It> typename It::reference iterator_value(It const& it) {return *it;}
Code:

1 2 3 4 5 6 7 //SFINAE deduction template<typename It> typename It::value_type::second_type & iterator_value(It const& it, typename It::value_type::second_type* =0) {return it->second;} template<typename It> typename It::reference iterator_value(It const& it) {return *it;}
Mais mon cher compilateur s'entête à considérer les fonctions comme ambigües, ce qui est assez logique.

Une partie de mon problème étant que je suis coincé avec un compilateur naphtalinien (Visual 2008), qui refuse les valeurs par défaut pour les paramètres template des templates de fonction. (et aussi, refuse le C++11)
Bien évidemment, je n'ai pas non plus le droit d'utiliser boost. (je peux à la rigueur importer un petit fragment, pour peu qu'il n'y ait pas une dizaine d'autres entêtes à importer)

Quelqu'un a-t-il une idée pour écrire cette SFINAE?

Citation:

Envoyé par leternel

Quelqu'un a-t-il une idée pour écrire cette SFINAE?

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
#include <map>
#include <vector>
#include <iostream>
 
template <bool, class T>
struct value_ref {
	typedef typename T::reference type;
};
 
template <class T>
struct value_ref<true, T> {
	typedef typename T::value_type::second_type& type;
};
 
template <bool, class ref_type, class T>
struct iter_value {
	static ref_type iterator_value(T const& it) { return it->second; }
};
 
template <class ref_type, class T>
struct iter_value<false, ref_type, T> {
	static ref_type iterator_value(T const& it) { return *it; }
};
 
template <class T>
struct Foo {
	typedef char One;
	typedef struct { char a[2]; } Two;
 
	template <class C> static One test(typename C::value_type::second_type *);
	template <class C> static Two test(...);
 
public:
	enum { Yes = sizeof(/* Foo<T>:: */test<T>(0)) == 1 };
	enum { No = !Yes };
 
	typedef typename value_ref<Yes, T>::type type;
};
 
template <class T>
struct Iter {
	typedef typename Foo<T>::type ref_type;
 
	ref_type operator()(T const& it) {
		return iter_value<Foo<T>::Yes, ref_type, T>::iterator_value(it);
	}
};
 
template <class T>
void test(T& ctn) {
	Iter<typename T::iterator> it;
	std::cout << it(ctn.begin()) << std::endl;
}
 
int main(int, char**) {
	std::vector<int> v;
	std::map<int, int> m;
 
	v.push_back(42);
	m.insert(std::make_pair(42, 42));
 
	test(v);
	test(m);
 
	return 0;
}

Mais... Ça marche pas sous VS2015 :/

Faut trouver comment l'écrire d'une façon compatible :/

edit :

Code:

enum { Yes = sizeof(/* Foo<T>:: */test<T>(0)) == 1 };

Ligne 34, non commenté, ça compile pas sous VS.

J'ai pas VS alors à tester:

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
template <class It>
    struct _is_map_iterator { // SFINAE value
        typedef char yes;
        typedef struct {char a[2]; } no;
        template <class T> static no is_m_i(...);
        template <class T> static yes is_m_i(typename T::value_type::second_type*);
        static const int value = sizeof(is_m_i<It>(0)) == sizeof(yes); // SFINAE old style
    };
 
template <class It, bool> // SFINAE type dérivée
    struct is_map_iterator : std::true_type {};
template <class It>
    struct is_map_iterator<It, false> : std::false_type {};
 
template <bool, typename T, typename U> // pour gérer le second problème, le type de retour
    struct _select {
        typedef T type;
    };
template <typename T, typename U> 
    struct _select<false, T, U> {
        typedef U type;
    };
 
template <class It> // on choisir par surcharge
    typename It::value_type::second_type& _iterator_value(It it, std::true_type) {
    return it->second;
}
template <class It>
    typename It::value_type& _iterator_value(It it, std::false_type) {
    return *it;
}
template <class It> // enveloppe au-dessus des surcharges
    typename _select<_is_map_iterator<It>::value, typename It::value_type::second_type, typename It::value_type>::type& iterator_value(It it) {
        return _iterator_value(it, is_map_iterator<It, _is_map_iterator<It>::value>());
    }

@stendhal666, presque, reste une erreur bizarre.

Code:

1
2
3
4
5
6
7
8
9
10
11
int main(int, char**) {
	std::vector<int> v;
	std::map<int, int> m;
	v.push_back(42);
	m.insert(std::make_pair(42, 42));
 
	std::cout << iterator_value(v.begin()) << std::endl; // erreur
	std::cout << iterator_value(m.begin()) << std::endl; // ok
 
	return 0;
}

Code:

1
2
3
error C2893: La spécialisation du modèle de fonction '_select<_is_map_iterator<It>::value,It::value_type::second_type,It::value_type>::type &iterator_value(It)' a échoué
 note: Avec les arguments template suivants :
 note: 'It=std::_Vector_iterator<std::_Vector_val<std::_Simple_types<int>>>'

Comme je disais, je n'ai pas VS, ça compile sur clang et il n'y a pas de constructions c++11...
Le message d'erreur n'est pas très explicite par ailleurs

J'ai eu quelques minutes pour mieux regarder. Il y avait bien une erreur dans mon code: dans select<bool, T, U> le type mal-formé est vérifié par le compilateur même s'il n'est pas retenu. Je l'ai donc modifié un peu, je pense que cette nouvelle version a ses chances avec VS 2008 (j'ai testé sur une version online récente de VS (http://webcompiler.cloudapp.net/))
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 #include <map> #include <vector> #include <string> #include <iostream> template <class It> struct _is_map_iterator { // SFINAE value typedef char yes; typedef struct {char a[2]; } no; template <class T> static no is_m_i(...); template <class T> static yes is_m_i(typename T::value_type::second_type*); static const int value = sizeof(is_m_i<It>(0)) == sizeof(yes); // SFINAE old style }; template <class It, bool> // SFINAE type dérivée struct is_map_iterator : std::true_type { typedef typename It::value_type::second_type iterator_value_type; // gère également type retour }; template <class It> struct is_map_iterator<It, false> : std::false_type { typedef typename It::value_type iterator_value_type; }; template <class It> // on choisir par surcharge typename It::value_type::second_type& _iterator_value(It it, std::true_type) { return it->second; } template <class It> typename It::value_type& _iterator_value(It it, std::false_type) { return *it; } template <class It> // enveloppe au-dessus des surcharges typename is_map_iterator<It, _is_map_iterator<It>::value>::iterator_value_type& iterator_value(It it) { return _iterator_value(it, is_map_iterator<It, _is_map_iterator<It>::value>()); } int main() { std::map<int, std::string> mm; mm[0]="bonjour"; std::vector<std::string> mv = { "au revoir" }; std::cout << iterator_value(mm.begin()) << std::endl; // bonjour std::cout << iterator_value(mv.begin()) << std::endl; // au revoir }
Malheureusement, en admettant même que le code compile correctement sur VS 08, il y a un problème de conception:
Mettons un itérateur: std::vector<std::pair<int, std::string>>::iterator, il existe un iterator::value_type::second_type, c'est donc la fonction destinée aux maps qui sera instanciée... et je ne vois pas quel discriminant pourrait être employé

map<it::key_type, it::value_type>::iterator != it && map<it::key_type, it::value_type>::const_iterator != it.

J'en profite pour ajouter du code pour les itérateurs constants.

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
92
93
94
95
96
97
98
99
100
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
 
namespace meta {
  struct true_type { static const bool value = true; };
  struct false_type { static const bool value = false; };
 
  template<class T, class U> struct is_same : false_type {};
  template<class T> struct is_same<T, T> : true_type {};
 
  template<bool, class T, class U> struct conditional { typedef T type; };
  template<class T, class U> struct conditional<false, T, U> { typedef U type; };
 
  template<class R, class T> struct cp_const { typedef T type; };
  template<class R, class T> struct cp_const<const R &, T> { typedef const T type; };
}
 
template <class It>
struct _is_map_iterator { // SFINAE value
  typedef char yes;
  typedef struct {char a[2]; } no;
  template <class T> static no is_m_i(...);
  template <class T> static 
  typename meta::conditional<
    (  meta::is_same<T, typename std::map<typename T::value_type::first_type, typename T::value_type::second_type>::iterator>::value
    || meta::is_same<T, typename std::map<typename T::value_type::first_type, typename T::value_type::second_type>::const_iterator>::value),
    yes,
    no
  >::type is_m_i(typename T::value_type::second_type*);
  static const bool value = sizeof(is_m_i<It>(0)) == sizeof(yes); // SFINAE old style
};
 
template<class It>
struct map_iterator_value {
  typedef typename meta::cp_const<typename It::reference, typename It::value_type::second_type>::type type;
};
 
template <class It, bool> // SFINAE type dérivée
struct is_map_iterator : meta::true_type {
  typedef typename map_iterator_value<It>::type iterator_value_type; // gère également type retour
};
template <class It>
struct is_map_iterator<It, false> : meta::false_type {
  typedef typename It::reference iterator_value_type;
};
 
template <class It> // on choisir par surcharge
typename map_iterator_value<It>::type & _iterator_value(It it, meta::true_type) {
  return it->second;
}
template <class It>
typename It::reference _iterator_value(It it, meta::false_type) {
  return *it;
}
template <class It> // enveloppe au-dessus des surcharges
typename is_map_iterator<It, _is_map_iterator<It>::value>::iterator_value_type & iterator_value(It it) {
  return _iterator_value(it, is_map_iterator<It, _is_map_iterator<It>::value>());
}
 
template<class T>
T const & const_(T const & x) {
  return x;
}
 
template<class T>
struct my_allocator : std::allocator<T>
{
  template<class U> struct rebind {
    typedef my_allocator<U> other;
  };
 
  my_allocator()
  {}
 
  template<class Other>
  my_allocator(Other const &)
  {}
};
 
int main() {
 
  std::map<int, std::string> mm; mm[0]="bonjour";
  std::vector<std::string> mv(1, "au revoir");
  std::vector<std::pair<int, std::string> > mp(1, std::make_pair(0, "ok"));
  std::set<std::pair<int, std::string> > ms; ms.insert(std::make_pair(0, "ok 2"));
  std::map<int, std::string, std::less<int>, my_allocator<std::pair<int, std::string> > > ma; ma[0]="my_allocator";
  std::cout << iterator_value(mm.begin()) << std::endl; // bonjour
  std::cout << iterator_value(mv.begin()) << std::endl; // au revoir
  std::cout << iterator_value(ma.begin()) << std::endl; // my_allocator
  std::cout << iterator_value(mp.begin()).second << std::endl; // ok
  std::cout << iterator_value(ms.begin()).second << std::endl; // ok 2
  std::cout << iterator_value(const_(mm).begin()) << std::endl; // bonjour
  std::cout << iterator_value(const_(mv).begin()) << std::endl; // au revoir
  std::cout << iterator_value(const_(ma).begin()) << std::endl; // my_allocator
  std::cout << iterator_value(const_(mp).begin()).second << std::endl; // ok
  std::cout << iterator_value(const_(ms).begin()).second << std::endl; // ok 2
}

(pas de VS non plus, mais compile en c++98 avec gcc)

Je ne prévois pas d'utiliser de vector de pair, ce type de solution pourrait aller.

Cela dit, j'ai trouvé une autre astuce:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 template <typename It, typename ref = typename It::reference>//It::reference struct map_iterator_value_reference { typedef typename It::value_type::second_type& reference; }; template <typename It, typename ref> struct map_iterator_value_reference<It, ref const&> { typedef typename It::value_type::second_type const& reference; }; template<typename It> typename map_iterator_value_reference<It>::reference iterator_value(It const& it, typename It::value_type::second_type* =0) {return it->second;} template<typename It> typename It::reference iterator_value(It const& it, ...) {return *it;}
Dans ce cas, la première surcharge n'existe que pour les map (et collections de paires), et est prioritaire sur la seconde.
Cela lève l'ambigüité, tout en offrant la selection qui me suffit.

Pour faire la distinction entre map et vecteur de paires, en partant de l'itérateur, c'est vraisemblablement impossible.
En partant de la collection, on pourrait se servir du mapped_type ou du key_type.

Je garde vos solutions sous le coude, mais a priori, j'utiliserai celle-ci, car elle est plus courte. Il faudra tout de même que j'observe les performances.

21/01/2016, 09h16
stendhal666

Oui, ta solution est beaucoup plus élégante. Mais il faut appeler iterator_value avec deux arguments, cela ne te gêne pas ?
21/01/2016, 09h59
ternel

Non, car le second argument est automatique, voire absent.
dans la première surcharge, il y a une valeur par défaut, et dans la seconde, il n'est pas nécessaire.
C'est pour ca qu'il faudra que je surveille les performances.

Concrètement, ma solution précédente ne compilait pas sous Visual 2008, et peut-être juste pas.

j'utilise à présent :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//porte la constance et la référence de T sur U.
template <typename T, typename U>
struct const_alike {typedef U type;};
 
template <typename T, typename U>
struct const_alike<T&, U> {typedef U& type;};
 
template <typename T, typename U>
struct const_alike<T const, U> {typedef U const type;};
 
template <typename T, typename U>
struct const_alike<T const&, U> {typedef U const& type;};
 
 
//SFINAE deduction
template<typename It>
typename const_alike<typename It::reference, typename It::value_type::second_type>::type
iterator_value(It const& it, typename It::value_type::second_type* =0) {return it->second;}
 
template<typename It>
typename It::reference
iterator_value(It const& it, ...) {return *it;}

Voila, j'ai obtenu un résultat probant.
Je le mets ici, et avec un peu de mise en forme, je le proposerai en bibliothèque valide pour C++03, C++11 et C++14.

Tout d'abord, le code d'essai sur les types classiques (seulement les déclarations, pour vérifier la compilabilité).

Code:

1
2
3
4
5
6
7
8
9
10
template <typename T>
void test_deep_iterator(T & a) {
   for (utils::deep_iterator<T> it = a.begin(), end = a.end(); it!=end; ++it) cout << *it << endl;
}
 
template void test_deep_iterator(std::list< std::list<int> > const&);
template void test_deep_iterator(std::list< std::multimap<std::string, int> > const&);
template void test_deep_iterator(std::map<int, std::vector<std::string> > const&);
template void test_deep_iterator(std::list< std::list<int> > &);
template void test_deep_iterator(std::vector< std::vector<int> const > &);

Le gros morceau, un exemple de structures imbriquées

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
namespace truc {
 
typedef double Bidule;
 
class Machin {
public:
   typedef std::list<Bidule> bidules_type;
   typedef bidules_type::const_iterator bidules_iterator;
private:
   bidules_type bidules;
 
public:
   bidules_iterator bidules_begin() const {return bidules.begin();}
   bidules_iterator bidules_end  () const {return bidules.end();}
};
 
class GrosMachin {
public:
   typedef std::vector<Machin> machins_type;
   typedef machins_type::iterator machins_iterator;
   typedef machins_type::const_iterator machins_const_iterator;
private:
   machins_type machins;
 
public:
   machins_const_iterator machins_begin() const {return machins.begin();}
   machins_const_iterator machins_end  () const {return machins.end();}
 
   machins_iterator machins_begin() {return machins.begin();}
   machins_iterator machins_end  () {return machins.end();}
};
 
inline machins_const_iterator machins_begin(Animal const& a) {return a.machins_begin();}
inline machins_const_iterator machins_end  (Animal const& a) {return a.machins_end();}
 
inline machins_iterator machins_begin(Animal & a) {return a.machins_begin();}
inline machins_iterator machins_end  (Animal & a) {return a.machins_end();}
 
inline Machin::bidules_iterator bidules_begin(Presta const& p) {return p.bidules_begin();}
inline Machin::bidules_iterator bidules_end  (Presta const& p) {return p.bidules_end();}
 
typedef utils::deep_iterator<
   GrosMachin const,
   utils::IterableTraits<
      GrosMachin const,
      machins_const_iterator,
      &machins_begin, &machins_end,
      machins_const_iterator::value_type
   >,
   utils::IterableTraits<
      Machin const,
      Machin::bidules_iterator,
      &bidules_begin, &bidules_end,
      Machin::bidules_iterator::value_type
   >
> bidules_iterator;
 
bidules_iterator bidules_begin() const {return machins_begin();}
bidules_iterator bidules_end  () const {return machins_end();}
void f(GrosMachin const& a) {
   for (GrosMachin::bidules_iterator it = a.bidules_begin(), end = a.bidules_end(); it!=end; ++it)
     cout << *it << endl;
   ;
}
 
}//truc

et enfin, la solution complète, incluant quelques uns des outils standards (begin, end, cbegin et cend).

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#ifndef UTILS_DEEP_ITERATOR_H
#define UTILS_DEEP_ITERATOR_H
 
#include <iterator>
 
namespace utils {
/*
permet d'itérer sur des types imbriqués:
   un type extérieur est itérable et permet d'accéder à un type intérieur
   ce type intérieur qui est itérable et donne accès à des valeurs
   cas d'usage initial: map<K1, map< K2, V> >
   cas d'usage secondaires vector< list< V > >
   cas subsidiaire, requis: struct { list< struct{list<V>} > } (en fait, Animal={ list<Presta={list<Resultat>}> })
   
*/
 
template< class C >
typename C::iterator begin(C & c) {return c.begin();}
 
template< class C >
typename C::const_iterator begin(C const& c) {return c.begin();}
 
template< class C >
typename C::const_iterator cbegin(C const& c) {return begin(c);}
 
template< class T, std::size_t N >
T* begin( T (&array)[N] ) {return array;}
 
 
 
template< class C >
typename C::iterator end(C & c) {return c.end();}
 
template< class C >
typename C::const_iterator end(C const& c) {return c.end();}
 
template< class C >
typename C::const_iterator cend(C const& c) {return end(c);}
 
template< class T, std::size_t N >
T* end( T (&array)[N] ) {return array+N;}
 
 
template <typename T, typename U>
struct const_alike {typedef U type;};
 
template <typename T, typename U>
struct const_alike<T&, U> {typedef U& type;};
 
template <typename T, typename U>
struct const_alike<T const, U> {typedef U const type;};
 
template <typename T, typename U>
struct const_alike<T const&, U> {typedef U const& type;};
 
 
 
template <typename T>
struct Iterator {typedef typename T::iterator type;};
 
template <typename T>
struct Iterator<T const> {typedef typename T::const_iterator type;};
 
template<typename T>
class has_mapped_type {
   typedef char yes[1];
   typedef char no [2];
   template<typename C> static yes& test(typename C::mapped_type *);
   template<typename C> static no&  test(...);
public:
   static bool const value = sizeof(test<T>(0)) == sizeof(yes);
};
 
template <typename T, bool = has_mapped_type<T>::value>
struct iterated_value_of {typedef typename T::mapped_type type;};
 
template <typename T>
struct iterated_value_of<T, false> {typedef typename T::value_type type;};
 
 
//SFINAE deduction
template<typename It>
typename const_alike<typename It::reference, typename It::value_type::second_type>::type
iterator_value(It const& it, typename It::value_type::second_type* =0) {return it->second;}
 
template<typename It>
typename It::reference
iterator_value(It const& it, ...) {return *it;}
 
template <
   typename T,
   typename It = typename Iterator<T>::type,
   It Begin(T &) = begin, It End(T &) = end,
   typename V = typename const_alike<T, typename iterated_value_of<T>::type>::type
>
struct IterableTraits {
   typedef T iterable;
 
   typedef It iterator;
   typedef V value_type;
   typedef value_type& reference;
 
   static iterator begin(iterable & t) {return Begin(t);}
   static iterator end(iterable & t) {return End(t);}
};
 
 
/*
expected uses
map<map<>> : outer begin to end. (begin and end, !=, ++, *)
map<map<>> : inner begin to end, given a outer key
   begin and end, !=, ++, *
 
GrosMachin={ list<Machin={list<Bidule>}> }:
   tous les résultats.
*/
//utiliser des types constants pour iterer de manière constante
template <
   typename Outer,
   typename Outer_I_T = IterableTraits<Outer>,
   typename Inner_I_T = IterableTraits<typename Outer_I_T::value_type>
>
class deep_iterator {
private:
   typedef typename Outer_I_T::iterator OuterIt;
   typedef typename Inner_I_T::iterator InnerIt;
 
   OuterIt outer_it;
   mutable InnerIt inner_it;
   mutable enum {ready, pending_begin, pending_end} state;
 
   InnerIt inner_begin() const {return Inner_I_T::begin(iterator_value(outer_it));}
   InnerIt inner_end  () const {return Inner_I_T::end  (iterator_value(outer_it));}
 
   void stabilize() const {
      if (state==ready) return;
      inner_it = (state==pending_begin) ? inner_begin() : inner_end();
      state = ready;
   }
 
public:
   typedef typename Inner_I_T::value_type value_type;
 
   deep_iterator(OuterIt const& it): outer_it(it), state(pending_begin) {}
 
   value_type const& operator*() const {
      stabilize();
      return iterator_value(inner_it);
   }
 
   value_type const& value() const {
      return operator*();
   }
 
   deep_iterator & operator++() {
      if (++inner_it == inner_end()) {
         ++outer_it;
         state = pending_begin;
      }
      return *this;
   }
 
   deep_iterator & operator--() {
      if (inner_it == inner_begin()) {
         --outer_it;
         state = pending_end;
      }
      return *this;
   }
 
   deep_iterator operator++(int) {
      deep_iterator tmp(*this);
      operator++();
      return tmp;
   }
 
   deep_iterator operator--(int) {
      deep_iterator tmp(*this);
      operator--();
      return tmp;
   }
 
   bool operator==(deep_iterator const& o) const {
      if (outer_it!=o.outer_it) return false;
        stabilize();
      o.stabilize();
      return (inner_it==o.inner_it);
   }
 
   bool operator< (deep_iterator const& o) const {
      if (o.outer_it <   outer_it) return false;
      if (  outer_it < o.outer_it) return true;
        stabilize();
      o.stabilize();
      return inner_it < o.inner_it;
   }
 
   bool operator!=(deep_iterator const& o) const {return !operator==(o);}
 
   bool operator<=(deep_iterator const& o) const {return !(o<*this);}
   bool operator> (deep_iterator const& o) const {return o< *this;}
   bool operator>=(deep_iterator const& o) const {return o<=*this;}
};
 
}//utils::
#endif