vector recerche d'occurence
vector recerche d'occurence - C++ - Programmation
Marsh Posté le 03-11-2004 à 13:03:22
ça c'est pas une occurence, c'est de l'inclusion. tourne toi vers les std::set et std::multiset.
sinon, y a pas de solution miracle, tu prends chaque élément et tu regardes s'il est dans l'autre
Message édité par Taz le 03-11-2004 à 13:06:20
Marsh Posté le 03-11-2004 à 15:18:37
Reply
Marsh Posté le 03-11-2004 à 16:41:39
Puis je me souviens avoir ici même proposé ce problème et trouvé une solution efficace via une grosse hash_map. Qq d'autre avait proposé une solution encore plus efficace via un arbre AVL.
Marsh Posté le 03-11-2004 à 16:48:26
| el muchacho a écrit : Qq d'autre avait proposé une solution encore plus efficace via un arbre AVL. |
et std::set c'est du flanc ?
Marsh Posté le 03-11-2004 à 17:03:48
| Taz a écrit :
|
En fait, j'ai retrouvé la filière et cela concernait la recherche de doublons, ce qui n'est pas tout-à-fait le même problème qu'ici (même s'ls sont apparentés).
Message édité par el muchacho le 03-11-2004 à 17:05:23
Marsh Posté le 03-11-2004 à 17:17:17
faut voir. la solution brute, si je ne m'abuse c'est en (n/2)^2
Marsh Posté le 05-11-2004 à 16:57:16
| Taz a écrit : faut voir. la solution brute, si je ne m'abuse c'est en (n/2)^2 |
Oui, un truc comme ça. Moi j'avais une solution en O(n ln n) raisonnablement rapide eu égard à la simplicité de l'implémentation, et un autre (avec un arbre AVL) encore bien plus rapide. std::set, c'est quoi la structure de données qui se cache dessous ?
(recherche "recherche de doublons" )
Message édité par el muchacho le 05-11-2004 à 16:58:05
Marsh Posté le 05-11-2004 à 17:01:13
avec un arbre AVL/RB ok. mais le prix, tu le paies lors des autres opérations en maintenant l'ordre.
Sujets relatifs:
- Classe Vector: différence entre at() et [ ] ?
- Initialisation d'un vector
- [JAVA] Vector et différentes classes
- [c++] Conversion vector<T> en T*
- Problème avec la classe vector
- Probleme vector
- Pointeur sur un élément d'un std::vector
- JTABLE(vector,vector)
- [STL] pb vector de structure contenant des tableaux
- [JAVA ]utilisation de la classe Vector
Marsh Posté le 03-11-2004 à 13:00:08
existe t'il un moyen simple sans tout refaire a la main
pour trouver si un vector est contenus dans un autre vector ?