Finding an element in a list

Often you need to search through an array or list to find a specific element and of course you need this search to be as fast and efficient as possible. One of the best ways to do this is using a binary predicate function.

A binary function is a function object (which are also called Functors) and is any object which can be called as if it was a function. Depending on your language and platform of choice, Function objects are also known as callback functions, function pointers and delegates (.NET). Generally, there are three types of function objects:

  1. Generators – function with no arguments
  2. Unary Functions – function with one argument
  3. Binary Functions – functions with two arguments

A function object which takes one parameter (i.e. unary function) and returns a bool are treated as a special case and are  called Predicate functions.

How do we use it? Say we have a simple data structure called ContactData to represent a Contact in an Address book as shown in the code snippet below. We also define a predicate function called FindAContact. Now we need to use this predicate function and define another function called  findContact. The findContact function in turn uses find_if.  find_if takes three parameters, the start of the iterator, the last element and the predicate to use. It returns the first iterator it finds in a given range for which the predicate holds. If no matches are found then  the last element in the iterator is returned.

We also need to ensure we have the relevant includes for this to compile and link properly hence include’s below.

The code snippet below shows all that we have discussed.

#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

//Simple data structure
struct ContactData {
	string name;
	string addr1;
	string addr2;
	string addr3;
	string city;
	string postcode;
	string country;
	int workPhone;
	int homePhone;
	int mobilePhone;
	string workEmail;
	string homeEmail;
};

//I am lazy, create a typedef for the vector
typedef vector<ContactData> ContactDataArray;

// predicate function for rapidly searching the Contact data array
struct FindAContact: public std::binary_function<ContactData, std::string, bool>
{
	bool operator() (const ContactData &contact, const string &name) const
	{
		return (contact.name == name);
	}
};

//If a contact is find it returns that; else returns the iterator's last element
ContactData Contact::findContact(string name)
{
	ContactDataArray::iterator it = find_if(addressBook.begin(),
						addressBook.end(),
						std::bind2nd(FindAContact(), name)
					);

	return *it;
}

Published by

Amit Bahree

This blog is my personal blog and while it does reflect my experiences in my professional life, this is just my thoughts. Most of the entries are technical though sometimes they can vary from the wacky to even political – however that is quite rare. Quite often, I have been asked what’s up with the “gibberish” and the funny title of the blog? Some people even going the extra step to say that, this is a virus that infected their system (ahem) well. [:D] It actually is quite simple, and if you have still not figured out then check out this link – whats in a name?

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.