accélérer les algorithm

**yan** · 26/11/2007, 16h09

Bonjour,
constatant que les algo utilise souvent la fonction swap. J'ai essayer de jouer avec pour optimiser un sort.
Voici 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
 
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
 
//class qui contient la fonction swap pour éviter des recopie de memoire
class A 
{
public :
	A(int a,std::string s) :myString(s),nb(a){ };
 
	const std::string &GetString() {return myString;}
	bool operator<(const A& a) {return nb<a.nb;}
	A&  operator=(const A& a) 
		{
		static int nbegale(0);
		std::cout<<"= : "<<++nbegale<<std::endl;
		nb<a.nb;
		myString=a.myString;
		return (*this);
		}
	void swap(A& a) 
		{
			static int nbswap(0);
			std::cout<<"swap : "<<++nbswap<<std::endl;
			std::swap(nb,a.nb);
			myString.swap(a.myString);
		};
private:
	std::string myString;
	int nb;
 
};
//specialisation de la fonction swap pour la class A
template<>
inline void std::swap<A> ( A& a, A& b )
{
	a.swap(b);
};
 
int main(int argc, char** argv)
{
	//mon vecteur a trier
	std::vector<A> vect;
       //on remplie de n'importe quoi
      //le but etant quil y en ai assez pour que swap soit appelé
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
 
     //on fait le trie
	std::sort(vect.begin(),vect.end());
return 0;
}

En prenant l'hypothèse qu'un égale dure 1 second (du au reallocation et recopie de memoire), et swap .5s (echange de la mémoire, donc peut de recopie)

Les résultats que j'obtiens sous visual 20005 sont :
- sans le swap : 234 operation egale = 234s
- avec le swap : 74 operation swap et 72 operation egale = 109 s

Ce qui n'est pas négligable.
Maintenant je me demandé si :
1- ce que j'ai fait est tout à fait correcte
2- il n'y as pas d'autre manière de faire
3- on est obligé de spécifier std::swap

[EDIT]
4- existe t'il d'autre astuce comme celle la???
merci

**yan** · 26/11/2007, 18h54

voici une rversion qui marche avec GCC

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
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
 
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
 
//class qui contient la fonction swap pour éviter des recopie de memoire
class A
{
public :
	A(int a,std::string s) :myString(s),nb(a){ };
 
	const std::string &GetString() {return myString;}
	bool operator<(const A& a)const {return nb<a.nb;}
	A&  operator=(const A& a)
		{
		static int nbegale(0);
		std::cout<<"= : "<<++nbegale<<std::endl;
		nb=a.nb;
		myString=a.myString;
		return (*this);
		}
	void swap(A& a)
		{
			static int nbswap(0);
			std::cout<<"swap : "<<++nbswap<<std::endl;
			std::swap(nb,a.nb);
			myString.swap(a.myString);
		};
private:
	std::string myString;
	int nb;
 
};
//specialisation de la fonction swap pour la class A
namespace std
{
template<>
inline void swap<A> ( A& a, A& b )
{
	a.swap(b);
};
}
 
int main(int argc, char** argv)
{
	//mon vecteur a trier
	std::vector<A> vect;
       //on remplie de n'importe quoi
      //le but etant quil y en ai assez pour que swap soit appelé
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
 
     //on fait le trie
	std::sort(vect.begin(),vect.end());
	return 0;
}

Les résultats que j'obtiens avec GCC sous ubuntu sont :
- sans le swap : 361 operation egale = 361s
- avec le swap : 88 operation swap et 185 operation egale = 229 s

**yan** · 26/11/2007, 18h58

Au faite, pour ceux qui veule tester,pour enlever le swap, il suffit de commenter la definition de std::swap

**yan** · 27/11/2007, 22h51

personne n'as d'idée???

**yan** · 27/11/2007, 23h08

Bon,
j'ai trouvé un truc pour ceux que cela intéresse :
http://www.tantalon.com/pete/cppopt/...l.htm#Swapping

**r0d** · 08/03/2008, 11h08

Il serait intéressant de faire des tests sur des gros conteneurs bien remplis. Et chronométrer, avec différentes méthodes, sur différentes plateformes, et avec une machine dédiée (je veux dire un machine où aucune appli ne tourne, pas même les démons/services réseau etc.)

**yan** · 08/03/2008, 11h34

Envoyé par r0d

Il serait intéressant de faire des tests sur des gros conteneurs bien remplis. Et chronométrer, avec différentes méthodes, sur différentes plateformes, et avec une machine dédiée (je veux dire un machine où aucune appli ne tourne, pas même les démons/services réseau etc.)

Why not

Le petit bout de code que j'ai fournie est pour cela aussi

**reptils** · 09/03/2008, 02h00

pas mal le post.... seulement j'ai essayer de lancer ton code (avec le swap décommenté) et c'est l'opérateur d'affectation qui est appelé

