Discussion :

[camboui]

Bonjour à tous (ça fait un bail que je passais plus par ici )

Voici un petit code sympa de foncteur générique simple.

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
template<class C, typename T, T C::*P>
struct by_member
{
	bool operator()(C const & rl, C const & rr) const
	{
		return rl.*P < rr.*P;
	}
	bool operator()(C const & rl, T const & t) const
	{
		return rl.*P < t;
	}
	bool operator()(T const & t, C const & rr) const
	{
		return t < rr.*P;
	}
};

Et voici un petit code exemple d'utilisation (je vous laisse ajouter les #include nécessaires si vous l'essayer).

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
struct employee
{
	int         f_id;
	std::string f_firstname;
	std::string f_lastname;
	int         f_ssnumber;
 
	employee(int id, std::string const & firstname, std::string const & lastname, int ssnumber) :
		f_id(id), f_firstname(firstname), f_lastname(lastname), f_ssnumber(ssnumber) {}
};
 
typedef by_member<employee, std::string, &employee::f_lastname> by_lastname;
 
int _tmain(int argc, _TCHAR* argv[])
{
	std::vector<employee> v;
	v.push_back(employee(5, "John", "Smith", 1582));
	v.push_back(employee(3, "Paul", "Howard", 1777));
	v.push_back(employee(7, "Jude", "Muller", 1325));
	std::sort(v.begin(), v.end(), by_lastname());
	if ( std::binary_search(v.begin(), v.end(), "Muller", by_lastname()) )
		std::cout << "Found" << std::endl;
	return 0;
}

Simple, propre et efficace me semble-t-il.


Maintenant je souhaiterais un foncteur utilisant deux membres de employee (ou plus) afin de former une clé multiple permettant de trier puis rechercher sur, par exemple, f_lastname et f_firstname.

