6
quelle est l'alternative?pourquoi il n'y a pas de recherche de vecteur en C++
Devrais-je écrire par moi-même?
A
Répondre
41
Il est l'algorithme std::find(), qui effectue une recherche linéaire sur une plage de iterator, par exemple,
std::vector<int> v;
// Finds the first element in the vector that has the value 42:
// If there is no such value, it == v.end()
std::vector<int>::const_iterator it = std::find(v.begin(), v.end(), 42);
Si votre vecteur est triée, vous pouvez utiliser std::binary_search() pour tester si une valeur est présente dans le vecteur, et std::equal_range() pour commencer et terminer les itérateurs à la plage d'éléments du vecteur qui ont cette valeur.
+3
L'avantage d'avoir 'std :: find' en tant que fonction libre est qu'il fonctionnera sur un tableau en mémoire, un' std :: vector', ou tout autre conteneur qui peut être traversé linéairement. – Thanatos
+0
Vous pourriez "multi-thread" si. –
+0
Vous ne constateriez qu'une amélioration constante du facteur. En outre, c'est hors de la portée de ce que fait 'std :: find'. (Une recherche multithread n'est pas nécessaire dans la plupart des situations.) Vous pourriez écrire un 'parallel_find()' qui fonctionnerait de manière très similaire, et fonctionnerait sur tous les conteneurs qui répondaient à un ensemble d'exigences (assez lâches). – Thanatos
4
Utilisez std::find(vec.begin(), vec.end(), value).
Et ne pas oublier de comprennent<algorithm>
8
Qui vous a dit cela? Il y a un algorithme "find" pour vector en C++. Ironiquement Par coïncidence, il est appelé std::find. Ou peut-être std::binary_search. Ou autre chose, selon les propriétés des données stockées dans votre vecteur.
Les conteneurs obtiennent leurs propres versions spécifiques d'algorithmes génériques (implémentés en tant que méthodes conteneur) uniquement lorsque l'implémentation effective de l'algorithme est en quelque sorte liée aux détails internes du conteneur. std::list<>::sort serait un exemple.
Dans tous les autres cas, les algorithmes sont implémentés par des fonctions autonomes.
+0
Désolé de nitpick, mais ce qui est si ironique à propos d'une fonction de recherche s'appelant "trouver"? – jalf
+0
@jalf: Je suppose que c'était prévu sarcastique ... soulignant que l'OP se plaint il n'y a pas de "trouver" quand il y a "trouver" et une recherche google pour "C++ trouver" renvoie le second résultat comme un lien vers ' std :: find' sur cplusplus.com – KevenK
+3
Donc, sarcastiquement appeler quelque chose d'ironique ... L'homme, c'est profond. ;) – jalf
21
La raison pour laquelle il n'y a pas vector::find est parce qu'il n'y a aucun avantage sur algorithmiques std::find (std::find est O(N) et en général, vous ne pouvez pas faire mieux pour les vecteurs).
Mais la raison pour laquelle vous avez map::find est parce qu'il peut être plus efficace (map::find est O(log N) si vous voulez toujours utiliser que sur std::find pour les cartes).
+0
Vous pouvez certainement faire mieux que O (N) si le vecteur est trié. – moodboom
2
quelle est l'alternative?
La norme offre std :: find, pour la recherche séquentielle sur des séquences arbitraires d'éléments similaires (ou quelque chose comme ça).
Ceci peut être appliqué à tous les conteneurs supportant les itérateurs, mais pour les conteneurs triés en interne (comme std::map), la recherche peut être optimisée. Dans ce cas, le conteneur offre sa propre fonction membre find.
pourquoi il n'y a pas de recherche de vecteur en C++?
Il n'y avait pas de point dans la création d'un std::vector<???>::find que la mise en œuvre serait identique à std::find(vector.begin(), vector.end(), value_to_find);.
Devrais-je écrire par moi-même?
No.Sauf si vous avez des limitations ou des exigences spécifiques, vous devez utiliser l'implémentation STL chaque fois que cela est possible.
3
Avoir une fonctionnalité 'find' dans la classe de conteneur enfreint 'SRP' (principe de responsabilité unique). La fonctionnalité principale d'un conteneur est de fournir des interfaces pour le stockage, la récupération des éléments dans le conteneur. «Trouver», «Trier», «Itérer», etc. ne sont pas des fonctionnalités essentielles d'un conteneur et ne font donc pas partie de son interface directe.
Cependant, comme 'Herb' indique Namespace Principle, 'find' fait partie de l'interface en étant défini dans le même espace de noms que 'vector', à savoir 'std'.
+1
Cependant, il est tout à fait approprié qu'un conteneur fournisse sa propre fonction 'find' _if_ il peut en fournir un qui fonctionne mieux que l'algorithme générique' std :: find' (considérons 'std :: map :: find'). –
Peut-être que vous devriez définir ce que "trouver" est destiné à faire? – KevenK
Il existe un 'std :: find'. Voir http://stackoverflow.com/questions/571394/how-to-find-an-item-in-a-stdvector/571405#571405 – meagar
La beauté de la STL réside dans le __découplage des conteneurs et algorithmes__, réalisé par collage les ensemble avec les itérateurs. C'est une décision de conception délibérée, qui conduit à des abstractions plus élevées que toutes les bibliothèques OO que j'ai vues. Si vous venez d'un arrière-plan OO plus strict (Java, C#), cela peut sembler étrange au début, mais cela vaut vraiment la peine d'apprendre. – sbi