IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

SL & STL C++ Discussion :

map ou set ?


Sujet :

SL & STL C++

  1. #1
    Membre confirmé
    Avatar de Mindiell
    Profil pro
    Inscrit en
    juin 2006
    Messages
    735
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : juin 2006
    Messages : 735
    Points : 544
    Points
    544
    Par défaut map ou set ?
    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...
    Mindiell
    "Souvent, femme barrit" - Elephant man

  2. #2
    Responsable 2D/3D/Jeux


    Avatar de LittleWhite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mai 2008
    Messages
    26 072
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : mai 2008
    Messages : 26 072
    Points : 208 370
    Points
    208 370
    Billets dans le blog
    88
    Par défaut
    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 .
    Vous souhaitez participer à la rubrique 2D/3D/Jeux ? Contactez-moi

    Ma page sur DVP
    Mon Portfolio

    Qui connaît l'erreur, connaît la solution.

  3. #3
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    octobre 2004
    Messages
    11 525
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : octobre 2004
    Messages : 11 525
    Points : 29 976
    Points
    29 976
    Par défaut
    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
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  4. #4
    Membre confirmé
    Avatar de Mindiell
    Profil pro
    Inscrit en
    juin 2006
    Messages
    735
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : juin 2006
    Messages : 735
    Points : 544
    Points
    544
    Par défaut
    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 ?
    Mindiell
    "Souvent, femme barrit" - Elephant man

  5. #5
    Rédacteur
    Avatar de 3DArchi
    Profil pro
    Inscrit en
    juin 2008
    Messages
    7 634
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : juin 2008
    Messages : 7 634
    Points : 13 008
    Points
    13 008
    Par défaut
    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 .

  6. #6
    Membre confirmé
    Avatar de Mindiell
    Profil pro
    Inscrit en
    juin 2006
    Messages
    735
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : juin 2006
    Messages : 735
    Points : 544
    Points
    544
    Par défaut
    Hum, très intéressant l'idée du vecteur de paire.
    Je crois que je vais me pencher dessus, merci !
    Mindiell
    "Souvent, femme barrit" - Elephant man

  7. #7
    Membre éprouvé
    Inscrit en
    avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : avril 2005
    Messages : 1 110
    Points : 935
    Points
    935
    Par défaut
    Citation Envoyé par koala01 Voir le message
    ...

    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" ?

  8. #8
    zul
    zul est déconnecté
    Membre éclairé Avatar de zul
    Profil pro
    Inscrit en
    juin 2002
    Messages
    498
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : juin 2002
    Messages : 498
    Points : 668
    Points
    668
    Par défaut
    Ç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]
    ) .

  9. #9
    Membre éprouvé
    Inscrit en
    avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : avril 2005
    Messages : 1 110
    Points : 935
    Points
    935
    Par défaut
    ???

    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.

  10. #10
    Membre confirmé
    Avatar de Mindiell
    Profil pro
    Inscrit en
    juin 2006
    Messages
    735
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : juin 2006
    Messages : 735
    Points : 544
    Points
    544
    Par défaut
    Pour le premier cas, il ne trie qu'à l'insertion si mon souvenir est bon. Donc modifier une clef "casse" le tri du set.
    Pour le deuxième, c'est bizarre, en effet. Que fait un sort sur ce dernier set ?
    Mindiell
    "Souvent, femme barrit" - Elephant man

  11. #11
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    octobre 2004
    Messages
    11 525
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : octobre 2004
    Messages : 11 525
    Points : 29 976
    Points
    29 976
    Par défaut
    Citation Envoyé par camboui Voir le message
    ???

    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.
    Pourrais tu préciser quel compilateur tu utilise

    Parce que j'ai effectué un copier / coller de ton code, et j'ai un fantastique
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    D:\projects\testC++\main.cpp||In function 'int main()':|
    D:\projects\testC++\main.cpp|34|error: assignment of data-member 'MaStruct::u_' in read-only structure|
    D:\projects\testC++\main.cpp|37|error: assignment of data-member 'MaStruct::u_' in read-only structure|
    ||=== Build finished: 2 errors, 0 warnings ===|
    comme on est en droit de s'y attendre

    la ligne 34 étant le fameux p.first->u_=10;//clé modifiée, set "instable" ?

    (testé avec Gcc 4.5.0)
    d'ailleurs, si on essaye de modifier s_ avec un code proche de
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    p.first->s_=std::string("salut");
    on obtient une erreur du genre de
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    D:\projects\testC++\main.cpp|35|error: passing 'const std::string' as 'this' argument of 'std::basic_string<_CharT, _Traits, _Alloc>& std::basic_string<_CharT, _Traits, _Alloc>::operator=(const std::basic_string<_CharT, _Traits, _Alloc>&) [with _CharT = char, _Traits = std::char_traits<char>, _Alloc = std::allocator<char>, std::basic_string<_CharT, _Traits, _Alloc> = std::basic_string<char>]' discards qualifiers|
    parce que c'est l'opérateur d'affectation de la classe std::string qui... n'est pas applicable sur une donnée constante (ce qui prouve bel et bien que c'est toute la structure qui est considérée constante
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  12. #12
    zul
    zul est déconnecté
    Membre éclairé Avatar de zul
    Profil pro
    Inscrit en
    juin 2002
    Messages
    498
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : juin 2002
    Messages : 498
    Points : 668
    Points
    668
    Par défaut
    Pareil que koala => compilateur buggé

    g++ 4.4, g++ 4.5, clang-svn ne compile pas ton example, comme le veut la norme.

    Mais sinon, oui dans l'absolu, modifier les éléments du set "sur place" casse la structure de set (c'est bien pour ça que ce n'est pas légal de le faire, et qu'il faut toujours faire un get, erase, insert) .

  13. #13
    Membre émérite

    Inscrit en
    mai 2008
    Messages
    1 014
    Détails du profil
    Informations forums :
    Inscription : mai 2008
    Messages : 1 014
    Points : 2 252
    Points
    2 252
    Par défaut
    Citation Envoyé par koala01 Voir le message
    Pourrais tu préciser quel compilateur tu utilise
    Très probablement Visual C++ qui, malheureusement, autorise le programmeur étourdi à démolir l'arbre sous-jacent aux set/map s'il ne fait pas attention.
    Ceci-dit, c'est corrigé dans Visual 2010

  14. #14
    Membre éprouvé
    Inscrit en
    avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : avril 2005
    Messages : 1 110
    Points : 935
    Points
    935
    Par défaut
    Arzar, bingo.
    Ici en l'occurence j'ai fait ce petit test avec VS2005.

    Sinon, ben le monde s'écroule un peu. Ça fait des lustres que j'utilise les set<> sans me poser trop de questions. Il m'arrive ainsi d'intégrer un compteur dans la structure pour savoir combien de fois un élément avec même clé a été insérée. Par exemple:
    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
    struct MaStruct
    {
    	std::string s_;
    	unsigned u_, count_;
    	MaStruct(unsigned u=0): u_(u), count_(0) {}
    	friend bool operator<(MaStruct const & l, MaStruct const & r)
    	{
    		return l.u_<r.u_;
    	}
    };
     
    ...
     
    	std::pair<std::set<MaStruct>::iterator, bool> p=myset.insert(m);
    	++p.first->count_;
    En fait il m'arrive assez souvent d'accéder en écriture à l'élément référencé par p.first et retourné par un insert().
    J'aurai un problème de portage le jour où je changerais de compilo.
    Mais donc, si théoriquement tous les iterators de set<> sont constants, comment faites-vous pour accéder en écriture aux éléments d'un set<> ?
    Ici on ne dit pas que l'iterator de set<> est constant.

  15. #15
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    octobre 2004
    Messages
    11 525
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : octobre 2004
    Messages : 11 525
    Points : 29 976
    Points
    29 976
    Par défaut
    Citation Envoyé par camboui Voir le message
    Mais donc, si théoriquement tous les iterators de set<> sont constants, comment faites-vous pour accéder en écriture aux éléments d'un set<> ?
    Ici on ne dit pas que l'iterator de set<> est constant.
    On travaille en quatre temps:
    1- on crée une copie (non constante) de l'élément représenté par l'itérateur
    2 (ou 3) - on modifie la copie obtenue
    3- (ou 2) on supprime l'élément représenté par l'itérateur
    4- on insère la copie modifiée.

    Ou alors, tu peux envisager de déclarer le membre pouvant être modifié (pour autant qu'il n'intervient pas dans la clé de tri) mutable.

    C'est pour cela qu'il est préférable d'utiliser la std::map pour les structures (ou classes) qui peuvent être modifiées sans que cela n'influe sur leur clé de tri
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  16. #16
    Membre éprouvé
    Inscrit en
    avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : avril 2005
    Messages : 1 110
    Points : 935
    Points
    935
    Par défaut
    Finalement, si on en revient à la question du PO, la map<> sera aussi préférable si on souhaite accéder en écriture aux éléments de l'arbre.

    Et j'aurais appris quelque chose de plus au passage. Depuis longtemps la possibilité de changer la clé des éléments d'un set<> me dérangeait. Mais voilà, MS avait tout faux et je l'ignorais

  17. #17
    Membre émérite

    Inscrit en
    mai 2008
    Messages
    1 014
    Détails du profil
    Informations forums :
    Inscription : mai 2008
    Messages : 1 014
    Points : 2 252
    Points
    2 252
    Par défaut
    Citation Envoyé par camboui Voir le message
    Ici on ne dit pas que l'iterator de set<> est constant.
    En fait, si je me souviens bien, d'après la norme, les iterator et les const_iterator doivent être de même type pour les conteneurs associatifs (ou équivalent). Donc, en pratique, on peut considéer qu'un set<T>::iterator n'est qu'un typedef de set<T>::const_iterator.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [Mapping] Mapping SQL Set
    Par Miko95 dans le forum Hibernate
    Réponses: 0
    Dernier message: 05/09/2011, 18h56
  2. Un Map de Sets
    Par wilddances dans le forum Collection et Stream
    Réponses: 4
    Dernier message: 09/06/2011, 16h25
  3. Mapping de <set>
    Par Maxime Dupaul dans le forum Hibernate
    Réponses: 4
    Dernier message: 19/05/2011, 11h58
  4. Mapping collection <set>
    Par myrmidia dans le forum Hibernate
    Réponses: 5
    Dernier message: 14/08/2008, 14h20
  5. Relation Parent/Fils - Mapping et Set
    Par --cycy dans le forum Hibernate
    Réponses: 1
    Dernier message: 17/09/2007, 18h52

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo