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

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

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

@underscore_d 2020-07-01 16:09:08

Why would you take a pointer and risk users passing a nullptr that you don't handle? There's simply no need. Also, you copy the T what, which could be expensive and is unnecessary work. Both arguments should be const references instead of what they currently are. Finally, I don't know why people ever write if (condition) return true; else return false; when they could just write return condition;.

@user3157855 2020-07-02 17:56:42

Thanks for the suggestion, I wasn't experienced that much at the time and switched to Java meanwhile :) I updated the comment, let me know if it's better or if there is still something to fix.

@underscore_d 2020-07-03 07:57:43

Now that you receive references instead of pointers, you need to use . instead of ->.

@user3157855 2020-07-03 08:23:48

Oh, ye I forgot C++ a little, thanks!

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

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

@Pascal Laferrière 2019-10-28 15:23:52

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

@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'

@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 :(

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

@tectonicfury 2020-02-20 03:44:34

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

@James Mart 2020-06-29 18:50:06

@swalog 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.

@swalog 2020-06-29 18:57:01

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

@James Mart 2020-07-01 14:27:00

@swalog 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

@swalog 2020-07-01 14:29:30

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.

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

@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_*)

@underscore_d 2020-07-01 16:06:34

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.

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

@spiralmoon 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.

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

@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

29 Answered Questions

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

10 Answered Questions

[SOLVED] How to sum up elements of a C++ vector?

  • 2010-07-11 03:59:34
  • Prasoon Saurav
  • 319924 View
  • 246 Score
  • 10 Answer
  • Tags:   c++ stl vector

25 Answered Questions

[SOLVED] Concatenating two std::vectors

8 Answered Questions

[SOLVED] How to convert a std::string to const char* or char*?

15 Answered Questions

18 Answered Questions

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

13 Answered Questions

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

  • 2009-05-17 17:59:36
  • dau_man
  • 786842 View
  • 526 Score
  • 13 Answer
  • Tags:   c++ stl vector erase

24 Answered Questions

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

Sponsored Content