Discussion :

[Yoann_DM]

Bonjour,

Tout d'abord, excusez moi pour le manque d'accent dans ce message, je suis a l'etranger sur un clavier qwerty.

Voila mon probleme. Je dispose d'une structure assez simple qui ne contient que deux champs : un entier et une string.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
struct mapping{
	int code;
	string label;
 
	bool operator<(const mapping& map) const {
		return code < map.code;
	}
 
	bool operator==(const mapping& map) const {
		return label.compare(map.label) == 0 ;
	}
};

Je souhaite creer un set de mapping dont l'ordre est donne par le code comme specifie dans la surcharge de l'operateur <. Jusque la, tout va bien. Je remplis mon set avec des mappings dont le label est different et les elements sont bien ordonnes.

Dans un deuxieme temps, je souhaite ajouter de nouveaux mappings mais cette fois ci je ne suis plus certains qu'un mapping avec le meme label n'existe pas deja dans le set. En fait, s'il existe, je souhaite mettre a jour son code et sinon, je souhaite ajouter un nouveau mapping. J'ai donc besoin que la fonction find(m) me retourne un pointeur vers un mapping ayant le meme label que m. C'est la que le probleme intervient. Malgre la surcharge de l'operateur ==, find semble se baser sur l'ordre etabli par l'operateur <. Voici un bout de code pour illustrer ce comportement.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
mapping m = {1,"xxx"};
mapping m2 ={1, "yyy"};
 
this->fn[0].insert(m);
 
set<mapping>::iterator itTmp;
itTmp = this->fn[0].find(m2);
if (itTmp != this->fn[0].end() ) {
	cout << "m2 existe "<<endl;
 
	if ( !(*itTmp == m2) ){
		cout << "Pourtant ils sont differents selon l'operateur == "<<endl;
	}
}

L' output correspondant est:

Code :

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

1
2
m2 existe
Pourtant ils sont differents selon l'operateur ==

Je pensais qu'en surchargeant les 2 operateurs (< necessaire pour les sets et == pour le find()) tout allait bien se passer malgre le fait qu'ils ne portent pas sur le meme attribut de la structure.

Une idee de comment je peux m'en sortir? Dois je changer de conteneur? Je voudrais eviter la solution d'un iterateur sur tout le set avec comparaison systematique de l'attribut label car cette solution est en O(n) (n pouvant etre assez grand dans mon cas) et je prefererai donc une solution en O(log n) si possible.

Merci d'avance,
Yoann

[Trademark]

Salut,

A mon avis, une map conviendrait peut-être mieux. Je pense à faire :

Code :

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

1
2
3
4
5
6
7
8
std::map<std::string, int> mymap;
// Ajout initial...
mymap["element1"]= 5;
mymap["element2"] = 6;
 
// Etape 2
mymap["element3"] = 5; // Ajout car n'est pas déjà dans la map
mymap["element2"] = 1; // mise à jour de element2

Ce qui m'embête c'est ta structure mapping, si tu veux "mapper" il vaut mieux utiliser la structure est faites pour ça.

Et l'insertion sera en log(n) ainsi que la recherche

Sinon détail, est-ce que tu viens d'un autre langage (Java ou autre ?), parce que je vois des choses comme :

Code :

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

this->blabla; // En C++ il n'est pas d'usage d'accéder à un membre de la classe avec this..

ou

Code :

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

label.compare(map.label) == 0 ; // label == map.label;

[Yoann_DM]

Merci pour ta reponse qui souleve neanmoins une autre question. L'utilisation d'une map me permettrait elle d'ordonner ses elements en fonction du score (c'est essentiel pour mon algo). Autrement dit, puis je surcharger l'operateur < en me basant non pas sur la cle mais sur la valeur du mapping?

Sinon, oui je viens du java comme tu as pu largement le constater en si peu de code Merci pour les qqs commentaires qui amelioreront ma pratique.

[Trademark]

Déjà je pense qu'il faut "débroussailler un peu", tu veux qu'un élément soit unique sur :

• Le score
• Le string
• Les deux

D'après ce que j'ai compris tu veux garantir l'unicité sur le string tout en accédant en log(n) au score.

Le problème c'est que tu ne peux pas à la fois trier sur le string et en même temps trier sur le score (sauf en utilisant deux containers, je n'ai pas à ma connaissance un container qui fasse ça tout seul). Néanmoins comment vas-tu accéder à ton score ? Il te faudra bien passer par le string non ? Et donc tu auras un temps d'accès au score en log(n) même si ce n'est pas trié spécifiquement sur le score.

