Comment vérifier qu'un élément est dans un std::set?

Comment voulez-vous vérifier qu'un élément est dans un jeu?

Est-il un simple équivalent au code suivant:

myset.find(x) != myset.end()
  • La seule façon d'obtenir de plus simple que cela, ce serait un prédicat booléen: template <typename T> bool membre(T const &item). Et qui serait mis en œuvre (sous le capot) en termes de la ligne que vous parlez.
InformationsquelleAutor fulmicoton | 2009-11-09
  1. 342

    Typique de la façon de vérifier l'existence dans de nombreux conteneurs STL est:

    const bool is_in = container.find(element) != container.end();
    • il est spécifique pour les ensembles et des cartes. vecteurs, listes, etc. n'avez pas de trouver de la fonction membre.
    • Oui, vous avez raison. Parce que la recherche de l'élément dans le vecteur ou la liste est inefficace O(N), il n'existe pas de fonction membre find() mis en œuvre dans le vecteur ou d'une liste.
    • L'OMI à l'aide de count() est préférable car il est tout simplement plus courte et il convertit bool comme indiqué dans la réponse de Pierre. Je ne comprends pas pourquoi cette réponse a été accepté et donc de nombreux points...
    • J'ai eu une révision du code de commentaire où quelqu'un avait utilisé if (container.insert(foo).second == true) { //do something as this is the first time we've seen foo } je l'ai changé pour if (container.find(foo) == container.end) { //do something as this is the first time we've seen foo container.insert(foo); } L'examinateur n'a pas aimé mon changement, mais il semble de plus en plus évident pour moi que l'intention est.
    • Par souci d'exhaustivité: les vecteurs/listes peuvent utiliser std::find: std::find(container.begin(), container.end(), element) != container.end(); O(N) problème reste le même, bien sûr...
    • Avec votre variante: if(container.find(foo) == container.end()) besoin de faire un arbre de recherche pour trouver l'élément premier - si pas trouvé, alors vous devez faire un deuxième arbre de recherche pour trouver le bon emplacement d'insertion. La variante originale if(container.insert(foo).second) {...} a le charme qu'il a juste besoin d'un seul arbre de recherche...
    • count() est inefficace car elle nécessite de traverser l'ensemble de la structure de données. Find() s'arrête quand il en trouve un. Si tout ce qui vous intéresse est de savoir si l'élément est dans la liste ou pas, ou vous savez qu'il ya un seul exemplaire dans la liste, ne jamais utiliser la fonction count().
    • vous devriez vérifier la mise en œuvre du comte. il fait exactement la même chose que trouver, parce que la seule chose qu'il fait c'est l'appel de la trouver et de la valeur de retour: retour _M_t.trouver(__x) == _M_t.fin() ? 0 : 1;
    • pas sur le vecteur, qui a été le contexte des commentaires de tenter de trouver un mécanisme pour tous les conteneurs.
    • merci pour le tuyau sur cette question importante.
    • il y a un set.contains(x) qui renvoie un booléen en C++ 20 standard. Je ne sais pas pourquoi il nous a fallu jusqu'en 2020 pour le faire.
    • ne peut pas être plus d'accord. C++ STL a été totalement obsolète en raison du manque de sens sémantique.

    InformationsquelleAutor unwind
  2. 175

    Une autre façon de dire simplement si un élément existe, c'est pour vérifier la count()

    if (myset.count(x)) {
   //x is in the set, count is 1
} else {
   //count zero, i.e. x not in the set
}

    La plupart du temps, cependant, je me retrouve à avoir besoin d'accéder à l'élément où je l'ai vérifier son existence.

    Si je dois trouver l'itérateur de toute façon. Alors, bien sûr, il est préférable de simplement comparer à end trop. 

    set< X >::iterator it = myset.find(x);
if (it != myset.end()) {
   //do something with *it
}

    C++ 20

    En C++20 enregistre contains de la fonction, de sorte que celui-ci devient possible

    if (myset.contains(x)) {
  //x is in the set
} else {
  //no x 
}
    • Notez que l'utilisation de count() au lieu de find() n'est jamais mieux, mais potentiellement pire. C'est parce que find() sera de retour après le premier match, count() toujours itérer sur tous les éléments.
    • c'est seulement approprié pour les multiset et multimap je pensais? Toujours bon à signaler cependant 🙂
    • std::set est généralement mis en œuvre avec l'ordre de l'arborescence afin de count() et find() les deux ont O(logn). Ni va itérer sur tous les éléments de l'ensemble.
    • Êtes-vous certains? Depuis il est seulement possible pour set pour contenir un membre qui correspond à, ne serait pas la fonction d'être mis en œuvre de manière à s'arrêter après avoir trouvé le premier élément, dans ce cas, comme Pieter de points? Réponse utile en tout cas!
    • Oui, vous avez tout à fait raison (et sont donc +Pierre et +Alan): std::set, les deux fonctions sont équivalentes en termes de performances. Ainsi, même si la première partie de mon commentaire (count() jamais être plus rapide que find()) tient toujours, la deuxième partie est en effet pas applicable à std::set. Cependant, je pense autre argument peut être fait en faveur de find(): il est plus expressif, c'est à dire souligne que vous êtes essayer de trouver un élément, au lieu de compter le nombre de occurrances.
    • Je préfère find() même count() a les mêmes performances et plus concis, parce que d'autres développeurs peuvent confondre la raison pour laquelle vous utilisez count() quand juste vérifier si il est dans le conteneur.
    • Dans GCC .count pour set utilise find: count(const key_type& __x) const { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }.
    • Un autre argument favorable à find(): Si le type de conteneur changer tout le code à l'aide de count() besoin d'être fixé. Mais tous les find() code fonctionnent encore correctement.
    • pourquoi ne std::set ont count ? Peut un ensemble ont le même élément deux fois?
    • Je fais un peu d'accord Frerich dans un sens - has() ou contains() est beaucoup plus auto-documentation. Bonne chose qu'en C++, 20 🙂

    InformationsquelleAutor Pieter
  3. 35

    Juste pour préciser, la raison pourquoi il n'est pas membre comme contains() dans ces types de conteneurs est parce que vous vous ouvrir à l'écriture inefficace code. Une telle méthode serait probablement juste de faire un this->find(key) != this->end() en interne, mais réfléchissez à ce que vous faites lorsque la clé est bien présente; dans la plupart des cas, vous aurez alors voulez obtenir de l'élément et de faire quelque chose avec elle. Cela signifie que vous auriez à faire un deuxième find(), ce qui est inefficace. Il est préférable d'utiliser les trouver directement, de sorte que vous pouvez mettre en cache le résultat, comme suit:

    Container::const_iterator it = myContainer.find(key);
if (it != myContainer.end())
{
  //Do something with it, no more lookup needed.
}
else
{
  //Key was not present.
}

    Bien sûr, si vous n'avez pas à se soucier de l'efficacité, vous pouvez toujours passer votre propre, mais dans ce cas, vous probablement ne devrait pas être à l'aide de C++... 😉

    • Ce sur les jeux? Habituellement, vous avez déjà de l'élément, mais qui souhaitent tout simplement pour vérifier si il est dans.
    • Avez-vous une référence pour savoir si c'est la raison pour laquelle cette méthode/fonction n'est pas inclus dans la stl, ou est-ce juste votre hypothèse?
    • C'est ma supposition.
    • Vrai, pour le std::set, il est probablement juste de faire de la cohérence.
    • la cohérence n'est pas exactement le côté fort de la STL... (list::remove, remove(makes_sense_only_for_vector, iterators)...)
    • Je suis totalement en désaccord, std::remove algorithme fonctionne avec n'importe quel STL-comme conteneur, mais ne pas supprimer physiquement les éléments (car elle ne connaît pas la structure interne du conteneur, c'est à dire un std::list est différent d'un std::vector). C'est pourquoi le membre erase (erase_after pour forward_list) est utilisé en conjonction avec std::remove. Conteneurs associatifs définir leurs propres versions de certains algorithmes (comme remove, find etc) pour des raisons d'efficacité: c'est à dire, dans un list, vous venez de rétablir le lien avec les pointeurs internes, sans effectuer le générique de l'algorithme de suppression.
    • il va de tri de travail. Mais ça n'a pas de sens. Par exemple, essayez de l'utiliser sur un list ou slist. Quel serait le résultat? Est-ce que jamais souhaitable?
    • et de mon point de vue, est encore debout. Seulement certains conteneurs ont remove membre. La cohérence n'est pas le côté fort de la STL...
    • Je suis d'accord que certains conteneurs introduire les fonctions de membres qui se spécialisent algorithmes (algorithmes) sont découplées de conteneurs ne savent pas leur structure, de sorte que ne peut pas faire usage de la structure interne puisque l'accès se fait uniquement via les itérateurs). Et je suis d'accord que cela peut être incompatibles, cependant, le std::algorithmes de travailler avec tous les conteneurs (restrictions sur les itérateurs, vous ne pouvez pas utiliser de tri pour les itérateurs qui ne sont pas aléatoire). std::remove sur list œuvres, il fait ce qu'il fait sur un std::vector, déplace le end itérateur de coeur. Avez-vous un exemple de comportement étrange?
    • quand est std::remove(a_list.begin(), a_list.end()) utile? Que faut-il réellement faire de la liste chaînée?
    • peut-être que je ne comprends pas ce que tu veux dire, désolé pour le dos-et-vient des commentaires. Voici un code en direct en comparant std::remove pour les deux std::vector et std::list, et à mon avis, il se comporte de manière identique dans les deux cas, ideone.com/Psbepy
    • Il ne fait pas de sens pour moi de ne pas inclure une fonctionnalité parce que quelqu'un peut l'utiliser de manière incorrecte si ils ne savent pas ce qu'ils faisaient. La programmation est pour les gens qui peuvent penser par eux-mêmes et sont responsables de leur code et de ses performances
    • A noter que C++20 introduit contains(). En effet, il ya beaucoup de raisons que vous pourriez vouloir pour voir si quelque chose est dans un jeu sans l'obtention d'un itérateur pour elle. En fait, avec l'ensemble, vous ne pouvez pas faire beaucoup avec qui itérateur autre que supprimer de l'élément, dont vous pouvez déjà faire sans l'accord préalable de recherche de toute façon.

    InformationsquelleAutor Tim
  4. 6

    Si vous allez à ajouter un contains fonction, il pourrait ressembler à ceci:

    #include <algorithm>
