By Joan Venge


2009-02-20 21:58:41 8 Comments

All I want to do is to check whether an element exists in the vector or not, so I can deal with each case.

if ( item_present )
   do_this();
else
   do_that();

18 comments

@MSN 2009-02-20 22:00:50

You can use std::find from <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()

This returns a bool (true if present, false otherwise). With your example:

#include <algorithm>
#include <vector>

if ( std::find(vec.begin(), vec.end(), item) != vec.end() )
   do_this();
else
   do_that();

@Klaim 2009-02-21 00:26:47

Using std::count instead ( std::count(...) > 0 ), would it be "faster in theory"?

@MSN 2009-02-21 00:31:08

Possibly. It depends on how often you search empty vectors.

@Éric Malenfant 2009-02-21 03:29:18

I don't see how count() could be faster than find(), since find() stops as soon as one element is found, while count() always has to scan the whole sequence.

@MSN 2009-02-22 16:46:49

Actually, you'd want to use !vector.empty(). But whatever.

@rustyx 2012-03-02 15:46:58

Don't forget to #include <algorithm> or else you might get very strange errors like 'can't find matching function in namespace std'

@rajat 2012-10-18 13:06:13

What will this return ?

@MSN 2012-10-18 23:31:34

a bool. It's a drop in replacement (or initialization) of item_present in the original question.

@bobobobo 2012-12-07 02:33:56

Has it not bothered anyone that despite the STL being "object-oriented", .find() is still not a member function of std::vector, as you'd expect it should be? I wonder if this is somehow a consequence of templating.

@Sebastian Mach 2013-02-04 13:54:50

@bobobobo: OOP has nothing to do with members vs. non-members. And there is a widespread school of thought that if something does not have to be a member, or when it does not give any advantage when implemented as a member, than it should not be a member; std::vector<>::find() would not give any advantage, nor is it needed, therefore, no, it should not be a member. See also en.wikipedia.org/wiki/Coupling_%28computer_programming%29

@ArtOfWarfare 2013-02-10 20:25:19

I almost posted asking about whether this could be optimized by only calling vector.end() once before realizing that, first, if I'm really concerned with speed, I shouldn't be using find() on a vector at all, and second, that vector.end() being called once instead of twice is hardly any improvement at all.

@Steve Lorimer 2013-04-05 02:34:10

@ArtOfWarfare due to cache locality a sorted vector will often be far quicker to search than a map or set.

@Frerich Raabe 2013-12-10 08:23:21

@ArtOfWarfare Thirdly, you may find that the end() call is inlined by the compiler so there's no actual call` at all but just a raw pointer.

@user854270 2014-09-09 12:45:44

@phresnel: If it does not give any advantage to make find() a member of std::vector, how on earth current member functions give an advantage by being members of std::vector of std::map ??

@Sebastian Mach 2014-09-11 09:47:13

@Gasso: Nobody rated the sanity of the current members being members in this thread. I just presented that by certain school of thoughts, find should not be added as a member to std::vector; whether existing members make sense or not was not discussed, and indeed the STL is not well designed in many aspects, mainly because the lack of experience (and my post was a response to bobobobo, who implied that members are part of the OOP concept, but they are not)

@swalog 2015-04-29 20:09:55

@phresnel I would argue that "when it does not give any advantage when implemented as a member" is false for this case. The advantage being a simplified and clearer interface. For example: mvec.find(key) != mvec.cend() is preferable to std::find(mvec.cbegin(), mvec.cend(), key) != mvec.cend().

@koan911 2015-05-07 09:25:03

@bobobobo Referring to the section in "Containers and algorithms" within sgi.com/tech/stl/stl_introduction.html beginning with the words: "There are two important points to notice about this call to reverse." I think this sheds some light on the thinking of the designers of the STL, although one might still wonder how much this thinking predated the idea of using C++ abstract classes to define interfaces to make the linkage between algorithms and containers more evident.

@John Constantine 2015-11-26 17:51:23

@MSN Why do we need != vector.end() at end to check for the element ? Doesnt find(vector.begin(), vector.end(), item) itself suffice to find the element

@Pascal Engeler 2016-01-14 16:50:56

@bobobobo : The reason why the find() function is not a member of vector is that it is inefficient. When an object of the STL has a member, that means it is a useful, efficient method; it suggests that you should use it. Since find() can not be implemented efficiently for a vector, it is not a member of vector, and the suggestion is that you use a different container if you need to use find() operations. It has nothing to do with the STL being 'badly designed' as suggested in other comments.

