échec d'insertion dans un std::set utilisant une fonction de comparaison, quel est le problème?

Version imprimable

Voir 40 message(s) de cette discussion en une page

bonjour,
j'utilise un set de pair d'unsigned int avec une function comparative sur le deuxième élément de ma pair.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <set> typedef unsigned short ushort; struct compPairBySecond { bool operator() (const std::pair<ushort,ushort>& lhs, const std::pair<ushort,ushort>& rhs) const {return lhs.second < rhs.second;} }; typedef std::set<std::pair<ushort,ushort> , compPairBySecond> mySet; int main(){ mySet set; for (int i=0; i<2 ; ++i){ auto res = set.insert(std::pair<ushort,ushort>(i,1)); cout << "Insertion result: " << res.second << "\n"; } for (auto it = set.cbegin(); it != set.cend(); ++it) cout << "(" << it->first << ", " << it->second << ")\n"; return 0; }
Pourquoi la deuxième insertion pair<1,1> ne marche pas?

Si je change ma fonction de comparaison pour utiliser un inférieur ou égal cela marche...
Je ne comprend pourquoi...
j'imaginais qu'avec < j'aurai en résultat le set suivant: { (0,1) , (1, 1) }
et avec un <= dans l'autre sens: { (1, 1), (0, 1) }

Pourquoi ça ne marche pas et ne puis je pas obtenir le premier cas?
Dans l'example sur sur cplusplus.com ils utilisent un inférieur strict... (http://www.cplusplus.com/reference/set/set/set/)

30/12/2015, 19h48
jo_link_noir

Si la comparaison se fait sur le second élément, la valeur du premier n'a aucune importance, donc {0,1} et {1,1} sont identique du point de vue du set. Et comme set ne garde qu'un ensemble unique, seule la dernière paire est présente.

http://cpp.developpez.com/faq/cpp/?p...l-operateur-lt
Simplifié avec std::tie: http://en.cppreference.com/w/cpp/utility/tuple/tie
30/12/2015, 20h10
Iradrille

Citation:

Envoyé par jo_link_noir

Simplifié avec std::tie: http://en.cppreference.com/w/cpp/utility/tuple/tie

Je connaissais pas, c'est pratique.

std::tie(a, b) est bien l'équivalent de std::make_tuple(std::ref(a), std::ref(b)); ?
30/12/2015, 20h47
ramislebob

Citation:

Envoyé par jo_link_noir

Si la comparaison se fait sur le second élément, la valeur du premier n'a aucune importance, donc {0,1} et {1,1} sont identique du point de vue du set. Et comme set ne garde qu'un ensemble unique, seule la dernière paire est présente.

http://cpp.developpez.com/faq/cpp/?p...l-operateur-lt
Simplifié avec std::tie: http://en.cppreference.com/w/cpp/utility/tuple/tie

Ok je vois, le test d'unicité est fait comme ça:

Citation:

