Discussion :

[stof]

Bonjour,

J'ai un tableau:

Code :

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

1
2
3
4
5
6
7
8
9
CMyClass _mytab[MAX_NB];
 
class CMyClass
{
....
char* nom
...
//getter et setter associés
}

Avec quelle méthode puis-je trier le tableau selon le critère alphabétique du champ nom?

merci.

[3DArchi]

std::sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

[Florian Goo]

Bonjour,

Utilise plutôt les conteneurs de la STL (std::vector, std::list, …) à la place des vieux tableaux à la C.
Tu verras, c'est tellement plus simple !

[koala01]

Saut,

Déjà, si j'étais toi, je me dépêcherais de remplacer le tableau statique de ta classe par un joli std::vector<CMyClass>, et le champs nom par une encore plus jolie std::string nom.

Tu verra comme cela pourra te faciliter la vie par la suite

Ensuite, il sera sans doute temps de te poser la question de savoir si tu veux *réellement* disposer d'un acces aléatoire aux différents éléments de ton tableau, ou si tu souhaites qu'il reste trié "en toutes circonstances", ce qui rendra les recherches bien plus rapides, ou si tu envisage de toutes manière un acces "séquentiel" aux élément du "tableau".

En effet, si tu peux accepter d'avoir un tableau momentanément non trié, mais de parcourrir l'ensemble de ses éléments de toutes manières l'un à la suite de l'autre et de manière séquentielle, une liste d'éléments semblerait plus adaptée.

Si, de plus, tu souhaites que les différents éléments restent triés quoi qu'il arrive, il semblerait opportun de te diriger vers un set d'éléments, voire, vers une map utilisant une chaine comme clé et un élément de type cMyClass comme valeur.
Cette solution aura sans doute l'inconvénient de rendre le nom redondant (présent un fois sous la forme de clé et une fois sous la forme du champs de la variable de type CMyClass), mais te permettra d'éviter d'avoir créer les différents foncteurs de comparaison requis pour les différents algorithmes de tri / de recherche, car tout existe déjà dans la classe string, ce qui en fait un candidat "pas trop mauvais" pour servir de clé dans une map

D'autre part, si tu décide d'utiliser un set, il faut savoir que tu ne pourra accéder aux différents éléments que de manière constante, ce qui peut parfois poser problème (selon ce que tu veux faire des éléments contenus )

Par contre, l'énorme avantage que tu pourra tirer de ces deux manière de stocker tes éléments sera que la recherche sera optimisée parce que les éléments seront toujours triés...

N'oublie pas que, quoi qu'il arrive, une fois que le champs nom de ta structure aura été utilisé comme clé, il faudra veiller à ce que sa valeur ne soit plus jamais modifiée, sous peine de placer tes données dans un état incohérent.

Sinon, dans l'ensemble, que tu décides d'utiliser un vector, une list, ou un set, le plus facile (et généralement requis) pour effectuer un tri / une recherche, c'est de disposer d'un foncteur nommé less qui renvoie vrai si l'élément de gauche dans la comparaison elem1 < elem2 est plus grand que l'élément de droite.

Une fois ce foncteur créé, il te sera très simple, selon le choix du conteneur que tu auras effectué, d'utiliser soit un algorithme de tri comme std::sort, soit un conteneur trié, de type set

[stof]

J'aurais du préciser mais il n'est pas question de remanier l'ensemble du code de ce programme.
Donc voilà ce qui est utilisé et c'est juste une petite modification à apporter.

