How to find out if an item is present in a std::vector?

Question

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

Listel

searching in a vector is very slow since you have to look at every single element of the vector so consider using a map if you're doing a lot of lookups – Dull

@naumcho: If the vector is sorted there's always binary search, as posted below. This makes it as fast as a map and if you're only storing values (not key/value maps) then it's going to use a lot less memory. – Wicked

maps are certainly not the best choice, but using set might be useful. If you need O(1) lookup time, hash_set is the way to go. – Hallucinosis

A superb answer present on a duplicate question: https://mcmap.net/q/55114/-check-if-a-std-vector-contains-a-certain-object-duplicate – Contestation

If you're going to search multiple times for different numbers, a hash table would be more efficient. – Moisten

The answer(s) to this question do not match the title. I strongly suggest to change the title so that people who seek the answers given will find them. It is not the fault of the person who asked the question of course, but now we have this situation... The most upvoted (and accepted) answers find the element anyway (and then check if they found it). So a better title would be "How to find an item in a std::vector, if it exists?" Or something like that. – Zettazeugma

Answer 1

You can use std::find from <algorithm>:

#include <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 an iterator to the first element found. If not present, it returns an iterator to one-past-the-end. With your example:

#include <algorithm>
#include <vector>

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

Interlocution

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

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

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. – Fortunate

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

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

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

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. – Poem

@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 – Insertion

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. – Byandby

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

@Byandby 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. – Aristotle

@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 ?? – Pavier

@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) – Insertion

@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(). – Moersch

@Poem 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. – Quicksand

@Interlocution 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 – Insolvency

@Poem : 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. – Disconnected

@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. – Epispastic

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

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

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> >’ – Quiz

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

@Poem So many differing programming paradigms all over the place make it difficult for newcomers. – Reichstag

@Moersch std::find does not require that the user searches the entire range. So for the member function to be equal, it would have to be: mvec.find(mvec.cbegin(), mvec.cend(), key) != mvec.cend() which isn't a particularly cleaner interface than the nonmember function. – Subadar

@James Mart: it's been a while, but looking at in now, I don't see how that is true, the implied usage being find with a single argument of element type as key, is already aware of its own range, and can stop on first match, if any. Said in a different way, the values you are suggesting should be passed, are already known in the called scope, so you can drop them and make the interface cleaner. – Moersch

@Moersch I'm just saying if you make the interface cleaner like that, then your member function no longer directly imitates std::find. std find intentionally takes iterators in to allow the user to define a subset of the total range to be searched – Subadar

Fair enough. However, the discussion was on the hypothetical overload that implicitly searches the whole range, and as such does not require range specifics. If, and whenever one wished to search on a range (that isn't the whole range), you'd use find, or a member function like what you mentioned. – Moersch

This sucks. There should be a std::vector::contains method. – Kries

@SebastianMach I understand, that std::vector::find() is not implemented, as it is not better than std::find(). The problem is, that a programmer, that upgrades a certain data structure from std::vector to std::multiset (or std::set) then has to walk through the code and update every place, where a find() is performed. It would be nice, if the APIs of std::(multi)set and std::vector would be as similiar as possible. – Quiz

This solution does not work for std::vector<std::shared_ptr...> and other pimpl expressions. Does anyone know how to make it work?? – Lazulite

The idea of OO comes from Heidegger, and is a concept of how humans perceive the world and organize information. OO design is about structuring code in a way which is easy for humans to understand. As such, container objects (like vector) should mimic the concept of containers in the real world. The fact that I have to say what type of objects a container can hold (the template parameter) doesn't match the real world, where containers can hold anything provided there's enough space. And since finding things in containers is a common thing to do, it should be part of the container interface. – Mathew

It's annoying to use one pattern for std::map which does have find, then a more clunky pattern for std::vector because it does not have find. Consistency between containers would be nice, – Broadus

Answer 2

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.

Orling

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

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

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

@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 :) – Jarietta

Be wary this may play havoc with your branch prediction. – Cyler

Try to use std::set<> together with find() indeed. Or use std::map<> depending on your needs. – Polack

Answer 3

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.

Kathe

Don't you mean std::sort? qsort is very inefficient on vectors.... see: #12308743 – Nertie

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

