May 23

Searching for elements in an STL container is a common task. There are several ways to accomplish this. Let’s have a look at some of them.

Suppose we have a collection of elements in an STL container. The element type is defined as a simplified phonebook entry, as follows:

struct Entry
{
    Entry( const string& n, const string& p ) : name( n ), phoneNum( p ) {}

    std::string name;
    std::string phoneNum;
};

We then push some entries into a container, e.g. a list, like follows:

std::list<Entry> phonebook;

phonebook.push_back( Entry( "James Bond", "123" ) );
phonebook.push_back( Entry( "Felix Leiter", "456" ) );
phonebook.push_back( Entry( "Vesper Lynd", "789" ) );

We’d then like to look up the phone number of a contact. We know the contact’s name, so we can search it as follows using a for loop and an iterator:

std::string searchFor = "James Bond";
std::list<Entry>::const_iterator iter = phonebook.begin();

for ( ; iter != phonebook.end(); ++iter )
{
    if ( iter->name == searchFor )
    {
        break;  // No need to look any further
    }
}

if ( iter != phonebook.end() )
{
    std::cout << "Call " << searchFor << " at " << iter->phoneNum << endl;
}

Quite simple. We could also make this into a function, and call it whenever we need to seach for a number:

string GetNumber( const std::list<Entry>& phonebook, const string& searchFor )
{
    std::list<Entry>::const_iterator iter = phonebook.begin();

    for ( ; iter != phonebook.end(); ++iter )
    {
        if ( iter->name == searchFor )
        {
            break;  // No need to look any further
        }
    }

    return iter->phoneNum;
}

There is also a more elegant way; we can write a comparison operator that returns true if the given Entry matches a specified std::string, and use it with the STL's find() algorithm. For the purposes of this example, it doesn't matter if the operator is a member operator or a global one. Here's the global version:

bool operator==( const Entry& e, const string& n )
{
    if ( e.name == n )
    {
        return true;
    }

    return false;
}

Make sure you have the parameters so that the container element type is on the left side, and the comparison argument (i.e. the third parameter to find()) is on the right side; this is what the algorithm expects.

Armed with this function, we are able to use the find() algorithm (remember to #include <algorithm>) to do our bidding:

std::string searchFor = "Vesper Lynd";

std::list<Entry>::const_iterator iter =
    std::find( phonebook.begin(), phonebook.end(), searchFor );

if ( iter != phonebook.end() )
{
    std::cout << "Call " << searchFor << " at " << iter->phoneNum << endl;
}

The find() algorithm compares each element of the specified range (between begin() and end(), as specified above) against the third argument, which happens to be the search string. Given that we now have a comparison operator taking an Entry struct and an std::string defined, the compiler calls the operator for each element in the range. The find() terminates either when the comparison returns true, or when the iterator position specified as the second argument to the algorithm is reached, i.e. phonebook.end().

You can also use find_if() with a function object as a search criterion. Function objects have also much more powerful features than mere functions, e.g. the ability to maintain state between invocations, but for this example we'll use one just as a simple comparison critetion. Let's have a look:

class CompPred : public binary_function<Entry, std::string, bool>
{
public:
    bool operator()( const Entry& e, const std::string& s ) const
    {
        if ( e.name == s )
        {
            return true;
        }

        return false;
    }
};

Here we derive a class from binary_function, and add a function call operator (operator()). The template parameters to the base class are two of the argument types (here Entry and std::string), and a return type (bool). What we're doing here is basically a template specialization of the binary_function class template. We then use the Entry and std::string types as parameters for the function call operator, akin to what we did with operator== above.

We can then do the search using a slightly modified version of the previously presented code:

std::string searchFor = "Vesper Lynd";

std::list::const_iterator iter =
    std::find_if( phonebook.begin(),
                  phonebook.end(),
                  bind2nd( CompPred(), searchFor ) );

if ( iter != phonebook.end() )
{
    std::cout << "Call " << searchFor << " at " << iter->phoneNum << endl;
}

Note the use of the find_if() algorithm. It takes as the third argument a pointer to a function or function object derived from unary_function. The bind2nd() adapter takes as parameters a function object and the search argument. We need the adapter in order to convert a binary function (taking two arguments) into a unary function (taking a single argument).

This post has droned on for quite some time, so I'll cut this short. There are loads of stuff I deliberately left unexplained here, e.g. why the function object's operator() must be declared const, function objects and function adapters, and template specializations, but I'll save those for another time, my dear imaginary readers.

preload preload preload