Je pensais adapter by_member<> comme ceci (c'est juste un début de réflexion):

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
template<class C, typename T1, T1 C::*P1, typename T2, T2 C::*P2>
struct by_2_members
{
	bool operator()(C const & rl, C const & rr) const
	{
		return rl.*P1 < rr.*P1 || (rl.*P1 == rr.*P1 && rl.*P2 < rr.*P2);
	}
	bool operator()(C const & rl, Tuple? const & t) const
	{ // ici ça coince...
		return rl.*P1 < t<1> || (rl.*P1 == t<1> && rl.*P2 < t<2>);
	}
	bool operator()(Tuple? const & t, C const & rr) const
	{ // et ici aussi...
		return t<1> < rr.*P1 || (t<1> == rr.*P1 && t<2> < rr.*P2);
	}
};

Pour un usage comme ceci par exemple:

Code :

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

1
2
3
4
5
6
7
typedef by_2_members<employee, std::string, &employee::f_lastname, std::string, &employee::f_firstname> by_lastname_firstname;
 
	...
 
	std::sort(v.begin(), v.end(), by_lastname_firstname());
	if ( std::binary_search(v.begin(), v.end(), std::tuple("Muller", "Jude"), by_lastname_firstname()) )
		std::cout << "Found" << std::endl;

Je n'aime que moyennement utiliser std::tuple<>, toute idée pour l'éviter est bienvenue.

Ensuite l'usage d'un variadic template pour écrire une forme générale de by_member<> serait pas mal aussi (sans tout transformer en usine à gaz).

Merci pour vos avis

[Ehonn]

Bonjour

J'aime bien l'utilisation de std::tuple, j'ai essayé de le remplacer (dans les signatures) par std::initializer_list mais j'ai pas réussi à donner un brace-enclosed initializer list à std::binary_search (j'ai pas trop chercher).

Voila le code avec std::tuple. Je te laisse le soin de rajouter la généricité voulue.

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
// g++ -Wall -Wextra -Wconversion -Wsign-conversion -Ofast -std=c++11 -pedantic -fopenmp main.cpp -o main && ./main
 
#include <iostream>
#include <array>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
 
struct employee
{
	int         f_id;
	std::string f_firstname;
	std::string f_lastname;
	int         f_ssnumber;
 
	employee(int id, std::string const & firstname, std::string const & lastname, int ssnumber) :
		f_id(id), f_firstname(firstname), f_lastname(lastname), f_ssnumber(ssnumber)
	{ }
};
 
struct comp
{
	bool operator()(employee const & a, employee const & b)
	{
		return std::tie(a.f_lastname, a.f_firstname) < std::tie(b.f_lastname, b.f_firstname);
	}
 
	// std::tuple
 
// 	bool operator()(employee const & e, std::tuple<std::string, std::string> const & value)
// 	{
// 		return std::tie(e.f_lastname, e.f_firstname) < value;
// 	}
// 	
// 	bool operator()(std::tuple<std::string, std::string> const & value, employee const & e)
// 	{
// 		return value < std::tie(e.f_lastname, e.f_firstname);
// 	}
 
	// std::tuple template
 
	template <class value_t>
	bool operator()(employee const & e, value_t const & value)
	{
		return std::tie(e.f_lastname, e.f_firstname) < value;
	}
 
	template <class value_t>
	bool operator()(value_t const & value, employee const & e)
	{
		return value < std::tie(e.f_lastname, e.f_firstname);
	}
 
	// std::initializer_list
 
// 	bool operator()(employee const & e, std::initializer_list<std::string> const & value)
// 	{
// 		return std::tie(e.f_lastname, e.f_firstname) < std::tie(value.begin()[0], value.begin()[1]);
// 	}
// 	
// 	bool operator()(std::initializer_list<std::string> const & value, employee const & e)
// 	{
// 		return std::tie(value.begin()[0], value.begin()[1]) < std::tie(e.f_lastname, e.f_firstname);
// 	}
};
 
int main()
{
	std::vector<employee> v;
 
	v.push_back(employee(5, "John", "Smith", 1582));
	v.push_back(employee(3, "Paul", "Howard", 1777));
	v.push_back(employee(4, "Jane", "Howard", 1847));
	v.push_back(employee(7, "Jude", "Muller", 1325));
 
	for (auto const & e : v) { std::cout << e.f_lastname << " " << e.f_firstname << std::endl; }
	std::cout << std::endl;
 
 
	std::sort(v.begin(), v.end(), comp());
 
	for (auto const & e : v) { std::cout << e.f_lastname << " " << e.f_firstname << std::endl; }
	std::cout << std::endl;
 
 
	if (std::binary_search(v.begin(), v.end(), std::make_tuple("Muller", "Jude"), comp()))
// 	if (std::binary_search(v.begin(), v.end(), std::initializer_list<std::string>{ "Muller", "Jude" }, comp()))
	{
		std::cout << "Found" << std::endl;
	}
 
	return 0;
}

[camboui]

Et bien merci !
Je n'ai jamais utiliser les tuple<> encore, c'est l'occasion de commencer.
Ça n'a pas l'air mal du tout, mais j'ignore si l'usage des fonctions std::tie(), std::forward_as_tuple(), std::make_tuple(), etc, est pénalisant en performance.

Voici le foncteur version template:

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
template<class C,
	typename T1, T1 C::*P1,
	typename T2, T2 C::*P2>
struct by_member2
{
	bool operator()(C const & rl, C const & rr) const
	{
		return std::tie(rl.*P1, rl.*P2) < std::tie(rr.*P1, rr.*P2);
	}
	bool operator()(C const & rl, std::tuple<T1, T2> && t) const
	{
		return std::tie(rl.*P1, rl.*P2) < t;
	}
	bool operator()(std::tuple<T1, T2> && t, C const & rr) const
	{
		return t < std::tie(rr.*P1, rr.*P2);
	}
};

Et un peu de code pour illustrer l'usage:

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
typedef by_member<employee, std::string, &employee::f_lastname> by_lastname;
typedef by_member2<employee,
	std::string, &employee::f_lastname,
	std::string, &employee::f_firstname> by_lastname_firstname;
 
...
 
	std::vector<employee> v;
	v.push_back(employee(5, "John", "Smith", 1582));
	v.push_back(employee(3, "Paul", "Howard", 1777));
	v.push_back(employee(4, "Jane", "Howard", 1847));
	v.push_back(employee(7, "Jude", "Muller", 1325));
	std::sort(v.begin(), v.end(), by_lastname_firstname());
	if ( std::binary_search(v.begin(), v.end(), "Muller", by_lastname()) )
		std::cout << "Found 1" << std::endl;
	if (std::binary_search(v.begin(), v.end(), std::forward_as_tuple("Muller", "Jude"), by_lastname_firstname()))
		std::cout << "Found 2" << std::endl;
	if (!std::binary_search(v.begin(), v.end(), std::forward_as_tuple("Howard", "John"), by_lastname_firstname()))
		std::cout << "Not Found 2" << std::endl;

Je souhaiterai maintenant généraliser le foncteur pour un tri/recherche sur N membres.
Mais là je ne vois pas trop comment m'y prendre.
Une aide serait bienvenue. Merci !

[Ehonn]

Pour les performances :
Le temps de compilation est plus long (dans la version générique donnée en dessous, dès que j'ajoute le foncteur à 3 éléments, le temps de compilation passe de 3,5 secondes à 4,3).
Le temps d'exécution est normalement le même que la version écrite à la main à partir de l'optimisation -O1. En effet, les std::tuple n'apparaissent plus dans le code assembleur (tu peux vérifier sur https://gcc.godbolt.org/)

Voici le brouillon du code générique. J'ai utilisé C++14 mais à part le auto en retour de fonction, le code devrait fonctionner en C++11. J'ai utilisé des lambdas car à la base je voulais directement les passer en paramètre template à la structure mais je ne sais pas si ce genre de code est possible en C++ :

Code :

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

1
2
3
4
5
// Déclaration
template <class ... T, T ...>
struct type;
// Utilisation
type<5, 3.14, "char *"> t;

Si oui, je te laisse changer ça si besoin.
Cela permettrai de ne pas stocker les fonctions dans le std::tuple qui nous empêche d'utiliser ... directement (je dois passer par seq<S ...>).

Je n'ai pas nettoyé le code il doit avoir moyen de le simplifier, ne serait-ce qu'en séparant les différentes parties indépendantes et en donnant des noms plus explicites.
Je prend mes paramètres par T const &, ça peut être une limitation a enlevée en rendant le code (encore) plus générique.
Au final le code est relativement court (et haut niveau (et complexe)).
L'utilisation est sympathique comme souvent en C++
Voilà le code :

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
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
// g++ -Wall -Wextra -Wconversion -Wsign-conversion -Ofast -std=c++14 -pedantic -fopenmp main.cpp -o main && ./main
 
#include <iostream>
#include <array>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
 
 
 
template<int ...>
struct seq { };
 
template<int N, int ...S>
struct gens : gens<N-1, N-1, S...> { };
 
template<int ...S>
struct gens<0, S...> {
  typedef seq<S...> type;
};
 
 
struct employee
{
	int         f_id;
	std::string f_firstname;
	std::string f_lastname;
	int         f_ssnumber;
 
	employee(int id, std::string const & firstname, std::string const & lastname, int ssnumber) :
		f_id(id), f_firstname(firstname), f_lastname(lastname), f_ssnumber(ssnumber)
	{ }
};
 
std::ostream & operator <<(std::ostream & out, employee const & e)
{
	out << "{ " << e.f_id << ", " << e.f_firstname << ", " << e.f_lastname << ", " << e.f_ssnumber << " }";
	return out;
}
 
 
template <class T, class ... getter_t>
struct comp_generic
{
private:
 
	std::tuple<getter_t const ...> m_getters;
 
public:
 
	comp_generic(getter_t const & ... getters) : m_getters(std::make_tuple(getters...))
	{ }
 
	// operator()(T const & a, T const & b)
 
	bool operator()(T const & a, T const & b)
	{
		return fct_T_T(a, b, typename gens<sizeof...(getter_t)>::type());
	}
 
	template <int ... S>
	bool fct_T_T(T const & a, T const & b, seq<S ...> const)
	{
		return std::tie(std::get<S>(m_getters)(a)...) < std::tie(std::get<S>(m_getters)(b)...);
	}
 
	// operator()(T const & t, values_t const & values)
 
	template <class values_t>
	bool operator()(T const & t, values_t const & values)
	{
		return fct_T_values(t, values, typename gens<sizeof...(getter_t)>::type());
	}
 
	template <class values_t, int ... S>
	bool fct_T_values(T const & t, values_t const & values, seq<S ...> const)
	{
		return std::tie(std::get<S>(m_getters)(t)...) < values;
	}
 
	// operator()(values_t const & values, T const & t)
 
	template <class values_t>
	bool operator()(values_t const & values, T const & t)
	{
		return fct_values_T(values, t, typename gens<sizeof...(getter_t)>::type());
	}
 
	template <class values_t, int ... S>
	bool fct_values_T(values_t const & values, T const & t, seq<S ...> const)
	{
		return values < std::tie(std::get<S>(m_getters)(t)...);
	}
};
 
template <class T, class ... getter_t>
auto make_comp(getter_t const & ... getters)
{
	return comp_generic<T, getter_t const & ...>(getters...);
}
 
int main()
{
	std::vector<employee> v;
 
	v.push_back(employee(5, "John", "Smithh", 1582));
	v.push_back(employee(3, "Paul", "Howard", 1777));
	v.push_back(employee(1, "Paul", "Howard", 1798));
	v.push_back(employee(4, "Jane", "Howard", 1847));
	v.push_back(employee(7, "Jude", "Muller", 1325));
 
	for (auto const & e : v) { std::cout << e << std::endl; } std::cout << std::endl;
 
	auto const get_id = [](employee const & e) -> int const & { return e.f_id; };
	auto const get_firstname = [](employee const & e) -> std::string const &  { return e.f_firstname; };
	auto const get_lastname = [](employee const & e) -> std::string const & { return e.f_lastname; };
	auto const get_ssnumber = [](employee const & e) -> int const & { return e.f_ssnumber; };
 
	auto const comp_ssnumber = make_comp<employee>(get_ssnumber);
	auto const comp_firstname = make_comp<employee>(get_firstname);
	auto const comp_id = make_comp<employee>(get_id);
	auto const comp_lastname_firstname = make_comp<employee>(get_lastname, get_firstname);
	auto const comp_lastname_firstname_id = make_comp<employee>(get_lastname, get_firstname, get_id);
 
 
	std::cout << "Sort by id" << std::endl;
 
	std::sort(v.begin(), v.end(), comp_id);
 
	if (std::binary_search(v.begin(), v.end(), std::make_tuple(5), comp_id))
	{
		std::cout << "{ 5, _, _, _ } found in:" << std::endl;
	}
 
	for (auto const & e : v) { std::cout << e << std::endl; } std::cout << std::endl;
 
 
	std::cout << "Sort by firstname" << std::endl;
 
	std::sort(v.begin(), v.end(), comp_firstname);
 
	for (auto const & e : v) { std::cout << e << std::endl; } std::cout << std::endl;
 
 
	std::cout << "Sort by lastname and firstname" << std::endl;
 
	std::sort(v.begin(), v.end(), comp_lastname_firstname);
 
	for (auto const & e : v) { std::cout << e << std::endl; } std::cout << std::endl;
 
 
	std::cout << "Sort by ssnumber" << std::endl;
 
	std::sort(v.begin(), v.end(), comp_ssnumber);
 
	for (auto const & e : v) { std::cout << e << std::endl; } std::cout << std::endl;
 
 
	std::cout << "Sort by lastname and firstname and id" << std::endl;
 
	std::sort(v.begin(), v.end(), comp_lastname_firstname_id);
 
	if (std::binary_search(v.begin(), v.end(), std::make_tuple("Howard", "Jane", 4), comp_lastname_firstname_id))
	{
		std::cout << "{ 4, Howard, Jane, _ }" << "found:" << std::endl;
	}
 
	for (auto const & e : v) { std::cout << e << std::endl; } std::cout << std::endl;
 
	return 0;
}

[camboui]

Et bien merci encore
J'en apprends des choses.

J'ai modifié ton code en supprimant les seq<> et gens<> puisque cela existe déjà (std::index_sequence<> et std::index_sequence_for<>)

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
template <class T, class ... getter_t>
struct comp_generic
{
private:
 
	std::tuple<getter_t const ...> m_getters;
 
public:
 
	comp_generic(getter_t const & ... getters) : m_getters(std::make_tuple(getters...))
	{ }
 
	// operator()(T const & a, T const & b)
 
	bool operator()(T const & a, T const & b)
	{
		return fct_T_T(a, b, std::index_sequence_for<getter_t...>{});
	}
 
	template <std::size_t ... S>
	bool fct_T_T(T const & a, T const & b, std::index_sequence<S ...> const)
	{
		return std::tie(std::get<S>(m_getters)(a)...) < std::tie(std::get<S>(m_getters)(b)...);
	}
 
	// operator()(T const & t, values_t const & values)
 
	template <class values_t>
	bool operator()(T const & t, values_t const & values)
	{
		return fct_T_values(t, values, std::index_sequence_for<getter_t...>{});
	}
 
	template <class values_t, std::size_t ... S>
	bool fct_T_values(T const & t, values_t const & values, std::index_sequence<S ...> const)
	{
		return std::tie(std::get<S>(m_getters)(t)...) < values;
	}
 
	// operator()(values_t const & values, T const & t)
 
	template <class values_t>
	bool operator()(values_t const & values, T const & t)
	{
		return fct_values_T(values, t, std::index_sequence_for<getter_t...>{});
	}
 
	template <class values_t, std::size_t ... S>
	bool fct_values_T(values_t const & values, T const & t, std::index_sequence<S ...> const)
	{
		return values < std::tie(std::get<S>(m_getters)(t)...);
	}
};

Ça compile et tourne tel quel sous VS2015, et le résultat est comme attendu.

Mais comme tu le soulignes, le mieux serait de passer sous forme de paramètres le(s) membre(s) de structure directement à comp_generic<> comme je l'ai fait dans mes essais de code (structure by_member).
L'usage de lambda ne me semble pas élégant dans ce cas-ci (et c'est du fonctionnel).

C'est plus lisible d'écrire quelque chose comme by_member<employee, std::string, &employee::f_firstname> plutot
que [](employee const & e) -> std::string const & { return e.f_firstname; }.
Enfin, il me semble.

[jo_link_noir]

C'est plus lisible d'écrire quelque chose comme by_member<employee, std::string, &employee::f_firstname> plutot
que [](employee const & e) -> std::string const & { return e.f_firstname; }.
Enfin, il me semble.

std::mem_fn(&employee::f_firstname), enfin, il me semble

[camboui]

Oui, mais non...
Ou alors je ne vois pas.

std::mem_fn() est une fonction, pas un type ni un énumérable que l'on pourrait passer en paramètre d'une classe template.

Je souhaite passer &employee::f_firstname comme paramètre d'une classe variadic template (comme dans le foncteur by_member<> décrit au début).
boost::multi_index utilise le même principe (je m'en suis inspiré d'ailleurs).

Je vais voir ce que je peux faire avec std::mem_fn(), mais si vous avez d'autres idées elles sont bienvenues

[jo_link_noir]

std::mem_fn() est une fonction, pas un type ni un énumérable que l'on pourrait passer en paramètre d'une classe template.

Au mettre titre que les lambdas dans le code de Ehonn. Les valeurs sont stockées et le type passé en paramètre de template. Remplacer une des lambdas par le résultat de mem_fn compile sans problème.

Par contre, make_comp devrait construire un comp_generic<T, std::decay_t<getter_t>...> au risque de se retrouver avec des danglings références. Avec le make_tuple dans le constructeur de comp_generic, cela ne rate pas, le tuple interne contient des références sur des temporaires détruites.
Mais bon, comme les lambdas passés n'ont pas de contexte, cela ne se voit pas...

En gros, actuellement il y l'équivalent de tuple<int const &> t(make_tuple(1)); avec std::get<0>(t) une valeur qui n'existe plus.
(note: std::make_tuple n'est pas utile).

Un autre problème avec la fonction de comparaison et que toutes les fonctions seront appelées, même si toutes les valeurs ne sont pas comparées. De plus std::tie ne supporte pas les rvalue, donc ne fonctionne pas avec des fonctions qui en retournent, niveau généricité, on peut mieux faire.

Concernant by_member, je pense que tu y gagnerais en mettant un seul paramètre pour le type: by_member<employee::*std::string, &employee::f_firstname> pour pouvoir écrire au final by_member<decltype(&employee::f_firstname), &employee::f_firstname> et avoir la même syntaxe pour des fonctions membres. À condition évidemment d'avoir la bonne spécialisation template.
Généralement, pour ce genre de classe, on finit avec une macro qui fait le decltype: #define BY_MEMBER(m) by_member<decltype(m), m>, en attendant d'avoir des templates auto...

[camboui]

Effectivement, std::mem_fn() compile mais crash à l'execution...

Je ne souhaite pas utiliser les lambda ni std::mem_fn(), je cherche justement une solution dans la déclaration des foncteurs, pas à leur instanciation.
Donc on oublie le code fonctionel proposé.
Mais cela valait la peine d'y jeter un coup d'oeil afin de comprendre et essayer (je débute en C++11 ).

Bon, je vous ponds brut de décoffrage le résultat de mes reflexions de la journée:

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
template<class C, typename T, T C::*P>
struct a_member
{
	typedef C owner_type;
	typedef T type;
	static constexpr T C::* mptr= P;
};
 
 
template<class ...M>
struct by_members;
 
template<class M>
struct by_members<M>
{
	typedef M this_type;
	typedef typename M::owner_type C;
	typedef typename M::type T;
	bool operator()(C const & rl, C const & rr) const
	{
		return rl.*M::mptr < rr.*M::mptr;
	}
	bool operator()(C const & rl, T const & t) const
	{
		return rl.*M::mptr < t;
	}
	bool operator()(T const & t, C const & rr) const
	{
		return t < rr.*M::mptr;
	}
};
 
template<class M, class ...R >
struct by_members<M, R...>
{
	typedef M this_type;
	typedef typename M::owner_type C;
	typedef typename M::type T;
	typedef typename by_members<R...>::this_type R_type;
	bool operator()(C const & rl, C const & rr) const
	{
		return std::tie(rl.*M::mptr, rl.*R_type::mptr) < std::tie(rr.*M::mptr, rr.*R_type::mptr);
	}
	template<class ...Ts>
	bool operator()(C const & rl, std::tuple<Ts...> const & t) const
	{
		return std::tie(rl.*M::mptr, rl.*R_type::mptr) < t;
	}
	template<class ...Ts>
	bool operator()(std::tuple<Ts...> const & t, C const & rr) const
	{
		return t < std::tie(rr.*M::mptr, rr.*R_type::mptr);
	}
};

Quelques exemples d'usage:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef by_members<
	a_member<employee, std::string, &employee::f_lastname>
> by_lastname;
 
typedef by_members<
	a_member<employee, std::string, &employee::f_lastname>,
	a_member<employee, std::string, &employee::f_firstname>
> by_lastname_firstname;
 
typedef by_members<
	a_member<employee, std::string, &employee::f_lastname>,
	a_member<employee, std::string, &employee::f_firstname>,
	a_member<employee, int        , &employee::f_id>
> by_lastname_firstname_id; // celui-ci ne fonctione pas... encore ;-)

Ça compile et ça s'execute comme voulu jusqu'à 2 paramètres template pour by_members<>.Mais ça ne passe pas à trois paramètres, le dérouler (unpack) n'est pas effectué dans les std::tie<>.

Oui, l'usage de decltype et d'une macro seront utiles pour réduire un peu les répétitions verbeuses et rébarbatives.
Ce sera le fignolage final

En attendant, vous pouvez m'aider à dérouler les paramètres dans les std::tie<>

[camboui]

Yeahaa !

Commençons par deux petits traits asc_member<> et desc_member<>(vous l'avez deviné, un pour le tri ascendant l'autre pour le tri descendant):

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
template<class C, typename T, T C::*P>
struct asc_member
{
	typedef C owner_type;
	typedef T type;
	static constexpr T C::* mptr = P;
 
	static constexpr bool lt(T const & l, T const & r) //noexcept ?
	{ return (l < r); }
};
 
template<class C, typename T, T C::*P>
struct desc_member
{
	typedef C owner_type;
	typedef T type;
	static constexpr T C::* mptr = P;
 
	static constexpr bool lt(T const & l, T const & r) //noexcept ?
	{ return (r < l); }
};

Ensuite la déclaration et la spécialisaton de base de by_members<M>:

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
template<class ...M>
struct by_members;
 
template<class M>
struct by_members<M>
{
	typedef M this_type;
	typedef typename M::owner_type C;
	typedef typename M::type T;
 
	bool operator()(C const & rl, C const & rr) const
	{
		return M::lt(rl.*M::mptr, rr.*M::mptr);
	}
 
	bool operator()(C const & rl, T const & t) const
	{
		return M::lt(rl.*M::mptr, t);
	}
 
	bool operator()(T const & t, C const & rr) const
	{
		return M::lt(t, rr.*M::mptr);
	}
};

Et puis le gros morceau, le code générique de by_members<M, R...>:

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
template<class M, class ...R >
struct by_members<M, R...>
{
	typedef M this_type;
	typedef typename M::owner_type C;
	typedef typename M::type T;
 
	bool operator()(C const & rl, C const & rr) const
	{
		return M::lt(rl.*M::mptr, rr.*M::mptr) ||
			(!M::lt(rr.*M::mptr, rl.*M::mptr) && by_members<R...>()(rl, rr));
	}
 
	bool operator()(C const & rl, T const & t) const
	{
		return M::lt(rl.*M::mptr, t);
	}
	template<class ...Ts>
	typename std::enable_if<sizeof...(Ts) == 2,
		bool>::type
		operator()(C const & rl, std::tuple<Ts...> const & t) const
	{
		return M::lt(rl.*M::mptr, std::get<0>(t)) ||
			(!M::lt(std::get<0>(t), rl.*M::mptr) &&
				by_members<R...>()(rl, std::get<1>(t))
				);
	}
	template<class ...Ts>
	typename std::enable_if<sizeof...(Ts) != 2,
		bool>::type
		operator()(C const & rl, std::tuple<Ts...> const & t) const
	{
		return M::lt(rl.*M::mptr, std::get<0>(t)) ||
			(!M::lt(std::get<0>(t), rl.*M::mptr) &&
				by_members<R...>()(rl, t._Get_rest())
				);
	}
 
	bool operator()(T const & t, C const & rr) const
	{
		return M::lt(t, rr.*M::mptr);
	}
	template<class ...Ts>
	typename std::enable_if<sizeof...(Ts) == 2,
		bool>::type
		operator()(std::tuple<Ts...> const & t, C const & rr) const
	{
		return M::lt(std::get<0>(t), rr.*M::mptr) ||
			(!M::lt(rr.*M::mptr, std::get<0>(t)) &&
				by_members<R...>()(std::get<1>(t), rr)
				);
	}
	template<class ...Ts>
	typename std::enable_if<sizeof...(Ts) != 2,
		bool>::type
		operator()(std::tuple<Ts...> const & t, C const & rr) const
	{
		return M::lt(std::get<0>(t), rr.*M::mptr) ||
			(!M::lt(rr.*M::mptr, std::get<0>(t)) &&
				by_members<R...>()(t._Get_rest(), rr)
				);
	}
};

Exemple:

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
typedef by_members<
	asc_member<employee, decltype(employee::f_lastname), &employee::f_lastname>
> by_lastname;
 
typedef by_members<
	asc_member<employee, decltype(employee::f_lastname), &employee::f_lastname>,
	asc_member<employee, decltype(employee::f_firstname), &employee::f_firstname>
> by_lastname_firstname;
 
typedef by_members<
	asc_member<employee, decltype(employee::f_lastname), &employee::f_lastname>,
	asc_member<employee, decltype(employee::f_firstname), &employee::f_firstname>,
	desc_member<employee,decltype(employee::f_id), &employee::f_id>
> by_lastname_firstname_id;
 
int main()
{
	std::vector<employee> v;
	v.push_back(employee(5, "John", "Smith", 1582));
	v.push_back(employee(3, "Paul", "Howard", 1777));
	v.push_back(employee(1, "Paul", "Howard", 1798));
	v.push_back(employee(4, "Jane", "Howard", 1847));
	v.push_back(employee(7, "Jude", "Muller", 1325));
 
	std::sort(v.begin(), v.end(), by_lastname_firstname());
	if ( std::binary_search(v.begin(), v.end(), "Muller", by_lastname()) )
		std::cout << "[Muller] Found" << std::endl;
	if ( std::binary_search(v.begin(), v.end(), std::forward_as_tuple("Muller", "Jude"), by_lastname_firstname()) )
		std::cout << "[Muller, Jude] Found" << std::endl;
	std::string Howard = "Howard";
	if (!std::binary_search(v.begin(), v.end(), std::forward_as_tuple(Howard, "John"), by_lastname_firstname()))
		std::cout << "[Howard, John] Not Found" << std::endl;
	if (std::binary_search(v.begin(), v.end(), Howard, by_lastname_firstname()))
		std::cout << "[Howard] (partial search) Found" << std::endl;
 
	std::sort(v.begin(), v.end(), by_lastname_firstname_id());
	if ( std::binary_search(v.begin(), v.end(), std::forward_as_tuple("Howard", "Paul", 1), by_lastname_firstname_id()) ) // recherche sur 3 membres
		std::cout << "{ 1, Howard, Paul, _ }" << " Found" << std::endl;
	if (std::binary_search(v.begin(), v.end(), std::forward_as_tuple("Howard", "Jane"), by_lastname_firstname_id())) // recherche sur 2 membres
		std::cout << "{ _, Howard, Jane, _ }" << " (partial search) Found" << std::endl;
	if (std::binary_search(v.begin(), v.end(), "Muller", by_lastname_firstname_id())) // recherche sur 1 membre
		std::cout << "{ _, Muller, _, _ }" << " (partial search) Found" << std::endl;
return 0;
}

L'usage de traits permet d'en créer d'autres permettant un traitement sur les membres avant de les comparer (mettre les string en minuscule et sans accent par exemple), bien que ce ne soit pas très efficace car le traitement sera effectué avant chaque accès. C'est un développement pour plus tard...

Je vois un inconvénient: l'usage de std::tuple::_Get_rest() qui n'est pas documenté (et donc pas standard).
_Get_rest() permet de récupérer le sous-tuple d'un tuple sans le premier élément.
Existe-t-il un moyen standard pour obtenir cela ?

Remerci pour vos relecture

[jo_link_noir]

Plutôt que récupérer un sous-tuple, tu peux boucler sur l'indice. Quelque chose comme ça:

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
template<std::size_t i> using i_ = std::integral_constant<std::size_t, i>;
 
template<class... M>
struct by_members
{
  template<class T, class U>
  bool operator()(T const & x, U const & y) const
  { return cmp(i_<0>{}, lt<0>(x,y), x, y); }
 
private:
  template<std::size_t i> using elem = typename std::tuple_element<i, std::tuple<M...>>::type;
 
  template<std::size_t i>
  decltype(auto) get_val(C const & obj) const
  { return obj.*elem<i>::mptr; }
 
  template<std::size_t i>
  decltype(auto) get_val(std::tuple<Ts...> const & t) const
  { return std::get<i>(t); }
 
  template<std::size_t i, class T, class U>
  bool lt(T const & x, U const & y) const
  { return elem<i>::lt(get_val<i>(x), get_val<i>(y)); }
 
  template<std::size_t i, class T, class U>
  bool cmp(i_<i>, bool val, T const & x, U const & y) const
  { return val || (!lt<i>(y,x) && cmp(i_<i+1>{}, lt<i+1>(x,y), x, y)); }
 
  template<class T, class U>
  bool cmp(i_<sizeof...(M)-1>, bool val, T const &, U const &) const
  { return val; }
};

[camboui]

Ok merci.
La lisibilité en prend un coup quand même

J'ai écrit une petite fonction qui extrait le sous-tuple sans le premier élément d'un tuple:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
template <std::size_t ...S, class T, class ...Ts>
inline constexpr std::tuple<Ts...>
	tuple_minus_leftmost_helper(std::tuple<T, Ts...> const & t, std::index_sequence<S...> const) noexcept
{
	return std::forward_as_tuple(std::get<S+1>(t)...);
}
 
template<class T, class ...Ts>
inline constexpr std::tuple<Ts...> tuple_minus_leftmost(std::tuple<T, Ts...> const & t)
{
	return tuple_minus_leftmost_helper(t, std::index_sequence_for<Ts...>{});
}

Un peu plus lisible je trouve, et ça peut servir comme base de réflexion pour qui veut extraire n'importe quel sous-tuple d'un tuple

Merci à tous, donc.
Je trouvais cet exercice intéressant et utile (un foncteur générique qui va remplacer +80% des foncteurs de mes applications). Il m'a permis de mettre un premier pas dans les variadic template.

Ceci dit...
J'ai regardé le code assembleur généré, en release et toutes optimisations activées (sous VS2015), et je trouve que le résultat est assez moyen.
J'ai comparé le code avec trois versions spécialisées explicites de by_members<> avec 1, 2 et 3 paramètres template (qui couvrent probablement 95% des besoins). Ces dernières génèrent un code plus compact (avec une compilation plus rapide). A l'exécution les différences de performance ne devraient cependant que peu se faire sentir (bien que je n'ai pas vérifié).

Au délà...
J'ai finalement un petit doute sur les bienfaits des variadic template.
La syntaxe est lourde, la lisibilité est difficile, l'abstraction est exigente.
On s'interroge sur les temps de compilation et sur les performances du code assembleur généré.
Et au final on écrit un code générique permettant l'usage de template sans limite théorique de paramètres, certes, mais qu'on utilisera en pratique la plupart du temps avec 1, 2 ou 3 paramètres, très rarement plus de 5 me semble-t-il. La spécialisation pour ces cas est accessible (et c'est d'ailleurs ce qu'on faisait avant, n'est-ce-pas ? ).

Mais puisque les variadic template sont là, incitons-nous à s'en servir, sans se sentir obligé
Depuis le temps, je suppose que le débat a déjà eu lieu

[camboui]

Je reviens sur mes propos sur le code assembleur généré.

Un code comme ceci

Code :

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

std::binary_search(v.begin(), v.end(), std::make_tuple(std::string("Muller"), std::string("Jude")), by_lastname_firstname())

ou comme ceci

Code :

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

std::binary_search(v.begin(), v.end(), std::make_tuple("Muller", "Jude"), by_lastname_firstname())

change complètement la donne.

Le premier semble bien plus efficace. En voyant le code assembleur du deuxième cas je crois deviner que les chaines de caractères sont converties en std::string avant chaque comparaison par l'operator<().

Voilà, c'est tout

[ternel]

C'est exacte, et c'est parce que "Muller" étant un const char*, make_tuple crée un tuple<const char*, const char*>.