Sza­blo­ny i funk­to­ry w roli pre­dy­ka­tów

Nie­raz zda­rza się, że prze­cho­wu­je­my w kon­te­ne­rach STL-​owych nie­ba­nal­ne obiek­ty, czy typy nieco bar­dziej roz­bu­do­wa­ne od typów wbu­do­wa­nych. Praca na ta­kich obiek­tach i zbio­rach z wy­ko­rzy­sta­niem al­go­ryt­mów STL-a może być przy­jem­na i czę­sto nawet lep­sza od ręcz­ne­go rzeź­bie­nia kodu, choć cza­sem mogą po­ja­wiać się ja­kieś pu­łap­ki.

Dla przy­kła­du, za­łóż­my, że mamy vec­tor wy­peł­nio­ny pro­sty­mi obiek­ta­mi o bu­do­wie zbli­żo­nej do na­stę­pu­ją­cej struk­tu­ry:

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

I chcie­li­by­śmy wy­szu­kać w nim ele­ment o na­zwie “foo”.

Oczy­wi­ście naj­prost­szym i naj­szyb­szym roz­wią­za­niem wy­da­je się na­pi­sa­nie kilku pro­stych linii kodu, który wraz z pętlą ite­ru­ją­cą po wszyst­kich ele­men­tach kon­te­ne­ra i po­rów­ny­wa­niu nazwy po­zwo­li zna­leźć ten po­szu­ki­wa­ny ele­ment:

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ęcz­nie się tym bawić w cza­sach, gdy po­sia­da­my roz­bu­do­wa­ną bi­blio­te­kę stan­dar­do­wą, za­wie­ra­ją­cą kil­ka­na­ście sza­blo­no­wych (w każ­dym tego słowa zna­cze­niu) al­go­ryt­mów?

Do tego za­da­nia ide­al­nie na­da­je się de­dy­ko­wa­na “funk­cja” find_if, któ­rej pro­to­typ wy­glą­da tak:

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

Jej dzia­ła­nie jest pro­ste - szuka pierw­sze­go ele­men­tu mię­dzy start a end, dla któ­re­go orzecz­nik (pre­di­ca­te) pred zwró­ci true, a gdy nie znaj­dzie zwra­ca end.

Orzecz­nik może być wskaź­ni­kiem na funk­cje zwra­ca­ją­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ów­nie do­brze być pro­stym funk­to­rem:

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"));

Naj­le­piej o ile to moż­li­we, zde­fi­nio­wać kod jako in­li­ne, aby kom­pi­la­tor wszyst­ko ład­nie roz­wi­nął w miej­scu wy­wo­ła­nia i wy­ge­ne­ro­wał zwię­zły wy­ni­ko­wy kod, po­dob­ny do tego wy­rzeź­bio­ne­go ręcz­nie z pę­tel­ką wyżej ;)

Na pierw­szy rzut oka może się wy­da­wać, że taka za­ba­wa nie jest współ­mier­na do wy­ni­ku. Wszak­że “ręcz­nie” da­ło­by się to na­pi­sać szyb­ciej, za­miast bawić się ja­ki­miś sza­blo­na­mi, al­go­ryt­ma­mi… W tym pro­stym przy­pad­ku może tak…

Jed­nak nic nie stoi na prze­szko­dzie, aby wy­ko­rzy­stać w pełni za­war­tą w sza­blo­nach moc i po­ku­sić się o stwo­rze­nie uni­wer­sal­ne­go orzecz­ni­ka dla find_if i in­nych al­go­ryt­mów. Dzię­ki nim w łatwy spo­sób bę­dzie można wy­szu­ki­wać ele­men­ty w kon­te­ne­rach we­dług do­wol­nych kry­te­riów (skła­do­wych) róż­nych obiek­tów, do­ko­nu­jąc tylko spe­cja­li­za­cji wzor­ca.

Taka pro­sta im­ple­men­ta­cja ta­kie­go sza­blo­nu mo­gła­by wy­glą­dać na­stę­pu­ją­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 do­da­niu do MyObj pro­ste­go get­te­ra GetName do po­bie­ra­nia nazwy, po­wyż­szy kod można wy­ko­rzy­stać tak:

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

Przy­kład ten po­cho­dzi z use­ne­to­wej grupy comp.lang.c++. W te­ma­cie tym o dźwięcz­nym ty­tu­le “Help with tem­pla­te find_if pre­di­ca­te” można zna­leźć kilka cie­ka­wych przy­kła­dów zwią­za­nych z po­ru­sza­nym tutaj (i tam) pro­ble­mie.

Można także wy­ko­rzy­stać bind z std::tr1 lub bo­osta, co jesz­cze bar­dziej upro­ści kod:

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

Sam kie­dyś uwa­ża­łem, że le­piej i szyb­ciej jest ręcz­nie na­skro­bać kod, ale z cza­sem, z coraz więk­szą stycz­no­ścią i zna­jo­mo­ścią STL-a na­bie­ra się prze­ko­na­nia do niego. Tak samo jest z bo­ostem, ale z nim mam jesz­cze małe “do­świad­cze­nia”.

Może na po­cząt­ku wy­da­je się to tro­chę za­wi­łe i skom­pli­ko­wa­ne, ale to mija, gdy tylko pozna się tę ukry­tą moc.
Niech moc bę­dzie z wami!