How to find an item in a std::vector?

Question

All I wanna 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();

Answer 1

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

Answer 2

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 _tmain(int argc, _TCHAR* argv[])
{ 
 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;
}

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

The brute force approach (again presuming int as the stored type):

int value_to_find;
vector<int> cont;
vector<int>::const_iterator found = cont.find(value_to_find);
if (found != cont.end()) {
    do_this();
} else {
    do_that();
}

If you're doing many lookups in large vectors, this can be inefficient. You may want to cache your results in order to avoid doing the same search twice (assumes int as the stored type):

int value_to_find;
vector<int> cont;                         // main container
map<int, size_t> contPos;                 // position cache

// first see if the value is in cache
map<int, size_t>::const_iterator foundCache = contPos.find(value_to_find);
if (foundCache != contPos.end()) {
    do_this();
}
// not in cache, now do brute force search
vector<int>::const_iterator found = cont.find(value_to_find);
if (found != cont.end()) {
    // cache the value with its position
    contPos[value_to_find] = found - cont.begin();

    do_this();
} else {                                  // in neither
    do_that();
}