Utilisation de la méthode static vs. member find sur un ensemble STL?

Question

J'utilise un ensemble parce que je souhaite utiliser la propriété de recherche rapide d'un conteneur trié tel qu'un ensemble. Je me demande si je dois utiliser la méthode find member pour bénéficier d'un conteneur trié, ou puis-je également utiliser la méthode find statique dans les algorithmes STL?

Mon impression est que l'utilisation de la version statique utilisera une recherche linéaire au lieu d'une recherche binaire comme je le souhaite.

Answer 1

Vous avez raison de dire que la version non membre effectue une recherche linéaire, tandis que la version du membre fera une recherche O (log N). std :: set est optimisé pour l'insertion, la récupération et la suppression de O (journal N).

En tant que point de définition, la méthode std :: find n'est pas une fonction statique. Voir ici pour une description de les différentes choses statiques peuvent signifier en C ++.

Answer 2

Cela dépend de l'implémentation, car quelqu'un pourrait avoir implémenté une spécialisation partielle pour la "recherche" statique qui utilise une recherche binaire sur les ensembles, mais tout bien considéré, la version de la fonction membre aura de meilleures performances.

IIRC, Scott Meyers suggère dans son livre "Effective STL" de toujours préférer la version de membre aux fonctions communes telles que rechercher, échanger, etc. sur les fonctions non membres simplement parce qu'elles ont plus de chances d'être une implémentation optimale -member versions et , vous pouvez normalement vous fier aux avantages de la version membre en termes de performances, alors que vous ne pouvez pas toujours compter sur le fait qu'une spécialisation partielle pour une fonction donnée sera présente.