recherche rapide d'identifiant ?

Le
MGN
Bonne année et meilleurs voeux à tous.
Ma question : comment faites-vous pour déterminer rapidement si un
identifiant (type int par exemple) fait partie d'un ensemble donné ?
Pour ma part, je fais une map X static du type map<int,bool> et j'enregistre
dedans les id.
Ensuite je fais juste un X.find(id)!=X.end() pour savoir si un id fait
partie de l'ensemble défini.
Mais les bool sont parfaitement inutiles
Y-a-t-il (sûrement) une meilleure solution ?
Merci à vous.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
MGN
Le #20871131
> Y-a-t-il (sûrement) une meilleure solution ?
Merci à vous.


sans doute les std::set ?
Michael Doubez
Le #20891441
On 1 jan, 13:34, "MGN"
Bonne année et meilleurs voeux à tous.
Ma question : comment faites-vous pour déterminer rapidement si un
identifiant (type int par exemple) fait partie d'un ensemble donné ?
Pour ma part, je fais une map X static du type map<int,bool> et j'enregis tre
dedans les id.
Ensuite je fais juste un X.find(id)!=X.end() pour savoir si un id fait
partie de l'ensemble défini.
Mais les bool sont parfaitement inutiles...
Y-a-t-il (sûrement) une meilleure solution ?



Il y a toujours bitset où vector<bool> si le numéro d'identifiant
supérieur est pas trop grand.

--
Michael
Stan
Le #20893221
On 1 jan, 13:34, "MGN"
Bonne année et meilleurs voeux à tous.
Ma question : comment faites-vous pour déterminer rapidement si un
identifiant (type int par exemple) fait partie d'un ensemble donné ?
Pour ma part, je fais une map X static du type map<int,bool> et j'enregis tre
dedans les id.
Ensuite je fais juste un X.find(id)!=X.end() pour savoir si un id fait
partie de l'ensemble défini.
Mais les bool sont parfaitement inutiles...
Y-a-t-il (sûrement) une meilleure solution ?
Merci à vous.



Que faites vous de l'identifiant par la suite ?
Si c'est pour accéder à un objet, pourquoi, dans ce cas,
ne pas placer un pointeur de ce dernier dans la map à la place du
bool ?


--
-Stan
Mickaël Wolff
Le #20895281
Michael Doubez a écrit :

Il y a toujours bitset où vector<bool> si le numéro d'identifiant
supérieur est pas trop grand.



std::vector
--
Mickaël Wolff aka Lupus Michaelis
http://lupusmic.org
Mickaël Wolff
Le #20895471
MGN a écrit :
Bonne année et meilleurs voeux à tous.
Ma question : comment faites-vous pour déterminer rapidement si un
identifiant (type int par exemple) fait partie d'un ensemble donné ?
Pour ma part, je fais une map X static du type map<int,bool> et
j'enregistre dedans les id.
Ensuite je fais juste un X.find(id)!=X.end() pour savoir si un id fait
partie de l'ensemble défini.
Mais les bool sont parfaitement inutiles...
Y-a-t-il (sûrement) une meilleure solution ?



Tu devrais rester simple.

// On pourrait généraliser
bool is_in(std::vector<int> const & container, int presumed)
{
return identifiers.end() != std::find_if(identifiers.begin(),
identifiers.end(), std::bind2nd(std::equal<int>(), presumed)) ;

}


int main()
{
std::vector<int> identifiers ;
identifiers.push_back(10) ;
/* some pushes */

if(is_in(identifiers, 10))
/* On a trouvé */ ;
}

--
Mickaël Wolff aka Lupus Michaelis
http://lupusmic.org
Fabien LE LEZ
Le #20895891
On Mon, 04 Jan 2010 20:32:23 +0100, Mickaël Wolff

std::vector<bool> n'est pas standard



Si. Il fonctionne même parfaitement bien.
En revanche, il n'est pas considéré comme un conteneur standard.
MGN
Le #20896211
> // On pourrait généraliser
bool is_in(std::vector<int> const & container, int presumed)
{
return identifiers.end() != std::find_if(identifiers.begin(),
identifiers.end(), std::bind2nd(std::equal<int>(), presumed)) ;

}


int main()
{
std::vector<int> identifiers ;
identifiers.push_back(10) ;
/* some pushes */

if(is_in(identifiers, 10))
/* On a trouvé */ ;
}



la performance est importante dans mon cas, c'est pourquoi je me disais
qu'une recherche dans un conteneur ordonné (comme un set) serait plus rapide
Peut-être que le mieux est que je teste tout ça :-)
Merci de ta réponse
MGN
Le #20896441
non, je veux juste savoir si un id fait partie d'un ensemble. Il n'y a pas
de problème de pointeur...
Fabien LE LEZ
Le #20896601
On Mon, 4 Jan 2010 22:17:23 +0100, "MGN"
la performance est importante dans mon cas, c'est pourquoi je me disais
qu'une recherche dans un conteneur ordonné (comme un set) serait plus rapide



La recherche dans un std::set<> est effectivement plus rapide. Remplir
ce std::set<> au départ peut, en revanche, prendre un peu de temps.

Mais, plus important, le conteneur "naturel" pour ce que tu veux faire
est bien std::set<>. L'utiliser ne peut qu'améliorer la lisibilité de
ton code.
Michael Doubez
Le #20900711
On 4 jan, 21:50, Fabien LE LEZ
On Mon, 04 Jan 2010 20:32:23 +0100, Mickaël Wolff

>std::vector<bool> n'est pas standard

Si. Il fonctionne même parfaitement bien.
En revanche, il n'est pas considéré comme un conteneur standard.



C'est un conteneur standard dans le sens ou il est dans le standard (C+
+98): §23.2.5. Autant que je vois, il a la sémantique d'un container
standard, bien que sa représentation interne ne soit pas conforme (et
même dangereuse en multithreadé).

Ce qui pose réellement problème, c'est dans les templates, il faut à
chaque fois le traiter comme un cas particulier parcequ'il retourne un
proxy (comme mentionner dans le lien Gotw).

Mais pour un cas comme ici, il peut être utile.

--
Michael
Publicité
Poster une réponse
Anonyme