Discussion :

[YuGiOhJCJ]

Bonjour,
j'ai un programme C++ qui effectue un tri rapide sur un tableau.
Petit souci : avec certaines valeurs pour le tableau, une erreur apparait :

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
 
$ ./a.out
Taille du tableau?4
Valeurs du tableau?
T[0]=2
T[1]=1
T[2]=3
T[3]=5
T[0]=2
T[1]=1
T[2]=3
T[3]=5
T[0]=1
T[1]=2
T[2]=3
T[3]=5
*** glibc detected *** ./a.out: free(): invalid next size (fast): 0x0804a008 ***
======= Backtrace: =========
/lib/libc.so.6[0xb7e9c564]
/lib/libc.so.6(cfree+0x90)[0xb7ea0010]
/usr/lib/libstdc++.so.6(_ZdlPv+0x21)[0xb805fa11]
./a.out[0x8048bdb]
/lib/libc.so.6(__libc_start_main+0xe0)[0xb7e47390]
./a.out[0x8048781]
======= Memory map: ========
08048000-08049000 r-xp 00000000 08:04 2804       /home/yugiohjcj/Documents/Textes/Etudes/FLIN402/tp2/a.out
08049000-0804a000 rw-p 00001000 08:04 2804       /home/yugiohjcj/Documents/Textes/Etudes/FLIN402/tp2/a.out
0804a000-0806b000 rw-p 0804a000 00:00 0          [heap]
b7d00000-b7d21000 rw-p b7d00000 00:00 0
b7d21000-b7e00000 ---p b7d21000 00:00 0
b7e30000-b7e31000 rw-p b7e30000 00:00 0
b7e31000-b7f76000 r-xp 00000000 08:02 14420      /lib/libc-2.7.so
b7f76000-b7f77000 ---p 00145000 08:02 14420      /lib/libc-2.7.so
b7f77000-b7f79000 r--p 00145000 08:02 14420      /lib/libc-2.7.so
b7f79000-b7f7a000 rw-p 00147000 08:02 14420      /lib/libc-2.7.so
b7f7a000-b7f7d000 rw-p b7f7a000 00:00 0
b7f7d000-b7f87000 r-xp 00000000 08:02 200        /usr/lib/libgcc_s.so.1
b7f87000-b7f88000 rw-p 00009000 08:02 200        /usr/lib/libgcc_s.so.1
b7f88000-b7fac000 r-xp 00000000 08:02 14424      /lib/libm-2.7.so
b7fac000-b7fad000 r--p 00023000 08:02 14424      /lib/libm-2.7.so
b7fad000-b7fae000 rw-p 00024000 08:02 14424      /lib/libm-2.7.so
b7fae000-b8089000 r-xp 00000000 08:02 3252       /usr/lib/libstdc++.so.6.0.9
b8089000-b808c000 r--p 000da000 08:02 3252       /usr/lib/libstdc++.so.6.0.9
b808c000-b808e000 rw-p 000dd000 08:02 3252       /usr/lib/libstdc++.so.6.0.9
b808e000-b8095000 rw-p b808e000 00:00 0
b80b6000-b80b8000 rw-p b80b6000 00:00 0
b80b8000-b80d4000 r-xp 00000000 08:02 14462      /lib/ld-2.7.so
b80d4000-b80d5000 r--p 0001b000 08:02 14462      /lib/ld-2.7.so
b80d5000-b80d6000 rw-p 0001c000 08:02 14462      /lib/ld-2.7.so
bfdc1000-bfdd6000 rw-p bffeb000 00:00 0          [stack]
ffffe000-fffff000 r-xp 00000000 00:00 0          [vdso]
Abandon

Il me semble, d'après mon expérience, que ce sont des erreurs d'allocation dynamique de mémoire.
Bien sûr mon programme fonctionne dans d'autres cas :

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
 
$ ./a.out
Taille du tableau?4
Valeurs du tableau?
T[0]=9
T[1]=7
T[2]=6
T[3]=4
T[0]=9
T[1]=7
T[2]=6
T[3]=4
T[0]=4
T[1]=6
T[2]=7
T[3]=9