@MikeMB 2016-06-08 22:00:29

@PascalEngeler: I'd say, It's not so much about whether the operation is efficent or not, but about whether direct access to the internal data structure allows a more efficent implementation of the algrithm than the generic one, which uses iterators.

@Ap31 2016-09-13 08:48:33

@Claudiu in c++ you can use whatever syntax you like, just takes a page of the ugliest code and voilà

@Claudiu 2016-09-13 16:00:47

@ap31: that's true, but when I use code like that in production people yell at me :(

@Ap31 2016-09-13 16:11:21

@Claudiu so true

@Kai Petzke 2019-02-11 22:26:58

The error message from GCC/GXX for forgetting to #include the <algorithm> header when using std::find has even gotten worse: error: cannot bind non-const lvalue reference of type ‘__gnu_cxx::__normal_iterator<const int*, std::vector<int> >&’ to an rvalue of type ‘__gnu_cxx::__normal_iterator<const int*, std::vector<int> >’

@Arun 2019-03-08 06:09:54

I have std::vector<std::any> datatype. how to use std::find for vector of any type?

@Pavan Chandaka 2019-03-26 19:23:26

(C++17 and above):

can use std::search also

This is also useful for searching sequence of elements.

#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;
}

Also there is flexibility of passing some search algorithms. Refer here.

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

@Moises Rojo 2018-04-11 12:10:35

Using Newton C++ it's easier, self-documented and faster than with std::find because of return a bool directly.

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

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

I think it's obvious what the functions do.

include <newton/algorithm/algorithm.hpp>

if ( newton::exists_linear(first, last, value) )
   do_this();
else
   do_that();

@Ako 2018-10-07 07:28:07

Link does not work.

@Martin Broadhurst 2016-02-11 21:38:51

Here's a function that will work for any Container:

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();
}

Note that you can get away with 1 template parameter because you can extract the value_type from the Container. You need the typename because Container::value_type is a dependent name.

@Andy Krouwel 2016-11-02 12:01:34

Note that this is sometimes a bit too broad - it'd work for std::set for example, but give terrible performance compared to the find() member function. I've found it best to add a specialisation for containers with a faster search (set/map, unordered_*)

@m-sharp 2009-02-20 22:06:50

Use find from the algorithm header of stl.I've illustrated its use with int type. You can use any type you like as long as you can compare for equality (overload == if you need to for your custom class).

#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;
}

@Éric Malenfant 2009-02-20 22:12:29

Depending on the OP's needs, find_if() could also be appropriate. It allows to search using an arbitrary predicate instead of equality.

@Frank 2009-02-20 22:19:36

Oops, saw your comment too late. The answer I gave also mentions find_if.

@Mikhail 2016-09-27 16:02:37

With boost you can use any_of_equal:

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

bool item_present = boost::algorithm::any_of_equal(vector, element);

@Bin Feng 2012-11-23 08:58:39

If your vector is not ordered, use the approach MSN suggested:

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

If your vector is ordered, use binary_search method Brian Neal suggested:

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

binary search yields O(log n) worst-case performance, which is way more efficient than the first approach. In order to use binary search, you may use qsort to sort the vector first to guarantee it is ordered.

@Jason R. Mick 2013-08-16 01:57:14

Don't you mean std::sort? qsort is very inefficient on vectors.... see: stackoverflow.com/questions/12308243/…

@BillT 2017-03-31 14:07:02

Binary search will perform better for larger containers, but for small containers a simple linear search is likely to be as fast, or faster.

@Valdemar_Rudolfovich 2016-05-13 08:57:50

Another sample using C++ operators.

#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!");
  }
}

@Leon 2016-06-08 16:13:01

I wouldn't recommend abusing operator overloading in such a way.

@Valdemar_Rudolfovich 2016-06-10 12:34:20

Leon, I agree with you, semantically it isn't correct. I use it to make unit tests more clearly.

@Deqing 2015-08-11 04:15:57

In C++11 you can use any_of. For example if it is a vector<string> v; then:

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

@andreee 2019-04-30 07:50:23

bind1st and bind2nd are deprecated since C++11 and completely removed in C++17. Use bind with placeholders and/or lambdas instead.

@Aditya 2015-03-11 10:00:12

You can use count too. It will return the number of items present in a vector.