comment forcer l'appel de swap?

Edit: j'ai essayé de changer le code pour afficher à l'écran le contenu du vector<A> utilisant l'algo copy, avec un ostream_iterator de maniere sioux, mais ça marche pas la compilation... des idées?

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
 
#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>
#include <string>
 
//class qui contient la fonction swap pour éviter des recopie de memoire
 
 
class A
{
public :
	A(int a,std::string s) :myString(s),nb(a){ };
 
	const std::string &GetString() {return myString;}
 
	bool operator<(const A& a)const {return nb<a.nb;}
 
	A&  operator=(const A& a)
	{
		static int nbegale(0);
		std::cout<<"= : "<<++nbegale<<std::endl;
		nb=a.nb;
		myString=a.myString;
		return (*this);
	}
 
	void swap(A& a)
	{
		static int nbswap(0);
		std::cout<<"swap : "<<++nbswap<<std::endl;
		std::swap(nb,a.nb);
		myString.swap(a.myString);
	}
 
	friend std::ostream& operator <<(std::ostream& lhs, A& rhs)
	{
		rhs.Print(lhs);
 
		return  lhs;
	}	
 
	void Print(std::ostream& os)
	{
		os<< "id= " << nb <<" chaine= " << myString;	
	}
 
 
private:
	std::string myString;
	int nb;
 
};
//specialisation de la fonction swap pour la class A
namespace std
{
template<>
inline void swap<A> ( A& a, A& b )
{
	a.swap(b);
};
}
 
int main(int argc, char** argv)
{
	//mon vecteur a trier
	std::vector<A> vect;
 
       //on remplie de n'importe quoi
      //le but etant quil y en ai assez pour que swap soit appelé
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
 
     //on fait le trie
	std::sort(vect.begin(),vect.end());
 
	std::copy(vect.begin(),vect.end(),std::ostream_iterator<A>(std::cout," "));
 
	return 0;
}

**yan** · 09/03/2008, 08h42

Envoyé par reptils

pas mal le post.... seulement j'ai essayer de lancer ton code (avec le swap décommenté) et c'est l'opérateur d'affectation qui est appelé

comment forcer l'appel de swap?

Tu compile avec quoi? C'est possible que ca ne marche pas avec toute les implementation. Ca marche avec visual et gcc normalement

Edit: j'ai essayé de changer le code pour afficher à l'écran le contenu du vector<A> utilisant l'algo copy, avec un ostream_iterator de maniere sioux, mais ça marche pas la compilation... des idées?

Je regarderai tout à l'heure

**yan** · 09/03/2008, 09h17

Code :

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

1
2
3
4
5
6
std::ostream& operator <<(std::ostream& lhs, A& rhs)
	{
		rhs.Print(lhs);
 
		return  lhs;
	}

faut la mettre hors de la declaration de la class. Il faut peut etre un const A

**reptils** · 09/03/2008, 11h04

Envoyé par Mongaulois

Tu compile avec quoi? C'est possible que ca ne marche pas avec toute les implementation. Ca marche avec visual et gcc normalement

pour faire vite j'ai utilisé le gcc de cygwin (3.4.4)

Envoyé par Mongaulois

Code :

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

1
2
3
4
5
6
std::ostream& operator <<(std::ostream& lhs, A& rhs)
	{
		rhs.Print(lhs);
 
		return  lhs;
	}

faut la mettre hors de la declaration de la class. Il faut peut etre un const A

oui tu as raison, ça marche maintenant, il faut aussi que je "constifie" la A et la méthode Print

**yan** · 09/03/2008, 11h07

avec l'affichage du contenue :

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
#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>
#include <string>
 
//class qui contient la fonction swap pour éviter des recopie de memoire
 
 
class A
{
public :
	A(int a,std::string s) :myString(s),nb(a){ };
 
	const std::string &GetString() {return myString;}
 
	bool operator<(const A& a)const {return nb<a.nb;}
 
	A&  operator=(const A& a)
	{
		static int nbegale(0);
		std::cout<<"= : "<<++nbegale<<std::endl;
		nb=a.nb;
		myString=a.myString;
		return (*this);
	}
 
	void swap(A& a)
	{
		static int nbswap(0);
		std::cout<<"swap : "<<++nbswap<<std::endl;
		std::swap(nb,a.nb);
		myString.swap(a.myString);
	}
 
	friend std::ostream& operator <<(std::ostream& lhs, const A& rhs);
	void Print(std::ostream& os) const
	{
		os<< "id= " << nb <<" chaine= " << myString<<std::endl;	
	}
 
 
private:
	std::string myString;
	int nb;
 
};
std::ostream& operator <<(std::ostream& lhs,const  A& rhs)
	{
		rhs.Print(lhs);
 
		return  lhs;
	}	