Juste pour nous mettre dans le contexte, est-ce qu'on peut en savoir plus sur ton algo ?

[Yoann_DM]

Je veux que l'element soit unique sur le label (string) mais que les elements soient ordonnes dans le conteneur par le score.

L'acces en log(n) au score n'est pas obligatoire. L'acces au label doit par contre ]etre fait en log(n).

En fait, j'implemente un algo de fouille de donnees sur les valeurs d un cube de donnees. Typiquement, j'ai envi d'extraire des regles du genre "Frequemment, on constate que si le prix des iPhones augmente aux USA et que le cout de revient diminue pour les processeurs utilises ds les iPhone diminue alors le benefice global augmentera dans 2 semaines." Le hic, c'est qu'il y a bcp de combinaisons et surtout que je ne veux pas de regle avec le premice de la regle contenant une generalisation d'un autre element dans ce premice. Par exemple, je ne veux pas de regle avec Prix(iPhone,US) (note A) et Prix(iPhone,New York) (note B). Par consequent, j'ai un mapping pour optimiser ce parcours et eviter de tester des regles candidates qui violent cette contrainte de generalisation.

Les elements les plus precis (B ici) se voient attribuer un nombre premier. Les autres se voient attribuer un code qui est grosso modo le produit des code de niveau inferieur. Ici, le code de A sera donc le produit du code de B par les codes associes aux autres specialisations de A (par exemple Prix(iPhone,Texas)).

Ce qui correspond a la premiere etape ds mon premier message est d attribuer un nombre premier pour tous les bas niveau. Ensuite, pour chacun de ses bas niveau, j execute une requete MDX pour recuperer ses generalisations. Sauf qu'il y a des elements communs ds les generalisations (Prix(iPhone,New York) et Prix(iPhone,Texas) ont les memes generalisations). Je vais donc en rencontrer certaines plusieurs fois et tant mieux car cela me permet de multiplier le score de maniere adequate. Apres avoir traite les generalisations de Prix(iPhone,New York), Prix(iPhone,US) aura le score de Prix(iPhone,New York). Au traitement de Prix(iPhone,Texas), le code associe a Prix(iPhone,US) sera code(Prix(iPhone,New York)) x code(Prix(iPhone,Texas)).

A la fin, je veux donc une liste ordonnee par score

lab1 score1
lab2 score2
lab3 score3
......
labn scoren

Si le reste de la division de scorei par scorej est nul (i>j => scorei >= scorej) alors inutile de considerer la regle (labi)(labj) puisque labi est une generalisation de labj. L'ordre me sert aussi a eviter de considerer le premice (lab2)(lab1) si j'ai deja considere le premice (lab1)(lab2).

Voila l'idee en gros pour parcourir l'espace de recherche.

[Gymble]

Je pensais qu'en surchargeant les 2 operateurs (< necessaire pour les sets et == pour le find()) tout allait bien se passer malgre le fait qu'ils ne portent pas sur le meme attribut de la structure.

std::set (et std::map) n'utilise jamais l'operateur ==. L'égalité entre a et b est definie via l'operateur < comme étant (!a<b && !b<a).

En fait, s'il existe, je souhaite mettre a jour son code et sinon, je souhaite ajouter un nouveau mapping.

La partie clé des iterateurs sur les map et les iterateurs sur les set sont const.
En effet, les conteneurs étant trie, si tu modifie la clé de tri des objets qui sont dedans tu corromps ton conteneur.
Donc si tu veux modifie un élément de la clé, tu dois retirer ton élément du conteneur, modifie la clé et le réinsérer.

A mon sens pour ton problème tu as besoin de deux conteneurs, l'un contenant des objets tries suivant le code (std::set<mapping, compare_sur_code>), l'autre contenant en clé tes labels et en valeur un iterateur vers le premier (std::unordered_map<label, std::set<mapping>::iterator, hash_sur_label, equal_sur_label>).
Avec les foncteurs qui vont bien et le code qui va bien pour garantir la cohérence entre les deux.

[koala01]

Salut,

En fait, je me demande si ton problème ne pourrait pas trouver une solution avec les multi index de boost...

typiquement, ce sont des conteneurs qui permettent de gérer plusieurs index, dont un qui est considéré comme "index primaire" (celui sur lequel le tri global est effectué) et "autant d'index secondaidre que tu peux le souhaiter".