Je suis autant désolé que vous mais il faut absolument que je parte de ce tableau (il est rempli à plein d'endroits dans le code et à la fin, j'écris le contenu dans un fichier; et c'est simplement là que j'aurais besoin de le trier avant d'écrire).

Si je fais
vector<CMyClass> myvector (_mytab, myints+nb_elements);
vector<CMyClass>::iterator it;
est-ce que je peux m'en sortir après avec mes comparaisons de char* pour une éventuelle fonction sort?

[Florian Goo]

Dans ce cas, utilise std::sort comme te l'a indiqué 3DArchi.
Les itérateurs de début et de fin correspondent à table et table + MAX_NB.

EDIT: Un lien vers un article sur les algorithme de la STL (comprenant std::sort) : http://r0d.developpez.com/articles/algos-stl/

[stof]

OK, c'est facile avec des int mais pour trier des CMyClass, c'est une autre paire de manches.

[Florian Goo]

Oui… moi-même, quand j'arrive à écrire un appel à un algorithme de la STL qui fonctionne, je me sens dans la peau d'un être supérieurement intelligent (un de ces quatre, va falloir que je me le paie, cet Effective STL).

Vas-y étape par étape. Tout d'abord, écris la fonction (libre) de comparaison qui va bien. Elle doit renvoyer bool et prendre deux références constantes de CMyClass.

[yan]

Un truc comme

Code :

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

1
2
3
4
5
6
7
8
9
10
struct test
{
bool operator(const CMyClass* t1, const CMyClass* t2)
 { 
      return strcmp(t1->nom,t2->nom) <0;
 }
 
}
...
std::sort( _mytab, _mytab+MAX_NB, test())

Mais faut mieux que tu ajout l'operator= dans CMyClass. SInon t'aura des truc bizzare

[Florian Goo]

Petite correction (pas grand chose, mais on sait jamais, des fois qu'il verrait pas) :

Code :

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

1
2
3
4
5
6
7
8
9
struct test
{
  bool operator()(const CMyClass* t1, const CMyClass* t2)
  { 
    return strcmp(t1->nom,t2->nom) < 0;
  }
};
...
std::sort(_mytab, _mytab + MAX_NB, test());

[koala01]

Un truc comme

Code :

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

1
2
3
4
5
6
7
8
9
10
struct test
{
bool operator(const CMyClass* t1, const CMyClass* t2)
 { 
      return strcmp(t1->nom,t2->nom) <0;
 }
 
}
...
std::sort( _mytab, _mytab+MAX_NB, test())

Mais faut mieux que tu ajout l'operator= dans CMyClass. SInon t'aura des truc bizzare

Et sous la forme de référence, ca donne encore mieux

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
struct test
{
bool operator(const CMyClass& t1, const CMyClass& t2)
 { 
      return strcmp(t1->nom,t2->nom) <0;
      /* si on a transformé nom en std::string, c'est encore plus simple:
       */
      return t1.nom<t2.nom;
 }
 
}
...
std::sort( _mytab, _mytab+MAX_NB, test())

[ram-0000]

Heu c'est la même écriture cela :

Code :

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

bool operator(...)

et cela :

Code :

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

bool operator()(...)

Ou bien il y en a un qui a tord

et pour apporter ma contribution, un petit const sur la fonction car elle ne modifie par les paramètres :

Code :

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

bool operator()(...) const

[Florian Goo]

et pour apporter ma contribution, un petit const sur la fonction car elle ne modifie par les paramètres :

Code :

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

bool operator()(...) const

Le const de fin indique qu'il ne modifie aucune variable membre de la classe test !

Cordialement.
Monsieur Je-Sais-Tout

[ram-0000]

Le const de fin indique qu'il ne modifie aucune variable membre de la classe test !

C'est ce que je voulais dire (la faute de frappe de fin de journée, cela peut arriver)

Par contre, les 2 notations sont légales ou bien il y en a une qui est fausse :

Code :

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

1
2
3
4
 
bool operator()(...)
ou
bool operator(...)

[Florian Goo]

Non non, seul le premier fonctionne. C'est une faute de frappe aussi, j'imagine.

[yan]

Et sous la forme de référence, ca donne encore mieux

Ca ne marchera pas, non?
Les iterator sont des pointeurs
Mais j'ai un doute

[Sylvain Togni]

Ca ne marchera pas, non?

La version avec des pointeurs, non. La version avec des références oui.

Les iterator sont des pointeurs

Non, les itérateurs sont des itérateurs, c'est à dire des classes. Mais je ne voit pas le rapport.

[Florian Goo]

La version avec des pointeurs, non. La version avec des références oui.

Ouch, oui, l'habitude des vecteurs de pointeurs

Voilà un truc qui compile, histoire qu'on cesse de tourner en rond (et surtout que stof s'y retrouve ) :

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
 
#include <algorithm>
#include <cstring>
 
#define MAX_NB 50
 
struct my_class
{
	char* name;
};
 
struct test
{
	bool operator()(const my_class& t1, const my_class& t2)
	{ 
		return strcmp(t1.name, t2.name) < 0;
	}
};
 
int main()
{
	my_class tab[MAX_NB];
 
	std::sort
	(
		tab,
		tab + MAX_NB,
		test()
	);
 
	return 0;
}

[yan]

Non, les itérateurs sont des itérateurs, c'est à dire des classes. Mais je ne voit pas le rapport.

Je voulais dire dans son cas, l'iterateur est un pointeur.

[koala01]

Ouch, oui, l'habitude des vecteurs de pointeurs

Voilà un truc qui compile, histoire qu'on cesse de tourner en rond (et surtout que stof s'y retrouve ) :<sniped code>

Et, surtout, une version un peu plus C++:

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
 
#include <string>
#include <vector>
struct MyStruct
{
    std::string name;
};
struct test
{
    bool operator()(const MyStruct& s1, const MyStruct& s2) const
    {
        return s1.name<s2.name;
    }
};
 
int main()
{
    std::vector<MyStruct> tab;
    /* remplissage sous la forme de tab.push_back(...) */
    std::sort(tab.begin(), tab.end(); test())
    /* le tableau est trié :-D:-D */
    return 0;
}