There is a time during the usage of a c++ class std::vector, std::list and others, when you need to find an element in the container. For instance, you want to create a collection of numbers (let’s suppose you have stored them in std::vector) and you have some function that checks for the given element in a container. Now you might need to find out whether some number exists in the std::vector class.
Finding an element in a container or array is quite a common task in programming, yet some programmers don’t know the number of ways it can be done. <algorithm> header provides several useful functions for manipulating containers, including a function std::find for getting the iterator of a given range. Through it, you can easily find whether an element in a container exists or not. It takes three parameters: First iterator, Last iterator and the element that you want to find in a container.
Read also: How to optimize a sort algorithm
C++ vector or std::vector find example:
int main() { std::vector<int> numbers; // this can be std::list, std::deque etc. numbers.push_back(10); numbers.push_back(20); auto it = std::find(numbers.begin(), numbers.end(), 10); if (it != numbers.end()) { // Found } else { // Not Found } }
If your vector is ordered (if not, then do so with std::sort), then you can use std::binary_search which yields O(log n) worst-case performance, which is way more efficient than the first approach. For sorting elements in a std::vector, you should use std::sort and NOT std::qsort, because the latter is quite expensive for std::vector. Note that if you want to find an element in a container at several times in your program, then you are better off using std::list, because it doesn’t need to be sorted and thus searching is more efficient. Following is its usage:
int main() { std::vector<int> numbers; numbers.push_back(10); numbers.push_back(20); std::sort(numbers.begin(), numbers.end()); // we need to sort it, as we are using std::vector auto it = std::binary_search(numbers.begin(), numbers.end(), 10); if (it) { // Found } else { // Not Found } }
As you can see, how easy it is to find an element through std::find function. Another easy way to find an element in a container is by using std::find_if alongside with the lambda feature of C++11. It finds an element in a container with a given condition; if you want to get the first odd/even number in your container that holds numbers, you can define the function for it and then pass it in its parameter. It takes three parameters: First iterator, Last iterator and the function that defines the condition. Following is an example of its usage:
bool IsOdd(int i) { return ((i%2)==1); } int main() { std::vector<int> numbers; numbers.push_back(10); numbers.push_back(20); numbers.push_back(25); auto it = std::find_if(numbers.begin(), numbers.end(), IsOdd); // this can be also written using lambda: std::find_if(numbers.begin(),numbers.end(),[](int i){return ((i%2)==1); }); std::cout << "The first odd value is " << *it << '\n'; }
Now you can decide, which way is better suited for your case.
Is there any other way that you know, through which an element in a container can be found? Please let me know in the comments section below!