Test de l'existence d'un élément dans un set

Version imprimable

26/10/2006, 15h31
Rodrigue

Test de l'existence d'un élément dans un set

Bonjour,

Comment savoir le plus rapidement possible si un élément existe déjà dans un std::set?

Je vous remercie par avance.
Cordialement,
Rodrigue

Code:

1
2
3
4
5
6
7
8
9
10
11
 
std::set<T> monSet;
T elementATrouver;
if(monSet.find(elementATrouver)!=monSet.end())
{
    // l'element est dedans
}
else // monSet.find(elementATrouver)==monSet.end()
{
    // l'element n'est pas dedans
}

26/10/2006, 15h45
Rodrigue

Merci! Je pensais à la même chose. Que penses-tu du fait d'utiliser un hash_set plutôt qu'un set?
http://www.sgi.com/tech/stl/hash_set.html
26/10/2006, 15h49
Matthieu Brucher

Comme ce n'est pas un conteneur standard, tu n'es pas sûr de l'avoir partout :|
26/10/2006, 15h52
roulious

Pareil que Miles, plus le fait que je n'ai jamais eu de problèmes de performance avec des set, même contenant plusieurs millions d'éléments (dans mon cas, un ensemble de voxels d'un objet 3D).
26/10/2006, 15h54
Rodrigue

Ok! Merci beaucoup pour toutes ses infos :D

Roulious tu travailles sur quel type d'application? Pour ma part, je m'amuse sur des calculs de radiosité... Mais au-delà d'un certains nombres d'éléments c'est impossible d'inverser cette satanée matrice ;). J'utilise Gauss-Seidel pour le moment, peut-être qu'il faudrait que je me tourne la technique de relaxation...
26/10/2006, 15h55
Matthieu Brucher

Pourquoi ne pas faire une pseudo inverse ?
26/10/2006, 15h58
Rodrigue

A vrai dire je ne suis pas capable de te répondre comme ça, il faudrait que cette méthode. Je dois inverser des matrices 10000x10000, est-ce que c'est capable de faire ça en un temps raisonnable?
26/10/2006, 16h04
Matthieu Brucher

En fait, uen pseudo inverse, c'est tu prends une diagonalisation de la matrice, tu inverses les vp pas trop petites et tu remultiplies.
26/10/2006, 18h53
Rodrigue

Je pense que Gauss Seidel ainsi que la méthode de relaxation sont bien plus rapides. Il s'agit d'algo itératif...
27/10/2006, 00h38
Luc Hermitte

std::set<>::count()
27/10/2006, 09h26
Rodrigue

Hein :P ?
27/10/2006, 09h31
Matthieu Brucher

count retourne le nombre d'éléments répondant favorablement à la question posée.
27/10/2006, 09h45
Luc Hermitte

Et pour un set -> 1 ou 0. Plus simple à utiliser qu'un find. find qui sera à privilégier (p/r à count) sur les multi_set.
27/10/2006, 19h04
Rodrigue

Ok, d'accord je vais essayer ça ce week-end.
27/10/2006, 19h09
roulious
Juste par curiosité : en regardant ce que fait la libstdc++ pour set::count, on s'aperçoit que c'est juste un wrapper autour de find :
Code:

1 2 3 4 size_type count(const key_type& __x) const { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
28/10/2006, 01h36
Luc Hermitte

Oui tout à fait. Et c'est probablement la même chose pour les autres implémentation. C'est juste pour simplifier l'écriture.