Search an Element in List in C++

In this article we will discuss different ways to find or search a given element in the list.

std::list does not provide ant find() or contains() method. So, if we want to search for an element in list or check if an element exists in std::list, then we not to write some code for it i.e.

Logic Used to find a given element in list,

• Iterate over all the elements of list
  • For each element check if this element is equal to given element

Suppose we have a list of strings i.e.

std::list<std::string> listOfStrs = { "is", "of",
					"the", "Hi",
					"Hello", "from" };

Now if we want to check if ‘the’ exists in this list or not. Let’s see different ways to do this,

Searching an element in std::list using std::find()

std::find

STL Provides an algorithm std::find() i.e.

template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);

In std::find() you can pass two iterators and a value. It will iterate all the elements between 2 given iterators and compare the given val with each one.
If any match is found, then it will immediately return that iterator, else it returns the iterator pointing to end of list.

Let’s see how to find a string in std::list using std::find

// Create a list Iterator
std::list<std::string>::iterator it;

// Fetch the iterator of element with value 'the'
it = std::find(listOfStrs.begin(), listOfStrs.end(), "the");

// Check if iterator points to end or not
if(it != listOfStrs.end())
	std::cout<<"'the' exists in list "<<std::endl;

Complete example is as follows,

#include <iostream>
#include <list>
#include <string>
#include <algorithm>

int main()
{
	std::list<std::string> listOfStrs = {
								"is", "of",
								"the", "Hi",
								"Hello", "from" };

	// Check if an element exists in list

	// Create a list Iterator
	std::list<std::string>::iterator it;

	// Fetch the iterator of element with value 'the'
	it = std::find(listOfStrs.begin(), listOfStrs.end(), "the");

	// Check if iterator points to end or not
	if(it != listOfStrs.end())
	{
		// It does not point to end, it means element exists in list
		std::cout<<"'the' exists in list "<<std::endl;
	}
	else
	{
		// It points to end, it means element does not exists in list
		std::cout<<"'the' does not exists in list"<<std::endl;
	}

}

Output:

'the' exists in list

Generic contains() method for std::list

Let’s create a generic function template that checks for the given value of type T in std::list<T>.

/*
 * Generic function to find if an element of any type exists in list
 */
template <typename T>
bool contains(std::list<T> & listOfElements, const T & element)
{
	// Find the iterator if element in list
	auto it = std::find(listOfElements.begin(), listOfElements.end(), element);
	//return if iterator points to end or not. It points to end then it means element
	// does not exists in list
	return it != listOfElements.end();
}

It will work for any type of list i.e. list of int, string etc.

Using generic contains with list of int,

std::list<std::string> listOfStrs =
{ "is", "of", "the", "Hi", "Hello", "from" };

// Check if an element exists in list
bool result = contains(listOfStrs, std::string("is"));

Using generic contains with list of string,

// List of ints
std::list<int> listOfNum =
{ 1, 2, 3, 4, 6, 7, 8 };

// Check if an element exists in list
result = contains(listOfNum, 3);

Complete example is as follows,

#include <iostream>
#include <list>
#include <string>
#include <algorithm>

/*
 * Generic function to find if an element of any type exists in list
 */
template<typename T>
bool contains(std::list<T> & listOfElements, const T & element)
{
	// Find the iterator if element in list
	auto it = std::find(listOfElements.begin(), listOfElements.end(), element);
	//return if iterator points to end or not. It points to end then it means element
	// does not exists in list
	return it != listOfElements.end();
}

int main()
{
	std::list<std::string> listOfStrs =
	{ "is", "of", "the", "Hi", "Hello", "from" };

	/* Use the same generic function with list of Strings */

// Check if an element exists in list
	bool result = contains(listOfStrs, std::string("is"));
	std::cout << result << std::endl;

	// Check if an element exists in list
	result = contains(listOfStrs, std::string("day"));

	std::cout << result << std::endl;

	/* Use the same generic function with list of int */

	// List of ints
	std::list<int> listOfNum =
	{ 1, 2, 3, 4, 6, 7, 8 };

	// Check if an element exists in list
	result = contains(listOfNum, 3);
	std::cout << result << std::endl;

	// Check if an element exists in list
	result = contains(listOfNum, 3);
	std::cout << result << std::endl;

}

Output:

1
0
1
1

To compile the above examples in Linux use following command,

g++ –std=c++11 example.cpp