check if a std::vector contains a certain object?

Question

Is there something in <algorithm> which allows you to check if a std:: container contains something? Or, a way to make one, for example:

if(a.x == b.x && a.y == b.y)
return true;

return false;

Can this only be done with std::map since it uses keys?

Thanks

If it contains something specific, or just of it's not empty? — James Curran, Aug 10 '10 at 15:54
Which C++ reference are you using? And the header is called `` - note no .h. — , Aug 10 '10 at 15:54
if the container contains a custom struct, then you'll need to implement `operator==` to compare them; then `std::find` will work. — Mike Seymour, Aug 10 '10 at 16:13
Like answered in the [duplicate](https://stackoverflow.com/q/571394/651937), I think the most elegant is to use [`boost::algorithm::any_of_equal`](https://stackoverflow.com/a/39729364/651937). — ingomueller.net, Jul 25 '18 at 10:58

score 683 · Accepted Answer · edited Jun 14 '15 at 13:49

683

Checking if v contains the element x:

#include <algorithm>

if(std::find(v.begin(), v.end(), x) != v.end()) {
    /* v contains x */
} else {
    /* v does not contain x */
}

Checking if v contains elements (is non-empty):

if(!v.empty()){
    /* v is non-empty */
} else {
    /* v is empty */
}

edited Jun 14 '15 at 13:49

E-rich

9,243
11
48
79

answered Aug 10 '10 at 15:57

You

22,800
3
51
64

33

what if x is the last element in v? – David Carpenter Dec 05 '12 at 01:38
124

David, end() points to one past the last element, so it all works out. – Mark Beckwith Jan 14 '13 at 20:08
4

Does this account for numerical tolerance when trying to determine if a double is in the vector? – Nicholas Hamilton Aug 20 '15 at 07:18
18

@NicholasHamilton: No, it uses `operator==`. If you need to account for numerical tolerance, use [`std::find_if`](http://en.cppreference.com/w/cpp/algorithm/find) and supply a suitable predicate. – You Aug 20 '15 at 18:38
Isn’t find exclusive of the last element? – Darnoc Eloc Jun 30 '20 at 06:26
1

@DarnocEloc: No. – You Aug 06 '20 at 07:58
1

june 2015. my mama was alive back then and I was doing my post doc. mann time passed so fast – Hani Gotc Dec 17 '21 at 22:15

score 136 · Answer 2 · edited Oct 31 '16 at 00:42

136

If searching for an element is important, I'd recommend std::set instead of std::vector. Using this:

std::find(vec.begin(), vec.end(), x) runs in O(n) time, but std::set has its own find() member (ie. myset.find(x)) which runs in O(log n) time - that's much more efficient with large numbers of elements

std::set also guarantees all the added elements are unique, which saves you from having to do anything like if not contained then push_back()....

edited Oct 31 '16 at 00:42

Bertrand Martel

42,756
16
135
159

answered Aug 10 '10 at 16:11

AshleysBrain

22,335
15
88
124

1

Great!!! I'm writing a lexer. Sets will be much better than vectors. Does `set` have a `count` method like `map`? I also want to be able to get the index of the element in a set. – IAbstract Apr 03 '15 at 12:30
4

Excellent information! Thank you for both answering the straight question and providing an additional solution. – CodeMouse92 Jun 18 '15 at 03:10
26

This is bad advice. If performance is important, profile. There is no guarantee whatsoever that complexity analysis has anything to say about your specific problem. – Andreas Haferburg Sep 02 '16 at 11:24
2

It depends on the number of elements. std::set's lookup characteristics work great for conainers with high number of elements at the cost of data locality. You must perform performance analysis (eg. profiling) to decide how high is high enough to switch from a vector data structure to a set data structure. – Burak Arslan Oct 03 '16 at 07:30
@AndreasHaferburg I'm a complete novice in profiling and performance, but if a `set` works like a `vector` in a worst case scenario isn't better to use `` just to avoid including `` that afaik adds too much overhead just to use `find()` .I'm talking about unsorted data. – Segmentation Apr 01 '19 at 08:47
4

@Segmentation The O(n) notation is not about worst cases. AFAIK, `set` doesn't work like a `vector` at all. Most `set` implementations use red-black trees, which have a significant overhead. I don't know what you mean by a header adding overhead. Overhead usually refers to runtime overhead. The best use cases of `set` are "I'm feeling lazy and don't want to think about it," and "I need to get this done quickly." If you care about performance, you need to profile. `unordered_set` might be worth trying. – Andreas Haferburg Apr 01 '19 at 09:41
1

@AndreasHaferburg Maybe the term overhead wasn't the right choice of words. Including ``, a "heavy" header just to use `find()`, as a project gets bigger will probably affect compile times etc. I know that I may be way out of subject here. – Segmentation Apr 01 '19 at 11:00
Be aware of the complexity of all other operations on `std::set`s and `std::vector`s. Appending to a vector is O(1) (if not reallocating). Inserting into a set is O(log n). Inserting into an `std::unordered_set` is O(1) and will never reallocate. Suchs oversights is one of the important reasons why profiling is important! – Jupiter Apr 10 '19 at 23:03
For compiling times the same thing applies. When this really becomes an issue then know that there are plenty of things you can optimize. Things like multi-core compilation, proper use of forward declarations, proper software design to reduce compilation dependencies, precompiled headers, and, sometimes and if applicable, the use of explicit template instantiations in cpp files. I like to always create an `fwd_decl.hpp` file in every project that contains all forward declarations of all classes, structs etc and them simply include them in all other header files without a second thought. – Jupiter Apr 10 '19 at 23:07
I agree with @AndreasHaferburg: It will give you only a hint. Also the constants could be much worse and can not be foreseen easily without profiling/benchmarking. – stephanmg Aug 10 '20 at 10:13
Note that I wrote a performance test of vectors vs. sets, storing enum values and ensuring uniqueness before push_back into the vector. Looping n times for all values of n from 100 to 1 million, vectors were consistently approximately twice as fast as sets. This was on a relatively modern Mac but running inside a Linux docker container. However, they're very fast. 1 million loops required 62 milliseconds for vectors and 137 milliseconds for sets. – Joseph Larson Nov 16 '20 at 16:11

score 15 · Answer 3 · edited May 23 '17 at 12:34

15

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

You'll also need to ensure you've implemented a suitable operator==() for your object, if the default one isn't sufficient for a "deep" equality test.

edited May 23 '17 at 12:34

Community

1
1

answered Aug 10 '10 at 15:56

NeilDurant

2,082
2
14
14

1

I normally wouldn't implement a custom `operator==()` for my class to just be able to use `std::find()` once or twice. I would only do that if it actually makes sense to add that override to the public interface of your class. Needing to be able to use `std::find()` doesn't justify that. Furthermore, what if you need to do `std::find()` twice but need to compare your objects in a different way? Like on a different property? – Jupiter Apr 10 '19 at 22:55
if you are worried to implement the `operator==`, then I would recommend using `std::find_if`, then you could have re-usable predicates for your different criteria cases – yano Nov 21 '19 at 23:57

check if a std::vector contains a certain object?

3 Answers3

Linked