souci fonction set_intersection

Bonjour,

je tente d'utiliser la fonction set_intersection afin de trouver des numeros communs entre deux vector<int>

Code:

---

1 2	itRet=set_intersection (cheminTemp->Path.begin(), cheminTemp->Path.end(), cheminTemp->Suiv->Path.begin(), cheminTemp->Suiv->Path.end(), v.begin());

---

Path sont des vector<int>

dans path j'ai successivement:
9 12 15
9 12
18 21 20
18 20

A la premiere itération,
il compare [9 12 15] et [9 12]: me trouve bien 9 et 12 en commun
ensuite
il compare [9 12 ] et [18 21 20]: me trouve bien aucun
ensuite
il compare [18 21 20 et [18 20]: me trouve seulement 18 en commun!

j'ai tenté de rajouter un numero 0 afin d'avoir les meme tailles mais ca ne fonctionne pas avec [18 21 20 et [18 20 0]

Si quelqu'un voit d'ou vient le problème je suis tout ouïe!

Merci

Citation:

---

Envoyé par loicounet

il compare [18 21 20 et [18 20]: me trouve seulement 18 en commun!

---

Normal, il faut que les deux séquences soient ordonnées pour pouvoir utiliser la fonction set_intersection.

ah ok!
je n'avais pas lu cette condition!

je rajoute donc un

Code:

---

sort(cheminTemp->path.begin(), cheminTemp->path.end());

---

Salut,

Un petit conseil en passant: Autant que faire se peut, il est préférable d'utiliser les fonctions propres du conteneur que tu manipule plutôt que les fonctions libres génériques...

En effet, le tri d'un vecteur peut utiliser des algorithmes plus intéressants, parce que de complexité moindre (utilisant la dichotomie, par exemple) qu'un tri générique (souvent le tri "à bulles") et, sauf erreur de ma part, tu dispose d'une fonction membre sort dans std::vector ;)

Le résultat sera identique, car il n'y a pas de raison qu'une méthode de tri fournisse un résultat différent d'une autre, mais le temps mis pour l'effectuer peut varier énormément, surtout sur des nombres d'objets important (allant d'une complexité en N*log(n) à une complexité en N^2)

Citation:

---

En effet, le tri d'un vecteur peut utiliser des algorithmes plus intéressants, parce que de complexité moindre (utilisant la dichotomie, par exemple) qu'un tri générique (souvent le tri "à bulles") et, sauf erreur de ma part, tu dispose d'une fonction membre sort dans std::vector

---

Alors je dirais que, pour une fois, tu es pris en flagrant délit d'erreur :). Il n'y a pas de fonction sort dans std::vector.

Pas besoin, car std::sort travaille avec des "random access containers", et que vector en est un très bon exemple.

D'ailleurs, std::sort est en général un quicksort ou mieux, de complexité O(n*log n) dans le cas général. Donc, tu as tout lieu de l'utiliser sur un vector (mais surtout pas sur un std::list, qui lui a sa fonction membre sort ;) ).

Citation:

---

Envoyé par white_tentacle

Alors je dirais que, pour une fois, tu es pris en flagrant délit d'erreur :). Il n'y a pas de fonction sort dans std::vector.

Pas besoin, car std::sort travaille avec des "random access containers", et que vector en est un très bon exemple.

---

Je n'ai jamais prétendu être infaillible non plus;)

Citation:

---

D'ailleurs, std::sort est en général un quicksort ou mieux, de complexité O(n*log n) dans le cas général. Donc, tu as tout lieu de l'utiliser sur un vector (mais surtout pas sur un std::list, qui lui a sa fonction membre sort ;) ).

---

Parce que, justement, les listes ne sont absolument pas adaptées à une quelconque dichotomie ni aux accès aléatoires (obligation d'accès séquentiels)...

La dichotomie peut être utilisées soit en acces aléatoire soit sur des structures en forme d'arbres binaires (typiquement les map, set, multimap et multiset) ;)

Mais, quoi qu'il en soit, si une collection propose une fonction membre de tri, c'est généralement celle qu'il vaut mieux préférer ;)