SFINAE, iterateurs de map et C++03

**ternel** · 20/01/2016, 15h58

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 :

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
 
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 :

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

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 :

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

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 :

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

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 :

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

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 :

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

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?

**Iradrille** · 20/01/2016, 18h08

Envoyé par leternel

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

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

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

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

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

**stendhal666** · 20/01/2016, 18h24

J'ai pas VS alors à tester:

Code C++ :

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

**Iradrille** · 20/01/2016, 18h31

@stendhal666, presque, reste une erreur bizarre.

Code :

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

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 :

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

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>>>'

**stendhal666** · 20/01/2016, 19h41

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 C++ :

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

**jo_link_noir** · 21/01/2016, 03h52

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 :

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

SFINAE, iterateurs de map et C++03

C++

Vue hybride

Discussions similaires

Partager

Partager