Donc pourriez vous m'expliquer ce phénomène étrange?

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
 
#include <iostream>
using namespace std;
//Affiche les elements d'un tableau T de taille n
void afficher_tableau(int T[], int n){
	for(int i=0;i<=n;i++){
		cout << "T[" << i << "]=" << T[i] << endl;
	}
}
//Echange les elements d'indice u et v dans un tableau t
void echanger(int u, int v, int t[]){
	int c;
	c=t[u];
	t[u]=t[v];
	t[v]=c;
}
//Partitionne un tableau et renvoi le pivot
int partitionner(int T[], int deb, int fin){
	int pivot = T[deb];
	int ind_pivot=deb;
	for(int i=deb;i<=fin;i++){
		if(T[i] < pivot){ //Si l'element est plus petit que le pivot
			ind_pivot++; //On incremente la position du pivot
			echanger(ind_pivot,i,T); //On echange l'element et le pivot
		}
	}
	echanger(ind_pivot, deb, T);
	return(ind_pivot);
}
//Tri un tableau en utilisant la methode quicksort
void tri_rapide(int T[], int deb, int fin){
	int pivot; //Le pivot
	if(deb<fin){ //Cas d'arret
		pivot=partitionner(T, deb, fin); //Partition du tableau en 2
		tri_rapide(T, deb, pivot-1); //Tri de la 1ere partie
		tri_rapide(T, pivot+1, fin); //Tri de la 2eme partie
	}
}
//Fonction principale
int main(){
	//Creation d'un tableau dynamique
	int* T = new int;
	int n = 0;
	cout << "Taille du tableau?";
	cin >> n;
	cout << "Valeurs du tableau?\n";
	for(int i=0;i<=n-1;i++){
		cout << "T[" << i << "]=";
		cin >> T[i];
	}
	//Affichage du tableau avant le tri
	afficher_tableau(T, n-1);
	//Appel de la fonction de tri
	tri_rapide(T, 0, n-1);
 
	//Affichage du tableau apres le tri
	afficher_tableau(T, n-1);
	//Liberation du tableau
	delete T;
	return(0);
}

Merci.

[Arzar]

Salut !
int* T = new int;
Là, tu déclares un unique entier dans le tas, pas un tableau d'entier!

Code :

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

1
2
3
4
5
 
//Creation d'un tableau dynamique
int* T = new int[size];
...
delete[] T;

Et le plus fantastique dans tout ça c'est que le debuggeur ne plante que sur delete T, pas avant, et même pas sur les accès T[i], alors que la mémoire n'est pas allouée !
Ah, les joies du C...

[poukill]

Code :

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

1
2
3
4
5
6
 
void afficher_tableau(int T[], int n){
	for(int i=0;i<=n;i++){
		cout << "T[" << i << "]=" << T[i] << endl;
	}
}

WAAAAAAAAAAAAAAAAAAAAAAAAAAA ça fait mal aux yeux !
tu veux vraiment pas utiliser std::vector ? les algos de tri de la STL ?
ça t'éviterai l'erreur que vient de signaler arzar !

[HanLee]

Je pense que c'est un programme pour apprendre à coder un quicksort, non ?

[3DArchi]

J'ai pas tout lu en détail, mais, par habitude, le '<=' sur le for ça me fait 'tilt'. Ne serait-ce pas un '<'.

[EDIT] : bon, je viens de regarder, et c'est cohérent avec la façon dont c'est appelé. En revanche, comme dit en début, quand je lis ça, pour moi une alarme se lève. Traditionnellement, le n désigne la taille du tableau. Ici, il signale le dernier index accessible. Cela pose deux problèmes :
1/ un code inhabituel sera mal compris -> risque de maintenance.
2/ est-tu conscient de ce qui se passe pour un tableau vide? Là ça marche, mais est-ce fait exprès ?
En fait, dans la logique des itérateurs, le end est toujours inaccessible ; c'est pour cela que n est la taille du tableau.

[YuGiOhJCJ]

Merci pour vos réponses.
Finalement j'ai opté pour une solution de tableau statique :

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
 
