Discussion :

[Mindiell]

Bonjour à tou(te)s,

Je suis en train de créer une liste d'éléments (des cellules d'un tableau en gros) et je me demandais dans quoi les stocker (non, pas un vector ).
Mon problème c'est que ces cellules doivent être triées, mais que c'est leurs attributs qui détermine leur ordre. Les attributs étants fixés, je peux calculer l'ordre et le conserver dès que je crée l'objet, d'où ma question : map ou set pour stocker mes objets ? La grandeur de l'ordre est-il inclut à l'objet ou pas pour vous ?

Merci de vos opinions bienvenues

En attendant, je pars sur un set...

[LittleWhite]

Bonjour,

Je sais que sur la FAQ C++ il y a un magnifique schéma pour choisir le conteneur parfait pour chaque cas, cela pourra vous être utile .

Sinon, je vous conseille la map, que si vous voulez retrouver un objet dans un temps linéaire en vous basant sur l'attribut. Si vous n'avez pas besoin de ceci, et juste faire un tri selon les attributs, alors le set ira .

[koala01]

Salut,

Je ne reviendrai pas sur l'entrée de la faq déjà citée, mais, pour te permettre de trouver la meilleure solution, il peut "suffire" de t'interroger sur la possibilité qu'il y a éventuellement de modifier ne serait-ce qu'une partie de l'objet tout en gardant une clé identique.

S'il apparait que la valeur (éventuellement calculée) de la clé utilisée pour le tri est intrinsèquement liée à l'objet (comprend: que toute modification, aussi minime soit-elle, de l'objet occasionne une modification de la valeur servant pour le tri), tu peux envisager d'utiliser un std::set.

Si par contre, la clé servant pour le tri est un temps soit peu indépendante de l'objet (comprend: s'il est possible qu'un objet plus ou moins légèrement modifié continue à présenter une valeur servant pour le tri identique), il sera sans doute préférable d'envisager l'utilisation de la std::map.

Enfin, si l'idée est de trier tes différents objets selon différentes valeurs (d'avoir plusieurs clés, en somme ), il est peut-être utile d'envisager l'utilisation de boost.multi_index

[Mindiell]

Bonjour,

Merci à vous deux. J'avais, bien entendu, regardé la FAQ et le schéma toujours utile est sur ma clef USB

Je veux contenir des cellules d'une carte (pour un jeu) isométrique. L'ordre sert à l'affichage : jamais il ne sera modifié, jamais les coordonnées de la cellule ne seront modifiés.
En même temps, j'aurai peut-être, en effet, besoin de retrouver "facilement" une cellule en particulier (donc index multiples ?).

Bref, pour le moment ce n'est qu'une question de tri pour l'affichage. Pour le moment je ne calcule rien, ma fonction "operator<" gère l'ordre en se basant sur les coordonnées. Ca me fait un objet plus léger et qui ne doit être trié qu'une seule fois, à la création.

En y repensant en écrivant, je pourrais peut-être tout stocker dans un vector au chargement, puis tout restocker dans un set avant chaque affichage (une copie de juste ce qu'il faut pour l'affichage) ?

D'autres idées, n'hésitez pas ?

[3DArchi]

Salut
Si tout est trié dès le début et que ça n'évolue pas, il me semble qu'il y a des interventions de fcharton indiquant qu'un vecteur trié sera plus efficace qu'une map.
Tiens, j'en ai trouvé une ici ou là.

[Mindiell]

Hum, très intéressant l'idée du vecteur de paire.
Je crois que je vais me pencher dessus, merci !

[camboui]

...

S'il apparait que la valeur (éventuellement calculée) de la clé utilisée pour le tri est intrinsèquement liée à l'objet (comprend: que toute modification, aussi minime soit-elle, de l'objet occasionne une modification de la valeur servant pour le tri), tu peux envisager d'utiliser un std::set.

...

Je n'ai pas encore eu le cas (modifier les attributs servant au calcul de clé d'un set) mais que se passe-t-il dans ce cas ? Le set est-il dans un état indéfini ?

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
struct MaStruct
{
 std::string s;
 int i;
 friend bool operator<(MaStruct const & l, MaStruct const & r)
 {
  return l.i<r.i;
 }
};
 
...
 
std::set<MaStruct> s;
 
...
 
MaStruct m;
m.s="toto";
m.i=5;
std::pair<std::set<MaStruct>::iterator, bool> p=s.insert(m);
p.first->i=10;//clé modifiée, set "instable" ?

[zul]

Ça ne devrait pas compiler.
Un set<T>::iterator ne renvoie que des const T& (set modélise un SimpleAssociativeContainer (voir http://www.sgi.com/tech/stl/SimpleAs...Container.html), en particulier

The type of iterator used to iterate through a Simple Associative Container's elements. The types X::iterator and X::const_iterator must be the same type. That is, a Simple Associative Container does not provide mutable iterators. [1]

) .

[camboui]

???

Non seulement ça compile, mais en plus ça s'exécute. Voici un petit code de test

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
struct MaStruct
{
	std::string s_;
	unsigned u_;
	MaStruct(unsigned u=0): u_(u) {}
	friend bool operator<(MaStruct const & l, MaStruct const & r)
	{
		return l.u_<r.u_;
	}
};
 
int main()
{
	std::set<MaStruct> myset;
	MaStruct m(5);
	m.s_="toto";
	myset.insert(m);
	m.u_=1;
	myset.insert(m);
	m.u_=9;
	myset.insert(m);
	std::set<MaStruct>::iterator it;
	for (it=myset.begin(); it!=myset.end(); ++it)
		std::cout << it->u_ << std::endl;
 
	std::cout << std::endl;
 
	m.u_=3;
	std::pair<std::set<MaStruct>::iterator, bool> p=myset.insert(m);
	p.first->u_=10;//clé modifiée, set "instable" ?
	m.u_=7;
	p=myset.insert(m);
	p.first->u_=1;//clé modifiée, set "instable" ?
	for (it=myset.begin(); it!=myset.end(); ++it)
		std::cout << it->u_ << std::endl;
	return 0;
}

Voici le résultat affiché

Code :

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

1
2
3
4
5
6
7
8
9
1
5
9

1
10
5
1
9

Non seulement on peut se retrouver avec des doublons dans un std::set<> mais en plus ses éléments ne sont pas ordonnés lorsqu'on le parcourt via ses iterators comme on doit le faire.

Je suis un peu "choqué" !
Il manque comme un garde-fou.