Comment savoir si un élément est présent dans un vecteur std ::?

616

Tout ce que je veux faire, c'est vérifier si un élément existe dans le vecteur ou non, afin de pouvoir traiter chaque cas.

if ( item_present )
   do_this();
else
   do_that();
Joan Venge
la source
2
la recherche dans un vecteur est très lente car vous devez regarder chaque élément du vecteur, alors pensez à utiliser une carte si vous faites beaucoup de recherches
naumcho
7
@naumcho: Si le vecteur est trié, il y a toujours une recherche binaire, comme indiqué ci-dessous. Cela le rend aussi rapide qu'une carte et si vous ne stockez que des valeurs (pas des cartes de clés / valeurs), cela va utiliser beaucoup moins de mémoire.
Adam Hawes
4
les cartes ne sont certainement pas le meilleur choix, mais l'utilisation de set peut être utile. Si vous avez besoin du temps de recherche O (1), hash_set est le chemin à parcourir.
Philipp
Une superbe réponse présente sur une question en double: stackoverflow.com/a/3451045/472647
CodeMouse92
1
Si vous cherchez plusieurs fois des nombres différents, une table de hachage serait plus efficace.
NL628

Réponses:

916

Vous pouvez utiliser à std::findpartir de <algorithm>:

#include <vector>
vector<int> vec; 
//can have other data types instead of int but must same datatype as item 
std::find(vec.begin(), vec.end(), item) != vec.end()

Cela renvoie un booléen ( trues'il est présent, falsesinon). Avec votre exemple:

#include <algorithm>
#include <vector>

if ( std::find(vec.begin(), vec.end(), item) != vec.end() )
   do_this();
else
   do_that();
MSN
la source
216
Je ne vois pas comment count () pourrait être plus rapide que find (), car find () s'arrête dès qu'un élément est trouvé, tandis que count () doit toujours parcourir toute la séquence.
Éric Malenfant le
114
N'oubliez pas, #include <algorithm>sinon vous pourriez obtenir des erreurs très étranges comme «
Impossible de
80
Cela n'a-t-il pas dérangé personne que, bien que la STL soit "orientée objet", elle .find()n'est toujours pas une fonction membre std::vector, comme vous vous en doutez? Je me demande si c'est en quelque sorte une conséquence des modèles.
bobobobo
71
@bobobobo: OOP n'a rien à voir avec les membres par rapport aux non-membres. Et il y a une école de pensée répandue que si quelque chose n'a pas à être membre, ou quand il ne donne aucun avantage lorsqu'il est mis en œuvre en tant que membre, alors il ne devrait pas être membre; std::vector<>::find()ne donnerait aucun avantage et n’est pas nécessaire. Par conséquent, non, il ne devrait pas être membre. Voir aussi en.wikipedia.org/wiki/Coupling_%28computer_programming%29
Sebastian Mach
36
@phresnel Je dirais que "quand cela ne donne aucun avantage lorsqu'il est implémenté en tant que membre" est faux pour ce cas. L'avantage étant une interface simplifiée et plus claire. Par exemple: mvec.find(key) != mvec.cend()est préférable à std::find(mvec.cbegin(), mvec.cend(), key) != mvec.cend().
swalog
113

Comme d'autres l'ont dit, utilisez la STL findou les find_iffonctions. Mais si vous êtes à la recherche dans des vecteurs très importants et cette performance impacts, vous pouvez trier votre vecteur, puis utilisez les binary_search, lower_boundou des upper_boundalgorithmes.

Brian Neal
la source
3
Bonne réponse! La recherche est toujours o (n). lower_bound est o (log (n)) s'il est utilisé avec des itérateurs à accès aléatoire.
Stephen Edmonds, le
30
Le tri est cependant O (nlogn), donc cela ne vaut que si vous effectuez plus de recherches O (logn).
liori
7
@liori Vrai, cela dépend de vos habitudes d'utilisation. Si vous n'avez besoin de le trier qu'une seule fois, effectuez de nombreuses recherches à plusieurs reprises, cela peut vous sauver.
Brian Neal
1
@Brian Neal, trier un grand vecteur vaut la peine s'il doit y avoir de nombreuses recherches d'éléments. Le tri sera O (nlogn) et O (n) sera meilleur s'il ne faut trouver un élément qu'une seule fois :)
Swapnil B.
47