//Fonction principale
int main(){
	//Demande de la taille du tableau
	int n = 0;
	cout << "Taille du tableau?";
	cin >> n;
	//Creation d'un tableau de taille n
	int T[n];
	cout << "Valeurs du tableau?\n";
	for(int i=0;i<=n-1;i++){
		cout << "T[" << i << "]=";
		cin >> T[i];
	}
	//Affichage du tableau avant le tri
	afficher_tableau(T, n-1);
	//Appel de la fonction de tri
	tri_rapide(T, 0, n-1);
	//Affichage du tableau apres le tri
	afficher_tableau(T, n-1);
	return(0);
}

Comme ça, c'est impeccable.

tu veux vraiment pas utiliser std::vector ?

Je ne connais pas std::vector, je jetterai un oeil à ça.

les algos de tri de la STL ?

STL? C'est quoi ça?

Code :

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

Je pense que c'est un programme pour apprendre à coder un quicksort, non ?

C'est un programme que j'ai écrit en regardant des exemples sur le net du quicksort.

n désigne la taille du tableau

.
justement n c'est la taille de mon tableau : n=4 signifie un tableau de 4 éléments T[0...3]. Enfin je dis ça dans mon main()...Tu parles de la fonction afficher_tableau() peut être? Dans ce cas oui...C'est à corriger.

J'ai une question : pourquoi créer un tableau dynamiquement? Il semble que statiquement ça fonctionne...

[poukill]

Ah...
Bon, t'as du boulot!

Pour info, voici une version C++ possible de ton programme.

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
#include <list>
#include <iostream>
 
int main()
{
   // Création d'une liste
   std::list<int> ma_liste;
 
   // Initialisation au hasard (avec srand ce serait mieux)
   ma_liste.push_back(2);
   ma_liste.push_back(8);
   ma_liste.push_back(6);
   ma_liste.push_back(1);
   ma_liste.push_back(12);
   ma_liste.push_back(4);
 
   // tri 
   ma_liste.sort();
   // on affiche
   std::copy(liste.begin(), liste.end(), std::ostream_iterator<int>(std::cout, "\n"));
}

Code non testé et non compilé, mais c'est l'idée.

Tu trouveras tout plein de renseignements sur la STL et donc également sur std::vector, etd::list, etc... dans la FAQ C++ (lien dans ma signature)

Bonne continuation,

Poukill

[3DArchi]

justement n c'est la taille de mon tableau : n=4 signifie un tableau de 4 éléments T[0...3]. Enfin je dis ça dans mon main()...Tu parles de la fonction afficher_tableau() peut être? Dans ce cas oui...C'est à corriger.

Oui je parle dans afficher_tableau. C'est inhabituel de ne pas passer la taille du tableau mais n-1. Je pense qu'il vaut mieux, pour ce genre de chose, rester conservateur et suivre l'usage. De la même façon, je vois plus souvent du code écrit 'indice<taille' plutôt que 'indice<=taille-1'. Il vaut mieux adopter la première forme (qui se justifie par l'utilisation de size_t dans les tailles, et à ce moment taille-1 peut mener à des surprises pour des tailles à 0).

[poukill]

Oui je parle dans afficher_tableau. C'est inhabituel de ne pas passer la taille du tableau mais n-1. Je pense qu'il vaut mieux, pour ce genre de chose, rester conservateur et suivre l'usage. De la même façon, je vois plus souvent du code écrit 'indice<taille' plutôt que 'indice<=taille-1'. Il vaut mieux adopter la première forme (qui se justifie par l'utilisation de size_t dans les tailles, et à ce moment taille-1 peut mener à des surprises pour des tailles à 0).

Je suis d'accord avec mon collègue 3DArchi.
Cependant, en C++, il n'est pas habituel de passer la taille d'un tableau du tout. On préfère utiliser une structure qui contient la taille du tableau, comme ça on n'a plus à s'en occuper!

• Soit on utilise une classe très générale : std::vector, qui permet facilement de redimensionner les tableaux
• Soit on veut quand même un tableau de taille fixe, et on va utiliser std::tr1::array