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();
Related Questions
Sponsored Content
25 Answered Questions
[SOLVED] What is the easiest way to initialize a std::vector with hardcoded elements?
- 2010-02-10 10:55:33
- Agnel Kurian
- 721604 View
- 547 Score
- 25 Answer
- Tags: c++ vector initialization
18 Answered Questions
[SOLVED] Concatenating two std::vectors
- 2008-10-14 15:46:01
- yigal
- 276895 View
- 546 Score
- 18 Answer
- Tags: c++ vector stl concatenation stdvector
10 Answered Questions
23 Answered Questions
[SOLVED] Image Processing: Algorithm Improvement for 'Coca-Cola Can' Recognition
- 2012-04-16 04:23:16
- Charles Menguy
- 159326 View
- 1487 Score
- 23 Answer
- Tags: c++ algorithm image-processing opencv
10 Answered Questions
15 Answered Questions
[SOLVED] Difference between private, public, and protected inheritance
- 2009-05-13 20:47:07
- user106599
- 608407 View
- 885 Score
- 15 Answer
- Tags: c++ inheritance encapsulation access-specifier c++-faq
2 Answered Questions
[SOLVED] How to initialize a vector in C++
- 2012-01-18 07:22:46
- Md Faisal
- 600549 View
- 184 Score
- 2 Answer
- Tags: c++ arrays vector declaration
17 comments
@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.
I think it's obvious what the functions do.
@Ako 2018-10-07 07:28:07
Link does not work.
@Martin Broadhurst 2016-02-11 21:38:51
Here's a function that will work for any Container:
Note that you can get away with 1 template parameter because you can extract the
value_type
from the Container. You need thetypename
becauseContainer::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_*)
@MSN 2009-02-20 22:00:50
You can use
std::find
from<algorithm>
:This returns a bool (
true
if present,false
otherwise). With your example:@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'@rajat 2012-10-18 13:06:13
What will this return ?
@MSN 2012-10-18 23:31:34
a
bool
. It's a drop in replacement (or initialization) ofitem_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 ofstd::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 usingfind()
on a vector at all, and second, thatvector.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 amap
orset
.@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 tostd::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 tostd::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 :(
@Ap31 2016-09-13 16:11:21
@Claudiu so true
@Kai Petzke 2019-02-11 22:26:58
The error message from GCC/GXX for forgetting to
#include
the<algorithm>
header when usingstd::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> >’
@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).
@É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
:@Think Recursively 2012-11-23 08:58:39
If your vector is not ordered, use the approach MSN suggested:
If your vector is ordered, use binary_search method Brian Neal suggested:
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.
@Valdemar_Rudolfovich 2016-05-13 08:57:50
Another sample using C++ operators.
@Leon 2016-06-08 16:13:01
I wouldn't recommend abusing operator overloading in such a way.
@Valdemar_Rudolfovich 2016-06-10 12:34:20
Leon, I agree with you, semantically it isn't correct. I use it to make unit tests more clearly.
@Deqing 2015-08-11 04:15:57
In C++11 you can use
any_of
. For example if it is avector<string> v;
then:@Aditya 2015-03-11 10:00:12
You can use count too. It will return the number of items present in a vector.
@Camille Goudeseune 2015-08-16 20:27:27
find
is faster thancount
, 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 thestd
namespace, iestd::find
. You pass thestd::find
function thebegin
andend
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.You're also able to dereference that iterator and use it as normal, like any other iterator.
@user3157855 2014-01-26 17:55:40
@Andy Krouwel 2013-09-04 16:34:07
I use something like this...
...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:
@Brian Neal 2009-02-20 22:26:14
As others have said, use the STL
find
orfind_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 thebinary_search
,lower_bound
, orupper_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:
@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).