Pour tout a et b, si a<b est faux et b<a est faux, on dit que a et b sont équivalents (cette relation doit être une relation d'équivalence, comme précisée dans la question sur l' opérateur==.

En utilisant un <= dans ma fonction de comparaison, les deux paires sont insérées dans le set mais dans l'ordre (1,1) (0,1). En gros je contourne un peu le problème d'uncité et en devient presque un multi set puisque à aucun éléments ne seront jamais égaux...

En terme de performance, qu'est il mieux? Utiliser un multi-set avec ma comparaison stricte ou bien un set avec un <=?
(J'utilise mon set de pair afin de trier une map par valeur, je sais donc que tous les éléments seront différents.)

Citation:

Envoyé par ramislebob

je ne comprends pas trop comment est fait le test d'égalité. Ma fonction de comparaison entre (0,1) et (1,1) renvoit false comme elle le ferait pour (0,1) et (0,2)... Quelle est la différence? En aucun cas je ne dit au set de ne considérer que la seconde valeur de ma paire pour vérifier l'unicité...
Citation:
Envoyé par ramislebob
Code:

1 2 3 4 5 6 struct compPairBySecond { bool operator() (const std::pair<ushort,ushort>& lhs, const std::pair<ushort,ushort>& rhs) const {return lhs.second < rhs.second;} // comparaison sur le second élément, on ignore complètement le premier. }; typedef std::set<std::pair<ushort,ushort> , compPairBySecond> mySet;
Citation:

Envoyé par ramislebob

Autre question: En utilisant un <= dans ma fonction de comparaison, les deux paires sont insérées dans le set mais dans l'ordre (1,1) (0,1). Est ce que cela veut dire que l'uncité du set est contournée et qu'il devient un multi-set? Ça me parait un peu louche...

Çà risque surtout de faire des trucs très bizarre
Code:

1 2 3 4 mySet set; set.insert(std::pair<ushort,ushort>(0, 1)); // set = [ {0,1} ] set.insert(std::pair<ushort,ushort>(1, 1)); // set = [ {0,1}, {1,1} ]; ordre dépendant de l'implémentation set.remove(std::pair<ushort,ushort>(2, 1)); // set = [ ] ou [ {0,1} ] ou [ {1,1} ] en fonction de l'implémentation
Citation:

Envoyé par ramislebob

(J'utilise mon set afin de trier une map par valeur. Je sais que tous les éléments sont donc différents)

Une map est triée, pourquoi utiliser un set ?
Et si tes éléments sont différents, comment tu peux te retrouver dans le cas [ {0,1}, {1,1} ] où tu as deux éléments identiques ?

Citation:
Envoyé par Iradrille
Çà risque surtout de faire des trucs très bizarre
Code:

1 2 3 4 mySet set; set.insert(std::pair<ushort,ushort>(0, 1)); // set = [ {0,1} ] set.insert(std::pair<ushort,ushort>(1, 1)); // set = [ {0,1}, {1,1} ]; ordre dépendant de l'implémentation set.remove(std::pair<ushort,ushort>(2, 1)); // set = [ ] ou [ {0,1} ] ou [ {1,1} ] en fonction de l'implémentation
Une map est triée, pourquoi utiliser un set ?
Et si tes éléments sont différents, comment tu peux te retrouver dans le cas [ {0,1}, {1,1} ] où tu as deux éléments identiques ?
mince, tu as répondu pendant que je modifiais mon post précédent car j'avais compris comment ce passait le test d'égalité (négation du test d'infériorité dans les deux sens)...

Je réponds quand même à la question que tu soulèves et explique mon utilisation de ce set de pair.
En fait j'ai une map triée par key. map: (k1, v1), (k2, v2) (k3, v3) ...
et j'ai besoin de l'avoir triée en fonction des valeurs.
dans la map les k1, k2, k3... sont uniques. Les valeurs elles peuvent être identiques.
j'utilise un set de pair pour obtenir (v2, k2) (v1, k1) (v3, k3) si v2 <= v1 <= v3

mais bon je pensais qu'en cas d'égalité des valeurs, la première insérée resterai avant l'autre...

J'en reviens à ma nouvelle question dans mon post précédent que j'ai modifié...
Qu'est il préférable en terme de performance?
un set avec ma comparaison <=
ou un multi-set avec comparaison <

Je suppose le multi-set? Dans ce cas j'obtiendrai bien mon (0, 1) (1, 1) et le test d'égalité (comparaison inverse) est évité

30/12/2015, 21h22
ramislebob

PS: ce set de paire est juste utilisé pour un parcours de ma map en ordre de valeur, il n'y aura aucune suppression.

Citation:

Envoyé par ramislebob

J'en reviens à ma nouvelle question dans mon post précédent que j'ai modifié...
Qu'est il préférable en terme de performance?
un set avec ma comparaison <=
ou un multi-set avec comparaison <

Je suppose le multi-set? Dans ce cas j'obtiendrai bien mon (0, 1) (1, 1) et le test d'égalité (comparaison inverse) est évité

Ok pour le set, ça à du sens.

la meilleure solution : soit ce que propose @jo_link_noir avec tie, soit la solution que tu avais dans ton post avant d'edit (basiquement c'est la même chose que tie, sauf que tu le fais à la main).
Code:

1 2 3 4 5 6 7 8 struct compPairBySecond { bool operator() (const std::pair<ushort,ushort>& lhs, const std::pair<ushort,ushort>& rhs) const { return std::tie(lhs.second, lhs.first) < std::tie(rhs.second, rhs.first); // ou return (lhs.second == rhs.second) ? (lhs.first < rhs.first): (lhs.second < rhs.second); } };
edit : un set avec '<=', c'est faux.

30/12/2015, 22h05
ramislebob

oui c'est clair qu'un set avec un <= ce n'est pas beau...
j'hésite quand même entre ta deuxième option

Code:

return (lhs.second == rhs.second) ? (lhs.first < rhs.first): (lhs.second < rhs.second);

ou bien utiliser un multi-set avec un simple <
Le résultat sera le même.
En terme de performance je suppose que le multiset est peut être plus adapté car il n'y a besoin de faire qu'une seule comparaison (le test d'uncité n'étant pas requis).
J'hésite... je crois que je vais prendre le multiset
30/12/2015, 22h11
ramislebob

Merci pour votre aide :)
30/12/2015, 22h29
Bousk

Citation:

Envoyé par ramislebob

PS: ce set de paire est juste utilisé pour un parcours de ma map en ordre de valeur, il n'y aura aucune suppression.

Mais une map c'est pas déjà triée ?!
Et ça possède des itérateurs pour le parcours. :weird:
30/12/2015, 22h56
ramislebob

Citation:

Envoyé par Bousk

Mais une map c'est pas déjà triée ?!
Et ça possède des itérateurs pour le parcours. :weird:

Si mais la map est triée par clefs.
Et j'ai besoin d'avoir un tri par valeurs. Ma méthode est donc d'utiliser un multiset de pair<key,val> ordonné par le second élément de la paire.
Y a t'il une meilleure méthode?
30/12/2015, 23h38
Bousk

Perso j'utiliserais un simple vector où je mets toutes les valeurs qui m'intéressent puis je les trie.
Je suis pas convaincu qu'un set soit top pour ça, le tri est réalisé à chaque insertion, avec autant de remaniement de la mémoire. Alors que reserve permettra de consommer exactement ce qui est nécessaire et le sort se fait "in place".
31/12/2015, 02h08
ramislebob

Citation:

Envoyé par Bousk

Perso j'utiliserais un simple vector où je mets toutes les valeurs qui m'intéressent puis je les trie.
Je suis pas convaincu qu'un set soit top pour ça, le tri est réalisé à chaque insertion, avec autant de remaniement de la mémoire. Alors que reserve permettra de consommer exactement ce qui est nécessaire et le sort se fait "in place".

Oui c'est vrai, dommage qu'il n'y ait pas de reserve pour un set...
Ma map n'a pas beaucoup d'éléments, pour l'instant qu'un ou deux et potentiellement pas plus d'une dizaine. Du coup le set est plus pratique. Je pense que vais rester sur cette option de multiset mais c'est clair que si j'avais plus d'éléments je passerais par un vector.
31/12/2015, 09h57
white_tentacle

Citation:

Envoyé par Bousk

Perso j'utiliserais un simple vector où je mets toutes les valeurs qui m'intéressent puis je les trie.
Je suis pas convaincu qu'un set soit top pour ça, le tri est réalisé à chaque insertion, avec autant de remaniement de la mémoire. Alors que reserve permettra de consommer exactement ce qui est nécessaire et le sort se fait "in place".

C’est même surtout ce qu’il faut faire. De manière générale, un set ne doit être utilisé que si tu ne maîtrises pas le moment où seront faites tes insertions, et que tu dois garantir que la collection est triée en toute circonstances. Dans pratiquement tous les autres cas, un vector trié « au moment approprié » sera meilleur aussi bien en terme d’utilisation mémoire que de performances.
31/12/2015, 10h18
stendhal666
Citation:

Envoyé par ramislebob

Oui c'est vrai, dommage qu'il n'y ait pas de reserve pour un set...
Ma map n'a pas beaucoup d'éléments, pour l'instant qu'un ou deux et potentiellement pas plus d'une dizaine. Du coup le set est plus pratique. Je pense que vais rester sur cette option de multiset mais c'est clair que si j'avais plus d'éléments je passerais par un vector.

La discussion est résolue et tu as certainement avancé dans ton programme mais si je peux me permettre un ou deux conseils:
- si tu reviens sur cette portion de ton code un peu plus tard et que tu vois un multiset, tu penseras en priorité qu'il peut y avoir deux éléments semblables, pas que tu as réussi à éliminer une comparaison;
- rechercher un élément dans un multiset est plus long que dans un set puisqu'il faut parcourir les éléments égaux le cas échéant;
- pour une dizaine d'éléments au maximum, deux situations: 1) tu accèdes à ces éléments extrêmement fréquemment et tout le long de ton programme: alors trier est une option intéressante 2) tu y accèdes plus rarement ou seulement pendant une courte période de ton programme: tu peux laisser les données non triées, un find tout bête dans la map d'origine prendrait n/2 en moyenne (où n est le nombre d'éléments, voire moins selon les propriétés des paires); trouver dans un multiset prend lg n + (s/2) où s est le nombre d'éléments égaux mais il faut y ajouter la constitution du multiset;
- l'allocation de mémoire pour le contenu d'un vecteur de petite taille peut être fait sur la pile, je ne crois pas que ce soit le cas pour un set: cela pourrait militer pour la solution du vector
En bref, éviter une comparaison ne justifie à mon avis presque jamais une perte de précision sémantique et une recherche pas toujours un tri.
31/12/2015, 16h19
ramislebob
Citation:
Envoyé par stendhal666

La discussion est résolue et tu as certainement avancé dans ton programme mais si je peux me permettre un ou deux conseils:

si tu reviens sur cette portion de ton code un peu plus tard et que tu vois un multiset, tu penseras en priorité qu'il peut y avoir deux éléments semblables, pas que tu as réussi à éliminer une comparaison;
rechercher un élément dans un multiset est plus long que dans un set puisqu'il faut parcourir les éléments égaux le cas échéant;
pour une dizaine d'éléments au maximum, deux situations: 1) tu accèdes à ces éléments extrêmement fréquemment et tout le long de ton programme: alors trier est une option intéressante 2) tu y accèdes plus rarement ou seulement pendant une courte période de ton programme: tu peux laisser les données non triées, un find tout bête dans la map d'origine prendrait n/2 en moyenne (où n est le nombre d'éléments, voire moins selon les propriétés des paires); trouver dans un multiset prend lg n + (s/2) où s est le nombre d'éléments égaux mais il faut y ajouter la constitution du multiset;
l'allocation de mémoire pour le contenu d'un vecteur de petite taille peut être fait sur la pile, je ne crois pas que ce soit le cas pour un set: cela pourrait militer pour la solution du vector

En bref, éviter une comparaison ne justifie à mon avis presque jamais une perte de précision sémantique et une recherche pas toujours un tri.
Concrètement j'ai juste besoin de parcourir ma map par valeur. Pas de find, pas d'insert, pas de remove. J'ai n'ai pas non plus besoin de le faire souvent, ça reste très ponctuel.
C'est pour cela que j'avais pensé utiliser un set (puis multi-set) mais le fait de garder le vector sur la pile m'a fait changer d'idée. Il est clair que c'est plus propre et plus performant.
Et puis ce n'est pas grand chose à changer, je vais faire ça de suite.

Merci pour vos avis et bon réveillon à tous! :)
31/12/2015, 18h13
jo_link_noir

Citation:

Envoyé par Iradrille

Je connaissais pas, c'est pratique.

std::tie(a, b) est bien l'équivalent de std::make_tuple(std::ref(a), std::ref(b)); ?

Oui, cela crée une tuple contenant des références.
Je trouve dommage qu'il n'y ai pas d'objet pour optimiser les comparaisons en utilisant une fonction compare (qui retourne -1,0,1) au lieu de a<b puis a==b. Avec des séquences, cela a son importance (std::string par exemple),

Citation:

le fait de garder le vector sur la pile m'a fait changer d'idée. Il est clair que c'est plus propre et plus performant.

Un vector sur la pile n'est pas quelque chose de trivial. Il faut être sur que la taille de la pile est assez grande. Pour donner un peu de piquant, la taille réservée par le vector est dépendant de l'implémentation de celui-ci. Mais ce n'est pas grave, on peut lui mentir et fourni une zone mémoire pouvant contenir tous les éléments qu'on va y mettre, mais plus petite que la taille demandée. Si on ne l'utilise pas, ce n'est pas grave, c'est juste sale.
Cela dit, std::dynarray ne dépend pas de l'implémentation. Reste à connaître la taille max de la pile et faire un allocateur dédié. Bah oui, par défaut, les containers vont piocher dans le tas.

Tous ça pour dire que si c'est l'argument d'une allocation sur pile qui te fait changer d'avis, c'est une mauvaise raison. Perso, j'aurais choisi la continuité en mémoire des valeurs (donc accès rapide) et l'allocation unique si on utilise les fonctions faites pour (assign/constructeur avec itérateur). Par contre, il faut ajouter la ligne pour trier et celle pour réduire (std::unique ou un filter_iterateur (doit y avoir cela dans boost)).

Citation:

Envoyé par jo_link_noir

Tous ça pour dire que si c'est l'argument d'une allocation sur pile qui te fait changer d'avis, c'est une mauvaise raison. Perso, j'aurais choisi la continuité en mémoire des valeurs (donc accès rapide) et l'allocation unique si on utilise les fonctions faites pour (assign/constructeur avec itérateur). Par contre, il faut ajouter la ligne pour trier et celle pour réduire (std::unique ou un filter_iterateur (doit y avoir cela dans boost)).

Hum... une question, en quoi est ce plus rapide de parcourir une mémoire continue plutôt qu'une linked list? Le temps d'accès random oui, c'est clair, mais si je veux juste parcourir ma liste/array/vector c'est pareil non? Dans les deux cas on connait l'adresse mémoire du prochain élément...
En quoi cette opération:
Code:

1 2 3 4 std::vector<std::pair<int,int> > myVect = getMyVectorOrderedByValue(); for (auto it = myVect.cbegin(); it != myVect.cend(); ++it) cout << "(" << it->first << ", " << it->second << ")\n";
est elle plus rapide qu'avec un set?
Code:

1 2 3 4 std::set<std::pair<int,int> > mySet = getMySetOrderedByValue(); for (auto it = set.cbegin(); it != set.cend(); ++it) cout << "(" << it->first << ", " << it->second << ")\n";
Autre question, je n'arrive pas à trouvé explicitement que lorsque j'utilise un vecteur avec une taille réservée, l'allocation est faite sur la pile.
Si je fais ceci:

Code:

std::vector<std::pair<int,int>> myVect(getMapSize());

Que ce passe-t'il? Comme la taille n'est pas statique, j'ai tendance à penser que ça partira dans la heap... (comment on dit heap en français?)
Si j'ai bien compris tous les éléments sont initialisés avec le constructeur par défault? Est ce vrai?

Si je ne donne pas la taille initiale du vecteur dans le constructeur comme si dessus mais utilise reserve
Code:

1 2 3 std::vector<std::pair<int,int>> myVect; myVect.reserve(getMapSize());
C'est forcément alloué dans la heap non? Si j'ai bien compris la taille du vecteur sera de 0. Donc la mémoire n'est pas initialisé si?

Allez dernière question, que vaut il mieux privilégier:
Code:

1 2 3 4 5 6 std::map<int,int> myMap = getMap(); std::vector<std::pair<int,int>> myVect; myVect.reserve(getMapSize()); for (auto it = myMap.cbegin(); it != myMap.cend(); ++it) myVect.push_back(std::pair<ushort, ushort>(it->first, it->second));
ou
Code:

1 2 3 4 5 6 std::map<int,int> myMap = getMap(); std::vector<std::pair<int,int>> myVect(getMapSize()); int i=0; for (auto it = myMap.cbegin(); it != myMap.cend(); ++it) myVect[i++] = std::pair<ushort, ushort>(it->first, it->second);
Est ce équivalent? Personnellement ayant des gros doutes sur le fait que le vector serait sur la pile en utilisant le constructeur avec la taille dynamique je pencherai plus pour la première option et le réserve car je suppose que le bloc de mémoire global est réservé sans initialiser chaque élément avec le constructeur par défault de ma pair<int, int>. Est ce correct?

Bonne année tout le monde!

Citation:

Envoyé par ramislebob

Hum... une question, en quoi est ce plus rapide de parcourir une mémoire continue plutôt qu'une linked list? Le temps d'accès random oui, c'est clair, mais si je veux juste parcourir ma liste/array/vector c'est pareil non?

Justement non, list/map/set fragmentent la mémoire car chaque élément est alloué indépendamment. Cela augmente le risque de cachemiss et le nombre de déréférencement. De plus, le compilateur ne peut pas faire convenablement certaines optimisations (ex: préchargement de la mémoire).

Citation:

Envoyé par ramislebob

Autre question, je n'arrive pas à trouvé explicitement que lorsque j'utilise un vecteur avec une taille réservée, l'allocation est faite sur la pile.

Normal, l'allocation est faîte sur le tas (heap). À moins de définir un allocateur perso (second paramètre template du vector) le comportement par défaut est d'utiliser ::operator new.

Citation:

Envoyé par ramislebob

Si je fais ceci:

Code:

std::vector<std::pair<int,int>> myVect(getMapSize());

Si j'ai bien compris tous les éléments sont initialisés avec le constructeur par défault? Est ce vrai?

Oui depuis c++11. Avant, c'est une copie d'un paramètre construit avec le constructeur par défaut si non fournit. Mais il existe un constructeur prenant des iterateurs qui permettent d'initialiser les valeurs sans passer par le constructeur par défaut.
Citation:
Envoyé par ramislebob
Si je ne donne pas la taille initiale du vecteur dans le constructeur comme si dessus mais utilise reserve
Code:

1 2 3 std::vector<std::pair<int,int>> myVect; myVect.reserve(getMapSize());
[...] Si j'ai bien compris la taille du vecteur sera de 0. Donc la mémoire n'est pas initialisé si?
C'est bien cela. Mais il faut savoir que push_back contient un test conditionnel qui casse le pipeline et ralentit le programme quand le compilateur ne fait pas bien les optimisations (et cela arrive).
Citation:
Envoyé par ramislebob
Allez dernière question, que vaut il mieux privilégier:
Code:

1 2 3 4 5 6 std::map<int,int> myMap = getMap(); std::vector<std::pair<int,int>> myVect; myVect.reserve(getMapSize()); for (auto it = myMap.cbegin(); it != myMap.cend(); ++it) myVect.push_back(std::pair<ushort, ushort>(it->first, it->second));
ou
Code:

1 2 3 4 5 6 std::map<int,int> myMap = getMap(); std::vector<std::pair<int,int>> myVect(getMapSize()); int i=0; for (auto it = myMap.cbegin(); it != myMap.cend(); ++it) myVect[i++] = std::pair<ushort, ushort>(it->first, it->second);
Est ce équivalent? Personnellement ayant des gros doutes sur le fait que le vector serait sur la pile en utilisant le constructeur avec la taille dynamique je pencherai plus pour la première option et le réserve car je suppose que le bloc de mémoire global est réservé sans initialiser chaque élément avec le constructeur par défault de ma pair<int, int>. Est ce correct?
Entre les deux, je préfère la seconde solution pour la raison évoquée plus haut concernant push_back. Et aussi parce que l'initialisation d'une pair de short est 'rapide'.

D'ailleurs, en utilisant une structure intermédiaire, il est possible de ne rien initialiser:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 template<class T> struct uninitialized_storage { uninitialized_storage() {} // constructeur qui n'initialise pas la valeur operator T & () { return x; } operator T const & () const { return x; } private: T x; }; int x1; //non initialisé int x2{}; //initialisé à 0 uninitialized_storage<int> x3; //non initialisé uninitialized_storage<int> x4{}; //non initialisé using uninitialized_ushort = uninitialized_storage<ushort>; std::vector<std::pair<uninitialized_ushort, uninitialized_ushort>> v(3); // les valeurs ne sont pas initialisées
(C'est dans ces moments-là que vector manque d'une fonction d'initialisation externe du style assign(size_t, RawInitializer, RawCopy).)

Sinon, la forme la plus simple est:
Code:

1 2 3 std::map<int,int> myMap = getMap(); std::vector<std::pair<int,int>> myVect(myMap.begin(), myMap.end());
Cependant, comme les itérateurs du map sont bidirectionnel, la complexité de std::distance utilisé par le vecteur est de O(n). Un gros hack consiste à wrapper l'itérateur du map dans un itérateur taggué random_access_iterator_tag pour que std::distance(first, last) retourne last-first et que la soustraction retourne myMap.size() (:aie:).

Bonne année !

Voir 40 message(s) de cette discussion en une page