find_if predicate

Nieraz zdarza się, ze przechowujemy w kontenerach STL-owych niebanalne obiekty, czy typy nieco bardziej rozbudowane od typów wbudowanych.

Załóżmy, że mamy prosty vector wypełniony prostymi obiektami o budowie zbliżonej do następującej struktury:

struct MyObj{
	int foo;
	int bar;
	std::string name;
};

I chcielibyśmy wyszukać w nim element o nazwie „foo”.

Oczywiście najprostszym i najszybszym rozwiązaniem (przynajmniej na początku) byłoby napisanie kilku prostych linii kodu, wraz z pętelką, spełniających tą funkcje. Coś na wzór tego:

typedef std::vector<MyObj> MyObjVector;
// ...
MyObjVector my_vector;
// ...
for(MyObjVector::iterator iter = my_vector.begin(); iter != my_vector.end(); ++iter) {
	if (iter->name == std::string("foo"))
		break;
}

Czy warto ręcznie się tym bawić w czasach, gdy posiadamy rozbudowaną bibliotekę standardową, zawierającą kilkanaście szablonowych (w każdym tego słowa znaczeniu ;p) algorytmów?

Dla naszego przypadku nadaje się „funkcja” find_if, której prototyp wygląda tak:

iterator find_if(iterator start, iterator end, Predicate pred);

a jej działanie jest proste – szuka pierwszego elementu między start a end, dla którego orzecznik (predicate) pred zwróci true, a gdy nie znajdzie zwraca end.

Orzecznik może być wskaźnikiem na funkcje zwracającą typ bool lub prostym funktorem.

Czyli moglibyśmy napisać sobie prostą funkcje:

inline bool MyObjPred(const MyObj& obj) {
	return obj.name == std::string("foo");
}

lub prosty funktor:

class MyObjPred : public std::unary_function<MyObj, bool> {
	public:
		MyObjPred(const std::string& name) : m_name(name) {}
 
		bool operator()(const MyObj& obj) const {
			return obj.name == m_name;
		}
 
	private:
		const std::string& m_name;
};

i jego proste uzycie:

MyObjVector::iterator it = std::find_if(my_vector.begin(), my_vector.end(), MyObjPred("foo"));

Najlepiej inline, aby kompilator wszystko ładnie rozwinął w miejscu wywołania i wygenerował zwięzły wynikowy kod, podobny do tego wyrzeźbionego ręcznie wyżej ;)

Na pierwszy rzut oka można zauważyć, że taka zabawa nie jest współmierna do wyniku, wskaże ręcznie może szybciej byśmy to napisali, niż zabawiać się szablonami.

Może tak, ale nic nie stoi na przeszkodzie, aby wykorzystać w pełni zawartą w template moc i pokusić się o stworzenie uniwersalnego orzecznika dla find_if i innych algorytmów, dzięki któremu w łatwy sposób będziemy mogli wyszukiwać elementy w kontenerach według dowolnych kryteriów (składowych) różnych obiektów, specjalizując tylko nasz szablon.

Prosta implementacja takiego szablonu:

template < class T, class ConstType, const ConstType (T::*method)() >
class EqualThruMemFunc {
	public:
		EqualThruMemFunc(const ConstType& value) : m_value(value) { }
 
		bool operator()(T& instance) {
			return (instance.*method)() == m_value;
		}
 
	private:
		const ConstType& m_value;
}

Do naszej struktury dodajemy prosty getter do pobierania nazwy i powyższy kod możemy użyć następująco:

MyObjVector::iterator it = std::find_if(my_vector.begin(), my_vector.end(), 
		EqualThruMemFunc<MyObjVector, std::string, &MyObjVector::GetName>("foo"));

Przykład ten pochodzi z pewnego tematu usenetowej grupy comp.lang.c++.
W temacie tym o dźwięcznym tytule „Help with template find_if predicate” można znaleźć kilka ciekawych przykładów związanych z poruszanym tutaj (i tam) problemie.

Można także wykorzystać bind z std::tr1 lub boosta:

MyObjVector::iterator it = std::find_if(my_vector.begin(), my_vector.end(),
		boost::bind(&MyObj::GetName, _1) == std::string("foo"));

Sam kiedyś uważałem, że lepiej i szybciej będzie mi ręcznie naskrobać kod, ale z czasem i coraz większą znajomością STL-a nabiera się większego przekonania do niego. Tak samo z boostem, ale z nim to jeszcze mam małe „doświadczenie”.

Może na początku wydaje się to trochę zawiłe i skomplikowane, ale to mija, gdy tylko pozna się tą ukrytą moc.

Niech moc będzie z wami!

4 przemyślenia nt. „find_if predicate”

  1. Kawałek solidnej informatycznej wiedzy;) Piszącym w Pythonie można polecić moduł itertools. Kto nie zna – najlepiej zacząć od przykładów. Ja podam tylko jeden: policzyć iloczyn skalarny 2 wektorów.

    def dotproduct(vec1, vec2):
    return sum(imap(operator.mul, vec1, vec2))

    Piękne, prawda?

  2. Mam nadzieję że nadal używasz jedynego słusznego kompilatora – GCC? :>. Visual, ach Visual… Taki skromny wpis stawia przypominając się przed kolejnym rokiem udręki :)

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *