Finding an element in a container (std::vector, std::list, etc.)

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!