Utilisez find à partir de l'en-tête de l'algorithme de stl. J'ai illustré son utilisation avec le type int. Vous pouvez utiliser n'importe quel type que vous aimez tant que vous pouvez comparer pour l'égalité (surcharge == si vous en avez besoin pour votre classe personnalisée).

#include <algorithm>
#include <vector>

using namespace std;
int main()
{   
    typedef vector<int> IntContainer;
    typedef IntContainer::iterator IntIterator;

    IntContainer vw;

    //...

    // find 5
    IntIterator i = find(vw.begin(), vw.end(), 5);

    if (i != vw.end()) {
        // found it
    } else {
        // doesn't exist
    }

    return 0;
}
m-sharp
la source
2
Selon les besoins de l'OP, find_if () pourrait également être approprié. Il permet de rechercher en utilisant un prédicat arbitraire au lieu de l'égalité.
Éric Malenfant
Oups, vous avez vu votre commentaire trop tard. La réponse que j'ai donnée mentionne également find_if.
Frank
39

Si votre vecteur n'est pas ordonné, utilisez l'approche suggérée par MSN:

if(std::find(vector.begin(), vector.end(), item)!=vector.end()){
      // Found the item
}

Si votre vecteur est ordonné, utilisez la méthode binary_search Brian Neal a suggéré:

if(binary_search(vector.begin(), vector.end(), item)){
     // Found the item
}

la recherche binaire donne les performances du pire des cas O (log n), ce qui est beaucoup plus efficace que la première approche. Afin d'utiliser la recherche binaire, vous pouvez utiliser qsort pour trier d'abord le vecteur pour garantir qu'il est ordonné.

spiralmoon
la source
3
Tu ne veux pas dire std::sort? qsortest très inefficace sur les vecteurs .... voir: stackoverflow.com/questions/12308243/…
Jason R. Mick
1
La recherche binaire fonctionnera mieux pour les grands conteneurs, mais pour les petits conteneurs, une simple recherche linéaire sera probablement aussi rapide ou plus rapide.
BillT
21

J'utilise quelque chose comme ça ...

#include <algorithm>


template <typename T> 
const bool Contains( std::vector<T>& Vec, const T& Element ) 
{
    if (std::find(Vec.begin(), Vec.end(), Element) != Vec.end())
        return true;

    return false;
}

if (Contains(vector,item))
   blah
else
   blah

... comme ça c'est en fait clair et lisible. (Évidemment, vous pouvez réutiliser le modèle à plusieurs endroits).

Andy Krouwel
la source
et vous pouvez le faire fonctionner pour les listes ou les vecteurs en utilisant 2 noms de caractères
Erik Aronesty
@ErikAronesty, vous pouvez vous en tirer avec 1 argument de modèle si vous utilisez value_typele conteneur pour le type d'élément. J'ai ajouté une réponse comme celle-ci.
Martin Broadhurst
13

En C ++ 11, vous pouvez utiliser any_of. Par exemple, si c'est un vector<string> v;alors:

if (any_of(v.begin(), v.end(), bind(equal_to<string>(), _1, item)))
   do_this();
else
   do_that();

Vous pouvez également utiliser un lambda:

if (any_of(v.begin(), v.end(), [&](const std::string& elem) { return elem == item; }))
   do_this();
else
   do_that();
Deqing
la source
1
bind1stet bind2ndsont obsolètes depuis C ++ 11 et complètement supprimés en C ++ 17. Utilisez plutôt bindavec placeholderset / ou lambdas.
andreee
11

Voici une fonction qui fonctionnera pour n'importe quel conteneur:

template <class Container> 
const bool contains(const Container& container, const typename Container::value_type& element) 
{
    return std::find(container.begin(), container.end(), element) != container.end();
}

Notez que vous pouvez vous en tirer avec 1 paramètre de modèle, car vous pouvez extraire le value_typedu conteneur. Vous avez besoin du typenamecar Container::value_typeest un nom dépendant .