//specialisation de la fonction swap pour la class A
namespace std
{
template<>
inline void swap<A> ( A& a, A& b )
{
	a.swap(b);
};
}
 
int main(int argc, char** argv)
{
	//mon vecteur a trier
	std::vector<A> vect;
 
       //on remplie de n'importe quoi
      //le but etant quil y en ai assez pour que swap soit appelé
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
 
     //on fait le trie
	std::sort(vect.begin(),vect.end());
 
	std::copy(vect.begin(),vect.end(),std::ostream_iterator<A>(std::cout," "));
 
	return 0;
}

**yan** · 09/03/2008, 11h19

Envoyé par reptils

pour faire vite j'ai utilisé le gcc de cygwin (3.4.4)

Normalement ca fonctionne. En faite peut que tu n'as pas fait attention. IL ne fait pas que des swap. Il fait les deux

**reptils** · 09/03/2008, 11h21

oui mais seul les messages d'opération d'affectation s'affichent, et j'en ai 361 comme par hasard

**yan** · 09/03/2008, 11h26

Envoyé par reptils

oui mais seul les messages d'opération d'affectation s'affichent, et j'en ai 361 comme par hasard

ok...
Peut tu mettre le code?
Histoire que j'essaie de mon coté avec le même code?

**reptils** · 09/03/2008, 11h41

et hop!

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
173
174
175
 
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>
#include <string>
 
//class qui contient la fonction swap pour éviter des recopie de memoire
 
 
class A
{
public :
	A(int a,std::string s) :myString(s),nb(a){ };
 
	const std::string &GetString() {return myString;}
 
	bool operator<(const A& a)const {return nb<a.nb;}
 
	A&  operator=(const A& a)
	{
		static int nbegale(0);
		std::cout<<"= : "<<++nbegale<<std::endl;
		nb=a.nb;
		myString=a.myString;
		return (*this);
	}
 
	void swap(A& a)
	{
		static int nbswap(0);
		std::cout<<"swap : "<<++nbswap<<std::endl;
		std::swap(nb,a.nb);
		myString.swap(a.myString);
	}
 
	friend std::ostream& operator<<(std::ostream& lhs,const A& rhs);
 
 
	void Print(std::ostream& os) const
	{
		os<< "id= " << nb <<" chaine= " << myString;	
	}
 
 
private:
	std::string myString;
	int nb;
 
};
 
std::ostream& operator<<(std::ostream& lhs,const A& rhs)
{
	rhs.Print(lhs);
 
	return  lhs;
}
 
 
//specialisation de la fonction swap pour la class A
namespace std
{
template<>
inline void swap<A> ( A& a, A& b )
{
	a.swap(b);
};
}
 
int main(int argc, char** argv)
{
	//mon vecteur a trier
	std::vector<A> vect;
 
       //on remplie de n'importe quoi
      //le but etant quil y en ai assez pour que swap soit appelé
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
 
     //on fait le trie
	std::sort(vect.begin(),vect.end());
 
	std::copy(vect.begin(),vect.end(),std::ostream_iterator<A>(std::cout," \n"));
 
	return 0;
}

Commentes le std::copy si tu ne souhaite pas voir affiché le contenu du vector

**yan** · 09/03/2008, 11h47

Peut tu réessayer en enlevant la toute première ligne

Code :

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

#include <cstdlib>

**reptils** · 09/03/2008, 11h55

c'est pareil, en fait j'ai mis tout à l'heure parce que je voulais faire un system("pause")

**yan** · 09/03/2008, 12h02

Envoyé par reptils

c'est pareil, en fait j'ai mis tout à l'heure parce que je voulais faire un system("pause")

On ne sais jamais....
Je testerais tout à l'heure

**yan** · 09/03/2008, 14h22

donc en faite, j'ai trouvé le problème

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
 template<typename _ForwardIterator1, typename _ForwardIterator2>
    inline void
    iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
    {
      typedef typename iterator_traits<_ForwardIterator1>::value_type
	_ValueType1;
      typedef typename iterator_traits<_ForwardIterator2>::value_type
	_ValueType2;
 
      // concept requirements
      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
				  _ForwardIterator1>)
      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
				  _ForwardIterator2>)
      __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
				  _ValueType2>)
      __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
				  _ValueType1>)
 
      const _ValueType1 __tmp = *__a;
      *__a = *__b;
      *__b = __tmp;
    }

cette fonction n'utilise pas le swap....
SI tu remplace ce morceau de code

Code :

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

1
2
3
 const _ValueType1 __tmp = *__a;
      *__a = *__b;
      *__b = __tmp;

par

Code :

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

swap( *__a ,*__b);

et que tu met la partie swap au dessus,
ca marche de la balle. Mais bon

ca ce trouve dans le fichier
include\c++\3.4.2\bits\stl_algobase.h

accélérer les algorithm

SL & STL C++

Discussions similaires

Partager

Partager