@BillT: Wouldn't a decent binary search implementation switch itself to linear search below some threshold number of elements? – Aurea

Answer 4

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

Spermophyte

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

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

Answer 5

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(), bind(equal_to<string>(), _1, item)))
   do_this();
else
   do_that();

Alternatively, use a lambda:

if (any_of(v.begin(), v.end(), [&](const std::string& elem) { return elem == item; }))
   do_this();
else
   do_that();

Pincer

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

Why use std::any_of() when we have std::find()? – Aurea

If the purpose is to check for membership only, why use std::find() when we have std::any_of? – Delgadillo

@Aurea std::find is only for C++20. Not all projects are using C++20 already. Don't think that's that easy to migrate big professional projects from one version to another. Believe me. – Riess

@Maf: Fair point, I was under the illusion it was older. – Aurea

@Riess what do you mean with "find is only for C++20" ? std::find has been part of C++ since forever. – Galvan

I'm so sorry einpoklum and @ABaumstumpf, I was wrong. std::find is also part of C++11. I made a mistake because my C++ compiler allowed me to use it without including <algorithm> – Riess

Answer 6

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

Magnific

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

@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. – Grattan

You are basically writing : if true return true else return false. The method can be one lined in : return std::find(Vec.begin(), Vec.end(), Element) != Vec.end(); – Nevins

Answer 7

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.

Grattan

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_*) – Magnific

Maybe one day they'll finally add this to the stdlib... instead of people having to ask how to reinvent such a tiny wheel over and over again. It's totally viable now that in C++20 we have ranges, so that could just be called Range rather than Container, and Bob's your uncle. – Ericaericaceous

What do you think about @PascalLaferrière 's approach of deducing the value type? – Aurea

Answer 8

From C++20, using ranges (#include <ranges>)

    //SAMPLE DATA
    std::vector<int> vecOfElements = { 2,4,6,8 };

    //DO SOMETHING IF 8 IN VECTOR
    if (std::ranges::find(vecOfElements, 8) != vecOfElements.end())
    {
        std::cout << "DO SOMETHING" << std::endl;
    }

Dori

Answer 9

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.

Aerometer

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. – Robbie

Answer 10

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

Botch

Answer 11

In C++23 we finally have the most obvious solution:

if (std::ranges::contains(vec, item))
   do_this();
else
   do_that();

Botch

Yeah - finally. Such a shame that the committee has been so resistant for so long to people suggesting we need just a "has" or "contains" function for containers. std::map only got contains with C++20, and no love for vector. – Galvan

Answer 12

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

Ibanez

Answer 13

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

Ullman

Answer 14

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.

Harquebus

Answer 15

template <typename T> bool IsInVector(const T & what, const std::vector<T> & vec)
{
    return std::find(vec.begin(),vec.end(),what)!=vec.end();
}

Tinfoil

If you want to adapt std::find() to be usable with containers, do it generically rather than for just a vector. And maybe call it find() or stdx::find() or something. – Aurea

This function is a less useful wrapper than std::ranges::contains. – Bolivar

Answer 16

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

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

Gall

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

Answer 17

I've personally used templates of late to handle multiple types of containers at once rather than deal only with vectors. I found a similar example online (can't remember where) so credit goes to whoever I've pilfered this from. This particular pattern seems to handle raw arrays as well.

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

Burlesque

Please consider separating the value-type-deduction logic into its own trait, e.g. template <typename Container> struct value_type { ... etc. ... } – Aurea

@Aurea I'm quite new to template logic and to be honest, I'm barely able to understand how this solution does its magic. Could you possible expand on the {...etc...}? – Croteau

Answer 18

(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

Dori

std::search is for searching for any of multiple values in a range; for a single value, there's no reason to use it. – Aurea

Answer 19

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

Jacquijacquie

std::find is just fine in this case, no need for the predicate object. – Aurea

Answer 20

Another way to do it is using std::count.

Example code:

#include <algorithm>
#include <vector>

void run_vector_contains_example() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    int item_to_find = 3;

    int count = std::count(vec.begin(), vec.end(), item_to_find);

    if (count > 0) {
        // item found in vector
    } else {
        // item not found in vector
    }
}

Admittedly, this method might be slower than std::find when dealing with large vectors.

Precede