Szablony i funktory w roli predykatów

Nieraz zdarza się, że przechowujemy w kontenerach STL-owych niebanalne obiekty, czy typy nieco bardziej rozbudowane od typów wbudowanych. Praca na takich obiektach i zbiorach z wykorzystaniem algorytmów STL-a może być przyjemna i często nawet lepsza od ręcznego rzeźbienia kodu, choć czasem mogą pojawiać się jakieś pułapki.

Dla przykładu, załóżmy, że mamy 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 wydaje się napisanie kilku prostych linii kodu, który wraz z pętlą iterującą po wszystkich elementach kontenera i porównywaniu nazwy pozwoli znaleźć ten poszukiwany element:

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) algorytmów?

Do tego zadania idealnie nadaje się dedykowana “funkcja” find_if, której prototyp wygląda tak:

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

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:

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

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

Może też równie dobrze być prostym funktorem:

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;
};

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

Najlepiej o ile to możliwe, zdefiniować kod jako inline, aby kompilator wszystko ładnie rozwinął w miejscu wywołania i wygenerował zwięzły wynikowy kod, podobny do tego wyrzeźbionego ręcznie z pętelką wyżej ;)

Na pierwszy rzut oka może się wydawać, że taka zabawa nie jest współmierna do wyniku. Wszakże “ręcznie” dałoby się to napisać szybciej, zamiast bawić się jakimiś szablonami, algorytmami… W tym prostym przypadku może tak…

Jednak nic nie stoi na przeszkodzie, aby wykorzystać w pełni zawartą w szablonach moc i pokusić się o stworzenie uniwersalnego orzecznika dla find_if i innych algorytmów. Dzięki nim w łatwy sposób będzie można wyszukiwać elementy w kontenerach według dowolnych kryteriów (składowych) różnych obiektów, dokonując tylko specjalizacji wzorca.

Taka prosta implementacja takiego szablonu mogłaby wyglądać następująco:

template<class T, class ConstType, const ConstType& (T::* method)() const>
class EqualThruMemFunc {
public:
	EqualThruMemFunc(const ConstType& value) : m_value(value) { }

	bool operator()(T& instance) {
		return (instance.*method)() == m_value;
	}

private:
	const ConstType& m_value;
};

Po dodaniu do MyObj prostego gettera GetName do pobierania nazwy, powyższy kod można wykorzystać tak:

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

Przykład ten pochodzi z 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, co jeszcze bardziej uprości kod:

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 jest ręcznie naskrobać kod, ale z czasem, z coraz większą stycznością i znajomością STL-a nabiera się przekonania do niego. Tak samo jest z boostem, ale z nim mam jeszcze małe “doświadczenia”.

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!