recherche rapide d'identifiant ?
MGN
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.
MGN
> Merci � vous.
Michael Doubez
> 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
> Mais les bool sont parfaitement inutiles...
Il y a toujours bitset où vector<bool> si le numéro d'identifiant
supérieur est pas trop grand.
--
Michael
Stan
> 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
> Mais les bool sont parfaitement inutiles...
> 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
> Il y a toujours bitset o� vector<bool> si le num�ro d'identifiant
> sup�rieur est pas trop grand.
std::vector<bool> n'est pas standard <http://www.gotw.ca/gotw/050.htm>
--
Micka�l Wolff aka Lupus Michaelis
http://lupusmic.org
Mickaël Wolff
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� */ ;
Fabien LE LEZ
<mickae...@laposte.net>:
>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
> // 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
de probl�me de pointeur...
Fabien LE LEZ
>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
> On Mon, 04 Jan 2010 20:32:23 +0100, Mickaël Wolff
> <mickael.wo...@laposte.net>:
>
> >std::vector<bool> n'est pas standard
>
> 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
Michael Doubez
[snip]
> 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 :-)
Il y a aussi le unordered_set (aka hash_set) qui te donnerait un test
en temps constant.
Tout dépend en fait du nombre d'entier possible et leur répartition.
--
Michael
Mickaël Wolff
> Mais pour un cas comme ici, il peut �tre utile.
Bon, d�sol� les gars, j'ai jet� le b�b� avec l'eau du bain :D
Mickaël Wolff
> 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
En fait, ce que je ne comprenais pas, c'�tait pourquoi tu voulais
absolument avoir une cl� pour acc�der � l'entier. Mais si std::set
convient mieux que std::vector, alors je ne vois pas le probl�me. Comme
dis, c'�tait juste pour proposer quelque chose de plus basique que ce �
quoi tu pensais (pour une fois que je pense simple, j'en profite).
Fabien LE LEZ
<mickae...@laposte.net>:
> Tu devrais rester simple.
Toi aussi :
>// 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)) ;
return identifiers.end() !=
std::find (identifiers.begin(), identifiers.end(), presumed);
Mickaël Wolff
> On Mon, 04 Jan 2010 20:58:33 +0100, Micka�l Wolff
> <mickae...@laposte.net>:
>
>> Tu devrais rester simple.
>
> Toi aussi :
Certes :D