Martin Broadhurst
la source
5
Notez que c'est parfois un peu trop large - cela fonctionnerait pour std :: set par exemple, mais donnerait des performances terribles par rapport à la fonction membre find (). J'ai trouvé préférable d'ajouter une spécialisation pour les conteneurs avec une recherche plus rapide (set / map, unordered_ *)
Andy Krouwel
10

Gardez à l'esprit que, si vous effectuez de nombreuses recherches, il existe des conteneurs STL qui conviennent mieux à cela. Je ne sais pas quelle est votre application, mais les conteneurs associatifs comme std :: map peuvent être intéressants.

std :: vector est le conteneur de choix, sauf si vous avez une raison pour une autre, et les recherches par valeur peuvent être une telle raison.

David Thornley
la source
Même avec des recherches par valeur, le vecteur peut être un bon choix, tant qu'il est trié et que vous utilisez binary_search, lower_bound ou upper_bound. Si le contenu du conteneur change entre les recherches, le vecteur n'est pas très bon en raison de la nécessité de trier à nouveau.
Renze de Waal
8

Utilisez la fonction de recherche STL .

Gardez à l'esprit qu'il existe également une fonction find_if , que vous pouvez utiliser si votre recherche est plus complexe, c'est-à-dire si vous ne recherchez pas seulement un élément, mais, par exemple, vous voulez voir s'il y a un élément qui remplit un certain condition, par exemple, une chaîne commençant par "abc". ( find_ifvous donnerait un itérateur qui pointe vers le premier élément de ce type).

Franc
la source
7

Avec boost, vous pouvez utiliser any_of_equal:

#include <boost/algorithm/cxx11/any_of.hpp>

bool item_present = boost::algorithm::any_of_equal(vector, element);
Mikhail
la source
5

Vous pouvez essayer ce code:

#include <algorithm>
#include <vector>

// You can use class, struct or primitive data type for Item
struct Item {
    //Some fields
};
typedef std::vector<Item> ItemVector;
typedef ItemVector::iterator ItemIterator;
//...
ItemVector vtItem;
//... (init data for vtItem)
Item itemToFind;
//...

ItemIterator itemItr;
itemItr = std::find(vtItem.begin(), vtItem.end(), itemToFind);
if (itemItr != vtItem.end()) {
    // Item found
    // doThis()
}
else {
    // Item not found
    // doThat()
}
TrungTN
la source
3

Vous pouvez utiliser la findfonction, trouvée dans l' stdespace de noms, c'est-à-dire std::find. Vous passez la std::findfonction beginet l' enditérateur du vecteur que vous souhaitez rechercher, ainsi que l'élément que vous recherchez et comparez l'itérateur résultant à la fin du vecteur pour voir s'ils correspondent ou non.

std::find(vector.begin(), vector.end(), item) != vector.end()

Vous pouvez également déréférencer cet itérateur et l'utiliser normalement, comme n'importe quel autre itérateur.

TankorSmash
la source
3

Vous pouvez également utiliser le comptage. Il renverra le nombre d'éléments présents dans un vecteur.

int t=count(vec.begin(),vec.end(),item);
Aditya
la source
11
findest plus rapide que count, car il ne continue pas de compter après le premier match.
Camille Goudeseune
2

Si vous voulez trouver une chaîne dans un vecteur:

    struct isEqual
{
    isEqual(const std::string& s): m_s(s)
    {}

    bool operator()(OIDV* l)
    {
        return l->oid == m_s;
    }

    std::string m_s;
};
struct OIDV
{
    string oid;
//else
};
VecOidv::iterator itFind=find_if(vecOidv.begin(),vecOidv.end(),isEqual(szTmp));
Gank
la source
2

Un autre exemple utilisant des opérateurs C ++.

#include <vector>
#include <algorithm>
#include <stdexcept>

template<typename T>
inline static bool operator ==(const std::vector<T>& v, const T& elem)
{
  return (std::find(v.begin(), v.end(), elem) != v.end());
}

template<typename T>
inline static bool operator !=(const std::vector<T>& v, const T& elem)
{
  return (std::find(v.begin(), v.end(), elem) == v.end());
}

