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,
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,
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
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