#include <iterator>

template<class TInputIterator, class T> inline
bool contains(TInputIterator first, TInputIterator last, const T& value)
{
    return std::find(first, last, value) != last;
}

template<class TContainer, class T> inline
bool contains(const TContainer& container, const T& value)
{
    //This works with more containers but requires std::begin and std::end
    //from C++0x, which you can get either:
    // 1. By using a C++0x compiler or
    // 2. Including the utility functions below.
    return contains(std::begin(container), std::end(container), value);

    //This works pre-C++0x (and without the utility functions below, but doesn't
    //work for fixed-length arrays.
    //return contains(container.begin(), container.end(), value);
}

template<class T> inline
bool contains(const std::set<T>& container, const T& value)
{
    return container.find(value) != container.end();
}

    Cela fonctionne avec std::set, d'autres conteneurs STL, et même des tableaux de longueur fixe:

    void test()
{
    std::set<int> set;
    set.insert(1);
    set.insert(4);
    assert(!contains(set, 3));

    int set2[] = { 1, 2, 3 };
    assert(contains(set2, 3));
}

    Edit:

    Comme l'a souligné dans les commentaires, j'ai involontairement utilisé une fonction nouvelle pour C++0x (std::begin et std::end). Ici est la quasi-trivial de mise en œuvre de VS2010:

    namespace std {

template<class _Container> inline
    typename _Container::iterator begin(_Container& _Cont)
    { //get beginning of sequence
    return (_Cont.begin());
    }

template<class _Container> inline
    typename _Container::const_iterator begin(const _Container& _Cont)
    { //get beginning of sequence
    return (_Cont.begin());
    }

template<class _Container> inline
    typename _Container::iterator end(_Container& _Cont)
    { //get end of sequence
    return (_Cont.end());
    }

template<class _Container> inline
    typename _Container::const_iterator end(const _Container& _Cont)
    { //get end of sequence
    return (_Cont.end());
    }

template<class _Ty,
    size_t _Size> inline
    _Ty *begin(_Ty (&_Array)[_Size])
    { //get beginning of array
    return (&_Array[0]);
    }

template<class _Ty,
    size_t _Size> inline
    _Ty *end(_Ty (&_Array)[_Size])
    { //get end of array
    return (&_Array[0] + _Size);
    }

}
    • Cela fonctionne, mais est inefficace, comme expliqué ci-dessous.
    • il en fait est inefficace, mais pas du tout pour la raison que vous avez mentionné.
    • Assurez-vous d'inclure la spécialisation pour std::set, et n'oubliez pas que c'est seulement approprié si le que chose que vous devez savoir, c'est l'existence.
    • std::begin(conteneur)? Ce STL standard est qui? Il ne compile pas sur mon gcc.
    • heh, c'est nouveau pour C++0x. J'ai ajouté de la mise en œuvre de mon compilateur ci-dessus.
    • ce sujet de conteneur.begin()?
    • Cela ne fonctionne pas pour les tableaux de longueur. Vous devrez soit 1) le changement std::begin(container) à container.begin() (même pour la fin), ou 2) d'inclure les nouvelles fonctions de l'utilitaire à la base.
    • Vous pouvez utiliser boost::begin() et boost::end() de Stimuler la gamme de la bibliothèque.
    • c'est toujours insuffisant pour les raisons que j'ai fait mention.
    • Si vous connaissez le jeu contient une valeur, alors vous avez déjà la valeur. La seule raison pour laquelle vous avez besoin de l'itérateur est d'effacer l'élément de l'ensemble. Si tous vous avez besoin est de savoir si ou non une collection contient une valeur, cette solution n'en est pas moins efficace que toute autre solution.
    • C'est beaucoup d'ifs. Je parle du cas général, et expliquer pourquoi cette méthode n'est pas fournie par le TSL. Dans de nombreux cas, tout ce que vous avez est une clé, et vous êtes sur de trouver la valeur associée, ou comme vous le dites, vous avez besoin de l'itérateur pour supprimer l'élément.

    InformationsquelleAutor Sam Harwell
  5. 4

    Vous pouvez aussi vérifier si un élément est dans le jeu ou pas lors de l'insertion de l'élément.
    Le seul élément de la version de retourner une paire, avec ses membres de la paire::première série à un itérateur pointant vers le nouvellement inséré l'élément ou de l'élément équivalent déjà dans le jeu. La paire::deuxième élément de la paire est définie sur true si un élément nouveau a été inséré ou false si un élément équivalent existait déjà.

    Par exemple: Supposons que l'ensemble a déjà 20 comme un élément.

     std::set<int> myset;
 std::set<int>::iterator it;
 std::pair<std::set<int>::iterator,bool> ret;

 ret=myset.insert(20);
 if(ret.second==false)
 {
     //do nothing

 }
 else
 {
    //do something
 }

 it=ret.first //points to element 20 already in set.

    Si l'élément est inséré de paire: d'abord en va point à la position de l'élément nouveau dans la série.

    InformationsquelleAutor Prashant Shubham
  6. 3

    Dans C++20 nous allons enfin obtenir std::set::contains méthode.

    #include <iostream>