enum CODEC_ID {
  CODEC_ID_AAC,
  CODEC_ID_AC3,
  CODEC_ID_H262,
  CODEC_ID_H263,
  CODEC_ID_H264,
  CODEC_ID_H265,
  CODEC_ID_MAX
};

void main()
{
  CODEC_ID codec = CODEC_ID_H264;
  std::vector<CODEC_ID> codec_list;

  codec_list.reserve(CODEC_ID_MAX);
  codec_list.push_back(CODEC_ID_AAC);
  codec_list.push_back(CODEC_ID_AC3);
  codec_list.push_back(CODEC_ID_H262);
  codec_list.push_back(CODEC_ID_H263);
  codec_list.push_back(CODEC_ID_H264);
  codec_list.push_back(CODEC_ID_H265);

  if (codec_list != codec)
  {
    throw std::runtime_error("codec not found!");
  }

  if (codec_list == codec)
  {
    throw std::logic_error("codec has been found!");
  }
}
Valdemar_Rudolfovich
la source
4
Je ne recommanderais pas abuser de la surcharge de l'opérateur de cette manière.
Leon
2
Leon, je suis d'accord avec toi, sémantiquement ce n'est pas correct. Je l'utilise pour rendre les tests unitaires plus clairs.
Valdemar_Rudolfovich
1
template <typename T> bool IsInVector(T what, std::vector<T> * vec)
{
    if(std::find(vec->begin(),vec->end(),what)!=vec->end())
        return true;
    return false;
}
user3157855
la source
1

(C ++ 17 et supérieur):

peut std::searchégalement utiliser

Ceci est également utile pour rechercher une séquence d'éléments.

#include <algorithm>
#include <iostream>
#include <vector>

template <typename Container>
bool search_vector(const Container& vec, const Container& searchvec)
{
    return std::search(vec.begin(), vec.end(), searchvec.begin(), searchvec.end()) != vec.end();
}

int main()
{
     std::vector<int> v = {2,4,6,8};

     //THIS WORKS. SEARCHING ONLY ONE ELEMENT.
     std::vector<int> searchVector1 = {2};
     if(search_vector(v,searchVector1))
         std::cout<<"searchVector1 found"<<std::endl;
     else
         std::cout<<"searchVector1 not found"<<std::endl;

     //THIS WORKS, AS THE ELEMENTS ARE SEQUENTIAL.
     std::vector<int> searchVector2 = {6,8};
     if(search_vector(v,searchVector2))
         std::cout<<"searchVector2 found"<<std::endl;
     else
         std::cout<<"searchVector2 not found"<<std::endl;

     //THIS WILL NOT WORK, AS THE ELEMENTS ARE NOT SEQUENTIAL.
     std::vector<int> searchVector3 = {8,6};
     if(search_vector(v,searchVector3))
         std::cout<<"searchVector3 found"<<std::endl;
     else
         std::cout<<"searchVector3 not found"<<std::endl;
}

Il est également possible de passer certains algorithmes de recherche. Reportez-vous ici.

https://en.cppreference.com/w/cpp/algorithm/search

Pavan Chandaka
la source
1

J'ai personnellement utilisé des modèles récemment pour gérer plusieurs types de conteneurs à la fois plutôt que de traiter uniquement des vecteurs. J'ai trouvé un exemple similaire en ligne (je ne me souviens pas d'où), donc le mérite revient à qui que ce soit. Ce modèle particulier semble également gérer les tableaux bruts.

template <typename Container, typename T = typename std::decay<decltype(*std::begin(std::declval<Container>()))>::type>
bool contains(Container && c, T v)
{
    return std::find(std::begin(c), std::end(c), v) != std::end(c);
}
Pascal Laferrière
la source
-4

Utiliser Newton C ++ est plus facile, auto-documenté et plus rapide qu'avec std :: find car il renvoie directement un booléen.

bool exists_linear( INPUT_ITERATOR first, INPUT_ITERATOR last, const T& value )

bool exists_binary( INPUT_ITERATOR first, INPUT_ITERATOR last, const T& value )

Je pense que c'est évident ce que font les fonctions.

include <newton/algorithm/algorithm.hpp>

if ( newton::exists_linear(first, last, value) )
   do_this();
else
   do_that();
Moises Rojo
la source