C++ récipient pour vérifier si les données commandé se trouve dans une collection

Question

j'ai données est un ensemble d'entiers ordonnés

[0] = 12345 [1] = 12346 [2] = 12454 etc.

J'ai besoin de vérifier si une valeur est dans la collection en C++, quel conteneur aura la plus faible complexité lors de la récupération? Dans ce cas, les données ne se développent pas après l'initiation. En C#, j'utiliserais un dictionnaire, en C++, je pourrais utiliser un hash_map ou un ensemble. Si les données n'étaient pas ordonnées, j'utiliserais les collections non ordonnées de boost. Cependant, ai-je de meilleures options puisque les données sont commandées? Merci

EDIT: La taille de la collection est deux cents articles

Answer 1

Juste pour détailler un peu ce qui a déjà été dit.

Classé Conteneurs

Le immuabilité est extrêmement important ici: std::map et std::set sont généralement mis en œuvre en termes d'arbres binaires (arbres rouge-noir pour mes quelques versions du STL) en raison des exigences relatives à l'insertion, opération d'extraction et de suppression (et notamment en raison de l'invalidation des exigences de l'itérateur). Cependant, en raison de l'immutabilité, comme vous le soupçonniez, il y a d'autres candidats, pas les moindres d'entre eux étant des récipients semblables à des matrices.Ils ont ici quelques avantages:

• minimum de frais généraux (en terme de mémoire)
• contiguïté de la mémoire, et donc localité cache

Plusieurs "Random Access conteneurs" sont disponibles ici:

• Boost.Array
• std::vector
• std::deque

La seule chose que vous devez vraiment faire peut être rompu fait en 2 étapes:

• pousser toutes vos valeurs dans le récipient de votre choix, puis (après tout ont été insérées) utilisez std::sort dessus.
• recherche de la valeur à l'aide std::binary_search, qui a O (log (n)) complexité

En raison de la localité de cache, la recherche sera en fait plus rapide, même si le comportement asymptotique est similaire.

Si vous ne voulez pas réinventer la roue, vous pouvez également consulter les [AssocVector][1] d'Alexandrescu. Alexandrescu essentiellement porté les std::set et std::map interfaces sur une std::vector:

• parce qu'il est plus rapide pour les petits ensembles de données
• car il peut être plus rapide pour les jeux de données congelés

Unsorted conteneurs

En fait, , si vous ne vous souciez vraiment pas de votre commande et que votre collection est assez grande, alors un unordered_set sera plus rapide, surtout parce que les nombres entiers sont si triviaux à hash size_t hash_method(int i) { return i; }. Cela pourrait très bien fonctionner ... à moins que vous ne soyez confronté à une collection qui provoque de nombreuses collisions, car alors les conteneurs non triés vont chercher dans la liste des "collisions" d'un hachage donné en temps linéaire.

Conclusion

Juste essayer l'approche std::vector et triés l'approche boost::unordered_set avec un ensemble de données « réel » (et toutes les optimisations sur) et prenez celui que vous donne le meilleur résultat.

Malheureusement nous ne pouvons pas vraiment aider plus là, parce que cela dépend fortement de la taille de l'ensemble de données et la répartition de ses éléments

Answer 2

Utilisez un sort ed std::vector, et utiliser un std::binary_search pour le fouiller.

Vos autres options seraient un hash_map (pas dans le standard C++ encore mais il y a d'autres options, par exemple SGI's hash_map et boost::unordered_map), ou un std::map.

Si vous n'allez jamais ajouter à votre collection, un vecteur trié avec binary_search aura probablement de meilleures performances qu'une carte.

Answer 3

Je suggérerais d'utiliser un std :: vector <int> pour les stocker et un std :: binary_search ou std :: lower_bound pour les récupérer. Std :: unordered_set et std :: set ajoutent tous deux un surcoût significatif à la mémoire - et même si le unordered_set fournit une recherche O (1), la recherche binaire O (logn) le dépassera probablement étant donné que les données sont stockées contiguës (pas de pointeur suivant, moins de risque d'erreur de page, etc.) et vous n'avez pas besoin de calculer une fonction de hachage.

Answer 4

Si les données sont dans un conteneur d'accès aléatoire commandé (par exemple std::vector, std::deque, ou un simple tableau), puis std::binary_search trouvera si une valeur existe dans le temps logarithmique. Si vous avez besoin de trouver où c'est, utilisez std::lower_bound (également logarithmique).

Answer 5

Si vous avez déjà un tableau ordonné ou std::vector<int> ou d'un conteneur similaire de la données, vous pouvez simplement utiliser std::binary_search pour tester chaque valeur.Pas de temps d'installation, mais chaque sonde prendra l'heure O (log n), où n est le nombre d'entrées ordonnées que vous avez.

Alternativement, vous pouvez utiliser une sorte de hachage, tel que boost::unordered_set<int>. Cela nécessitera un certain temps de mise en place, et probablement plus d'espace, mais chaque sonde prendra O (1) fois en moyenne. (Pour un petit n, ce O (1) pourrait être plus grand que le précédent O (log n) Bien sûr, pour un petit n, le temps est négligeable quand même.)

Il est inutile de regarder quelque chose comme std::set ou std::map, puisque ceux-ci n'offrent aucun avantage par rapport à la recherche binaire, étant donné que la liste des nombres à correspondre ne changera pas après avoir été initialisée. Donc, les questions sont la valeur approximative de n, et combien de fois vous avez l'intention de sonder la table. Si vous n'allez pas vérifier plusieurs valeurs pour voir si elles sont dans les ints fournis, le temps d'installation est très important, et std::binary_search sur le conteneur trié est le chemin à parcourir. Si vous allez vérifier beaucoup de valeurs, cela peut valoir la peine de mettre en place une table de hachage. Si n est grand, la table de hachage sera plus rapide à explorer que la recherche binaire, et s'il y a beaucoup de sondes, c'est le coût principal. Par conséquent, si le nombre d'ints à comparer est raisonnablement petit ou si le nombre de valeurs de sonde est petit, faites la recherche binaire. Si le nombre d'ints est grand et que le nombre de sondes est important, utilisez la table de hachage.