#include <string>
#include <set>

int main()
{
    std::set<std::string> example = {"Do", "not", "panic", "!!!"};

    if(example.contains("panic")) {
        std::cout << "Found\n";
    } else {
        std::cout << "Not found\n";
    }
}
    InformationsquelleAutor Denis Sablukov
  7. 2

    Écrire votre propre:

    template<class T>
bool checkElementIsInSet(const T& elem, const std::set<T>& container)
{
  return container.find(elem) != container.end();
}
    • viens donc : template<class T> static inline bool contient(const std::set<T>& S, T x) { return (S. find(x) != S. end()); }
    • ne créez pas de statique des fonctions globales. mettez votre fonction dans l'anonymat de l'espace de noms à la place: c'est le C++ moyen de créer des fonctions qui ne sont pas de lien vers d'autres unités de compilation. aussi, votre T paramètre doit être un const référence, pour la const-correctness et pour plus d'efficacité.
    • -1: Pas basé sur un modèle et non pas tout dans la STL style. C'est très bien si vous n'utilisez pas la STL, mais si vous utilisez STL, vous devriez au moins essayer de la suivre ses normes.
    • mais si je veux qu'il inline?
    • Pourriez-vous nous donner votre version? Je ne suis pas vraiment familier avec STL style...
    • Je l'ai déjà fait avant de poster ce commentaire.
    • Je suis désolé que mon code n'est pas à vos normes, j'étais juste en montrant que si vous n'aimez pas du TSL interface, vous pouvez écrire votre propre. Hola, pas basé sur un modèle? Comment templated-t-il? Votre exemple a l'air bien, cela ne veut pas dire que le mien est mauvais. Il est un peu plus porté sur l'ensemble comme il a été demandé par l'OP.
    • Je sais je suis pointilleux sur les choses que les autres ne le sont pas. J'ai juste la haine de downvotes, sans une explication, donc j'ai donné le mien. Pour ce que ça vaut, si vous avez donné la solution dans une interview, il avait un sérieux pas vers la "location" de côté. C'est pratique, concis et efficace, je pense juste que le nom n'est pas aussi intuitif que cela pouvait être, il pourrait s'appliquer à d'autres conteneurs, et les paramètres sont dans l'ordre inverse de plusieurs autres fonctions.
    • Je faisais juste un point. Je pensais que les gens seraient assez intelligents pour obtenir de l'image.

    InformationsquelleAutor stefaanv
  8. 2

    - Je utiliser

    if(!my_set.count(that_element)) //Element is present...