int t=count(vec.begin(),vec.end(),item);

@Camille Goudeseune 2015-08-16 20:27:27

find is faster than count, because it doesn't keep on counting after the first match.

@TankorSmash 2014-06-15 00:36:20

You can use the find function, found in the std namespace, ie std::find. You pass the std::find function the begin and end iterator from the vector you want to search, along with the element you're looking for and compare the resulting iterator to the end of the vector to see if they match or not.

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

You're also able to dereference that iterator and use it as normal, like any other iterator.

@user3157855 2014-01-26 17:55:40

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;
}

@Andy Krouwel 2013-09-04 16:34:07

I use something like this...

#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

...as that way it's actually clear and readable. (Obviously you can reuse the template in multiple places).

@Erik Aronesty 2015-03-03 15:36:52

and you can make it work for lists or vectors by using 2 typenames

@Martin Broadhurst 2016-02-11 21:40:34

@ErikAronesty you can get away with 1 template argument if you use value_type from the container for the element type. I've added an answer like this.

@Gank 2013-05-31 13:55:53

If you wanna find a string in a vector:

    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));

@Brian Neal 2009-02-20 22:26:14

As others have said, use the STL find or find_if functions. But if you are searching in very large vectors and this impacts performance, you may want to sort your vector and then use the binary_search, lower_bound, or upper_bound algorithms.

@Stephen Edmonds 2009-07-08 19:54:45

Good answer! Find is always o(n). lower_bound is o(log(n)) if used with random-access iterators.

@liori 2014-06-15 00:48:07

Sorting is O(nlogn) though, so it's worth only if you're doing more than O(logn) searches.

@Brian Neal 2014-06-17 16:24:40

@liori True it depends on your usage patterns. If you only need to sort it once, then repeatedly do many searches it can save you.

@Swapnil B. 2018-03-11 18:17:51

@Brian Neal, sorting a large vector is worth if there has to be many element searches on it. Sorting will be O(nlogn) and O(n) will be better if one has to find an element only once :)

@TrungTN 2012-04-28 15:29:48

You can try this 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()
}

@David Thornley 2009-02-20 22:42:36

Bear in mind that, if you're going to be doing a lot of lookups, there are STL containers that are better for that. I don't know what your application is, but associative containers like std::map may be worth considering.

std::vector is the container of choice unless you have a reason for another, and lookups by value can be such a reason.

@Renze de Waal 2009-02-20 22:49:20

Even with lookups by value the vector can be a good choice, as long as it is sorted and you use binary_search, lower_bound or upper_bound. If the contents of the container changes between lookups, vector is not very good because of the need to sort again.

@Frank 2009-02-20 22:18:34

Use the STL find function.

Keep in mind that there is also a find_if function, which you can use if your search is more complex, i.e. if you're not just looking for an element, but, for example, want see if there is an element that fulfills a certain condition, for example, a string that starts with "abc". (find_if would give you an iterator that points to the first such element).

Related Questions

Sponsored Content

25 Answered Questions

[SOLVED] What is the easiest way to initialize a std::vector with hardcoded elements?

16 Answered Questions

[SOLVED] What is the difference between const int*, const int * const, and int const *?

24 Answered Questions

[SOLVED] Image Processing: Algorithm Improvement for 'Coca-Cola Can' Recognition

11 Answered Questions

[SOLVED] How do I erase an element from std::vector<> by index?

  • 2009-05-17 17:59:36
  • dau_man
  • 638959 View
  • 437 Score
  • 11 Answer
  • Tags:   c++ stl vector erase

18 Answered Questions

[SOLVED] Concatenating two std::vectors

15 Answered Questions

2 Answered Questions

[SOLVED] How to initialize a vector in C++

3 Answered Questions

[SOLVED] check if a std::vector contains a certain object?

  • 2010-08-10 15:52:47
  • jmasterx
  • 380567 View
  • 229 Score
  • 3 Answer
  • Tags:   c++ vector

4 Answered Questions

[SOLVED] Appending a vector to a vector

  • 2010-03-31 09:33:02
  • sub
  • 459382 View
  • 588 Score
  • 4 Answer
  • Tags:   c++ stl vector

3 Answered Questions

[SOLVED] Finding an item in std::vector

  • 2015-11-26 17:57:48
  • John Constantine
  • 121 View
  • -4 Score
  • 3 Answer
  • Tags:   c++ vector std

Sponsored Content