ChatGPT解决这个技术问题 Extra ChatGPT

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

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();
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
@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.
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.
A superb answer present on a duplicate question: stackoverflow.com/a/3451045/472647
If you're going to search multiple times for different numbers, a hash table would be more efficient.

A
Anselmo GPP

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

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.
Don't forget to #include <algorithm> or else you might get very strange errors like 'can't find matching function in namespace std'
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.
@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
@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().
B
Brian Neal

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.


Good answer! Find is always o(n). lower_bound is o(log(n)) if used with random-access iterators.
Sorting is O(nlogn) though, so it's worth only if you're doing more than O(logn) searches.
@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.
@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 :)
Be wary this may play havoc with your branch prediction.
h
hfossli

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.


Don't you mean std::sort? qsort is very inefficient on vectors.... see: stackoverflow.com/questions/12308243/…
Binary search will perform better for larger containers, but for small containers a simple linear search is likely to be as fast, or faster.
@BillT: Wouldn't a decent binary search implementation switch itself to linear search below some threshold number of elements?
i
isanae

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

Depending on the OP's needs, find_if() could also be appropriate. It allows to search using an arbitrary predicate instead of equality.
Oops, saw your comment too late. The answer I gave also mentions find_if.
L
L. F.

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

bind1st and bind2nd are deprecated since C++11 and completely removed in C++17. Use bind with placeholders and/or lambdas instead.
Why use std::any_of() when we have std::find()?
If the purpose is to check for membership only, why use std::find() when we have std::any_of?
C
Community

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


and you can make it work for lists or vectors by using 2 typenames
@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.
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();
M
Martin Broadhurst

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.


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_*)
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.
What do you think about @PascalLaferrière 's approach of deducing the value type?
D
David Thornley

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.


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.
F
Frank

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


M
Mikhail

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

T
TrungTN

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

T
TankorSmash

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.


P
Pang

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

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

find is faster than count, because it doesn't keep on counting after the first match.
u
user3157855
template <typename T> bool IsInVector(const T & what, const std::vector<T> & vec)
{
    return std::find(vec.begin(),vec.end(),what)!=vec.end();
}

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;.
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.
Now that you receive references instead of pointers, you need to use . instead of ->.
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.
P
Pascal Laferrière

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

Please consider separating the value-type-deduction logic into its own trait, e.g. template <typename Container> struct value_type { ... etc. ... }
@einpoklum 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...}?
G
Gank

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

std::find is just fine in this case, no need for the predicate object.
P
Pavan Chandaka

(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


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

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