;

    Mais il n'est pas aussi efficace que 

    if(my_set.find(that_element)!=my_set.end()) ....;

    Ma version seulement d'économiser de mon temps dans l'écriture du code. Je préfère cette façon concurrentielle pour le codage.

    • Oui, count(). Quelqu'un incapable de saisir un entier-de retour de la fonction utilisée dans une expression Booléenne est un test pour les non-zéro va avoir beaucoup, beaucoup d'autres travaux dans la grande mer de C/C++ idiomes. Et, comme l'a noté ci-dessus, doit être vraiment aussi efficace pour les jeux, c'était la question.
    InformationsquelleAutor Manas Bondale
  9. 0

    J'étais capable d'écrire un général contains fonction pour std::list et std::vector,

    template<typename T>
bool contains( const list<T>& container, const T& elt )
{
  return find( container.begin(), container.end(), elt ) != container.end() ;
}

template<typename T>
bool contains( const vector<T>& container, const T& elt )
{
  return find( container.begin(), container.end(), elt ) != container.end() ;
}

//use:
if( contains( yourList, itemInList ) ) //then do something

    Cela nettoie la syntaxe un peu.

    Mais je ne pouvais pas utiliser modèle de paramètre de modèle de la magie pour faire ce travail arbitraire des conteneurs stl.

    //NOT WORKING:
