STL list - how to find a list element by its object fields

Question

I have a list:

list<Unit *> UnitCollection;

containing Unit objects, which has an accessor like:

bool Unit::isUnit(string uCode)
{
    if(this->unitCode == uCode)
        return true;
    else
        return false;
}

How do I search my UnitCollection list by uCode and return the corresponding element (preferably and iterator).

In pseudo code it would look something like this:

for every item in my UnitCollection:
  if the unit.isUnit(someUnitIpass)
    do something
  else
    next unit

I have looked at the find() method, but i'm not sure you can pass a boolean method in instead of a searched item parameter if that makes sense.

Answer 1

Have a look at find_if.

If you can use boost, you can use it with boost::lambda.

namespace bl=boost::lambda;
std::find_if(...begin... , ...end... , bl::bind(&Unit::isUnit, *bl::_1, "code"))

or you can brew your own functor.

struct isUnitor // : public std::unary_function<Unit*, bool> -- this is only needed for the negation below
{
  string arg;
  isUnitor(const string& s) : arg(s) {}
  bool operator()(Unit* u) const { return u->isUnit(arg); }
};

std::find_if(...begin... , ...end... , isUnitor("code"))

or, if you want the index (for the negation, look here):

std::count_if(...begin... , ...end... , not1(isUnitor("code")))

Answer 2

You could have a look at find_if as jpalecek suggests, and then use distance to find the distance between the iterator returned from find_if and UnitCollection.begin(), and that distance should be the index of the element in the list.

And as for the predicate, you could write a function object like this:

struct predicate
{
    predicate( const std::string &uCode ) : uCode_(uCode) {}

    bool operator() ( Unit *u )
    {
        return u->isUnit( uCode_ )
    }
private:
    std::string uCode_;
};

And then use it like this:

predicate pred("uCode");
std::list<Unit*>::iterator i;
i = std::find_if( UnitCollection.begin(), UnitCollection.end(), pred );

Or at least I think that would be a way to do it.

Answer 3

An Insignificant Comment First

You might change your accessor function to the simpler form

return unitCode == uCode;

Now To What We're Here For

You're better off looking for the position of the element rather than its index. Getting an element from its index is an O(n) operation, whereas getting an element from its position is an O(1) operation. So, with the STL and a little help from boost::bind():

#include <algorithm>
#include <boost/bind.hpp>

// ...
std::string uCode("uCode to search for");
std::list<Unit*>::iterator pos = std::find_if(unitCollection.begin(),
                                              unitCollection.end(),
                                              boost::bind(&Unit::isUnit,
                                                          _1, uCode));

The STL does have std::mem_fun(), which, along with std::bind2nd() would give the same result. The problem is that mem_fun() only works with member functions that take no arguments. boost::bind() on the other hand is much more powerful, and does solve the problem here very nicely. You should expect it in the next standard, which should be here immediately after the Messiah arrives.

But If You Don't Have Boost

If don't already have boost in your project then you really, really should install it. If the standard library is C++'s wife, then Boost is C++'s young lover. They should both be there, they get along fine.

Having said that, you can extract the function into a standalone function object as Peter mentioned already:

struct has_uCode {
    has_uCode(cont std::string& uc) : uc(uc) { }
    bool operator()(Unit* u) const { return u->isUnit(uc); }
private:
    std::string uc;
};

Then, you can call std::find_if() like so:

std::list<Unit*>::iterator pos = std::find_if(unitCollection.begin(),
                                              unitCollection.end(),
                                              has_uCode("this and that"));

And a Little Bit of Performance Consideration

One more thing: I don't know how uCode's look like, but if they're big then you might speed things up by maintaing hashes of these strings so that in your search predicate you only compare the hashes. The hashes might be regular integers: comparing integers is pretty fast.

One more one-more-thing: If you run this search procedure often you might also consider changing your container type, because this really is an expensive procedure: in the order of the list's length.

Answer 4

Your predicate might look something like:

struct unit_predicate {
    unit_predicate(const string& s): str(s) {}
    bool operator()(const Unit* unit) const {
        return unit->isUnit(str);
    }
    const string& str;
};

UnitCollection::const_iterator unit = std::find_if(units.begin(), units.end(), unit_predicate("Some Unit"));

A couple of other comments:

Your isUnit function would be better to take the string by (const) reference to avoid unnecessary copies.

You say you'd like to return the index of an item; that isn't normally sensible for linked lists, because you can't get items back by index. If you want to deal with them by index, maybe std::vector would be more useful to you.