template<template<class> class STLContainer, class T>
bool contains( STLContainer<T> container, T elt )
{
  return find( container.begin(), container.end(), elt ) != container.end() ;
}

    Des commentaires au sujet de l'amélioration de la dernière réponse, ce serait bien.

    • Désolé je ne peux pas vraiment écrire bloc de code en commentaire, mais qu'en est template<typename CONTAINER, typename CONTAINEE> bool contains(const CONTAINER& container, const CONTAINEE& needle) { return find(container.begin(), container.end(), needle) != container.end();
    • Ce n'est pas de travail, parce que std::vector besoins supplémentaires de l'allocateur comme argument de modèle et std::set a besoin d'une allocation et une moins argument de modèle. Ces lignes woulkd travail: template<template<class,class> classe STLContainer, class T, class A> bool contient( STLContainer<T A> container, T elt ) { return trouver( récipient.begin(), d'un conteneur.end(), elt ) != le conteneur.fin() ; } template<template<class,la classe,la classe> classe STLContainer, de la classe T, classe L, classe A> bool contient( STLContainer<T,A,L> container, T elt ) { return trouver( récipient.begin(), d'un conteneur.end(), elt ) != le conteneur.fin() ; }
    InformationsquelleAutor bobobobo
  10. 0

    //Syntaxe générale 

           set<int>::iterator ii = find(set1.begin(),set1.end(),"element to be searched");

    /* dans le code ci-dessous je suis en train d'essayer de trouver l'élément 4 et int set s'il est présent ou pas*/

    set<int>::iterator ii = find(set1.begin(),set1.end(),4);
 if(ii!=set1.end())
 {
    cout<<"element found";
    set1.erase(ii);//in case you want to erase that element from set.
 }
    InformationsquelleAutor sanjeev