JakΘ funktory pro nßs p°ichystali tv∙rci STL a na co si dßt pozor - to vÜe najdete v tomto zßv∞reΦnΘm dφlu naÜeho povφdßnφ o funktorech.
Koncepty funkcφ v C++
Ji₧ v p°edminulΘm Φlßnku o STL [3] jsme uvedli, tehdy bez dalÜφho vysv∞tlenφ, hierarchii koncept∙ funkcφ. P°φsluÜnΘ schΘma, pro zm∞nu poΦeÜt∞nΘ, zde pro pohodlφ opakujeme a o celΘ v∞ci si nynφ povφme n∞co vφce.
Jak u₧ vφme, modelem konceptu v C++ m∙₧e b²t datov² typ. Ale co funkce? M∙₧e b²t obyΦejnß funkce modelem konceptu? Odpov∞∩ znφ: Ano, ale musφme na ni pohlφ₧et jako na typ (ukazatel na funkci). Nap°φklad funkce
bool mensi_nez(int x, int y)
{ return x < y; }
je typu bool (*)(int, int).
VÜechny funkce majφ jeden nßvratov² typ (t°eba i void), ale mohou se liÜit poΦtem parametr∙. Podle poΦtu parametr∙ d∞lφme funkce na:
* funkce bez parametr∙ - volajφ se bez parametr∙. TakovΘ funkci se takΘ °φkß generßtor, nebo¥ na v²stupu "generuje" n∞jakou hodnotu;
* unßrnφ funkce - volajφ se s jednφm parametrem;
* binßrnφ funkce - volajφ se se dv∞ma parametry;
* obecn∞ n-ßrnφ funkce - volajφ se s n parametry.
Pokud funkce vracφ hodnotu, kterß m∙₧e b²t interpretovßna jako pravdivostnφ, naz²vßme tuto funkci predikßt. Predikßtem samoz°ejm∞ m∙₧e b²t jak unßrnφ, tak binßrnφ funkce (obecn∞ jakßkoli n-ßrnφ funkce); hovo°φme pak o unßrnφm nebo binßrnφm predikßtu (n-ßrnφm predikßtu). Jak je vid∞t ze schΘmatu, tv∙rci STL se takticky omezili na maximßln∞ binßrnφ funkce, ale to nenφ na zßvadu, i tak STL pokr²vß Üirokou Ükßlu b∞₧n²ch pot°eb. Pokud n∞kdo pot°ebuje t°eba ternßrnφ funkce (n = 3), m∙₧e si je podle jednoduchΘho receptu doprogramovat.
Minule jsme takΘ poznali, ₧e by bylo dobrΘ, kdyby se funktor choval jako (Φφselnß) hodnota. V podstat∞ jde o to, aby jej bylo mo₧nΘ bezpeΦn∞ kopφrovat (kopφrovacφ konstruktor) nebo p°i°adit (operßtor =). STL jde dßl a p°φmo to na°izuje - vÜechny koncepty funkcφ zjem≥ujφ koncept Assignable, kter² po₧aduje prßv∞ uvedenΘ vlastnosti (value semantics). ObyΦejnΘ funkce se chovajφ jako hodnoty, nebo¥ p°ekladaΦ s nimi pracuje pomocφ ukazatel∙ Φi referencφ. U funktor∙ je dodr₧enφ po₧adovan²ch vlastnostφ odpov∞dnostφ programßtora.
Minule jsme takΘ narazili na potφ₧, ₧e se n∞kterΘ (zejmΘna obyΦejnΘ) funkce nedaly adaptovat. Proto STL rozliÜuje generßtory a adaptabilnφ generßtory, unßrnφ funkce a adaptabilnφ unßrnφ funkce atd. O tom, co v STL tento p°φvlastek znamenß, se doΦtete dßle.
Adaptabilnφ modely
D∙vod, proΦ se nßm neda°ilo obyΦejnΘ funkce adaptovat, byl prost²: p°ekladaΦ nenaÜel vno°enΘ definice typ∙. A o totΘ₧ jde v STL - adaptabilnφ funkce (funktor) musφ mφt vno°enΘ definice typ∙ argument∙ a typu v²sledku. STL nßm ulehΦuje prßci tφm, ₧e poskytuje dv∞ ÜablonovΘ t°φdy, jednu pro unßrnφ a druhou pro binßrnφ funkce, kterΘ obsahujφ (pouze) pot°ebnΘ vno°enΘ definice typ∙. Pokud nßÜ funktor odvodφme (d∞d∞nφ v duchu OOP) od takovΘ t°φdy, bude mφt automaticky po₧adovanΘ definice typ∙, a bude tedy adaptabilnφ. Tyto dv∞ pomocnΘ t°φdy vypadajφ takto:
// p°edek pro unßrnφ
// adaptabilnφ funktory
template <class ARGUMENT,
class VYSLEDEK>
struct unary_function
{
typedef ARGUMENT argument_type;
typedef VYSLEDEK result_type;
};
// p°edek pro binßrnφ
// adaptabilnφ funktory
template <class ARG1, class ARG2,
class VYSLEDEK>
struct binary_function
{
typedef ARG1 first_argument_type;
typedef ARG1 second_argument_type;
typedef VYSLEDEK result_type;
};
STL nedefinuje ₧ßdnou podobnou t°φdu pro generßtory (funktory volanΘ bez parametr∙). Ale to nevadφ, programßtor m∙₧e snadno vytvo°it adaptabilnφ generßtor i bez toho. A jeÜt∞ jedna d∙le₧itß poznßmka. Abychom vytvo°ili adaptabilnφ funktor, nemusφme jej nutn∞ odvodit od v²Üe uveden²ch t°φd, pot°ebnΘ definice typ∙ m∙₧eme samoz°ejm∞ vepsat ruΦn∞ - p°esn∞ tak jako v minulΘm dφlu.
Operßtory
╚asto pot°ebujeme pou₧φt n∞kter² z aritmetick²ch, logick²ch nebo relaΦnφch operßtor∙. A proto₧e vestav∞nΘ operßtory nelze p°edat funkci pomocφ ukazatele ani reference, musφme na to jφt oklikou a "zabalit" je do funktor∙; jejich seznam naleznete v tabulce 1. Teoreticky by se daly zabalit i do obyΦejn²ch vlo₧en²ch funkcφ, ale tφm bychom se p°ipravili o mo₧nost vno°en²ch definic typ∙ a ztratili tak adaptabilitu.
Jak vypadß implementace, si ukß₧eme na jednoduchΘm p°ikladu unßrnφho minus:
template <class T>
struct negate
: public unary_function<T, T>
{
// operßtor volßnφ funkce
T operator()(const T & arg) const
{
return -arg;
}
};
Ostatnφ t°φdy jsou vytvo°eny podle stejnΘho receptu. Vno°enΘ definice typ∙ se zd∞dφ po p°edcφch, vÜechny tyto funktory jsou tedy adaptabilnφ. P°φklady pou₧itφ naleznete na Chip CD 2/01. Zde si jen krßtce ukß₧eme, jak po slo₧kßch seΦφst dva kontejnery c1 a c2 (obsahujφcφ celß Φφsla typu int) a v²sledek ulo₧it do c1:
transform(c1.begin(), c1.end(),
c2.begin(), c1.begin(), plus<int>());
KlasickΘ funkce
Aby byla klasickß funkce modelem adaptabilnφ funkce, musφme k nφ p°idat vno°enΘ definice typ∙ a vÜechno to zabalit do specißlnφho adaptΘru. JakΘ prost°edky pro tento ·Φel poskytuje STL, vidφme v tabulce 2.
Vytvo°ujφcφ funkce se jmenuje stejn∞ pro unßrnφ i binßrnφ funkce - o rozliÜenφ se postarß p°ekladaΦ (docela p∞knß ukßzka p°et∞₧ovßnφ funkcφ). RozsßhlejÜφ p°φklady naleznete op∞t na Chip CD, zde alespo≥ kratiΦkou etudu, jak v kontejneru c Φφsel typu double nahradit ka₧d² prvek jeho druhou odmocninou:
transform(c.begin(), c.end(),
c.begin(), ptr_fun(sqrt));
╚lenskΘ funkce objektov²ch typ∙
Pokud by nßm nestaΦily ani operßtory, ani obyΦejnΘ funkce, m∙₧eme jeÜt∞ pou₧φt metody objektov²ch typ∙. Zde mφsto obyΦejnΘho ukazatele na funkci pracujeme s ukazatelem do t°φdy. Situace je vÜak slo₧it∞jÜφ, nebo¥ do hry vstupujφ reference a metody konstantnφch objekt∙. P°ehled standardem definovan²ch adaptΘr∙ a jejich vlastnostφ uvßdφ tabulka 3. Zjistφme v nφ mimo jinΘ, ₧e potomci unßrnφ funkce (unary_function) jsou ve skuteΦnosti ΦlenskΘ funkce bez parametr∙ - jedin²m parametrem je toti₧ instance, pro kterou se tato Φlenskß funkce volß. Stejn∞ tak potomci binßrnφ funkce jsou unßrnφ ΦlenskΘ funkce.
Na prvnφ pohled to vypadß slo₧it∞, ale snad pom∙₧e krßtk² p°φklad. Definujeme t°φdu numero, kterß zapouzd°φ typ double (viz soubor f15_stl_mem_fun.cpp na Chip CD):
class numero
{
public:
// ... n∞jakΘ metody ...
// vrati odmocnene numero
numero get_sqrt() const;
// odmocni "toto" numero
void do_sqrt();
private :
double x_;
};
Do n∞jakΘho kontejneru s ulo₧φme blφ₧e nespecifikovan² poΦet instancφ tΘto t°φdy. Budeme chtφt spoΦφtat odmocniny vÜech prvk∙ a ulo₧it je do kontejneru t (p°edpoklßdejme, ₧e t mß stejn∞ prvk∙ jako s). Musφme pou₧φt Φlenskou metodu get_sqrt:
transform(s.begin(), s.end(), t.begin(),
mem_fun_ref(&numero::get_sqrt));
Pokud bychom do kontejneru, nap°. seznamu, uklßdali jen ukazatele na t°φdu numero, tj.
list<numero *> u;
a cht∞li bychom vÜechna tato "numera" (na mφst∞) odmocnit, staΦilo by napsat
for_each(u.begin(), u.end(),
mem_fun(&numero::do_sqrt));
a vÜe by bylo v po°ßdku.
Standardnφ adaptΘry
Kdy₧ je t°eba fixovat parametr...
Jak zafixovat jeden z parametr∙ binßrnφ funkce, u₧ vφme z minula. Nynφ se podφvßme, jak se to d∞lß v STL. AdaptΘr, kter² fixuje parametr, se anglicky naz²vß binder (bind znamenß fixovat, vßzat). Implementace t∞chto adaptΘr∙ v STL je ovÜem pon∞kud slo₧it∞jÜφ ne₧ ta naÜe - je toti₧ koncipovßna obecn∞, pro jakoukoli adaptabilnφ binßrnφ funkci (funktor). Zde nßm postaΦφ jejich p°ehled v tabulce 4.
Pro ukßzku navß₧eme na p°φklady z minulΘho dφlu: mßme op∞t kontejner cisla cel²ch Φφsel typu int a chceme najφt prvnφ kladn² a prvnφ zßporn² prvek. Pou₧ijeme k tomu standardnφ binßrnφ funktor greater z tab. 1.
// prvnφ kladn² (>0)
find_if(cisla.begin(), cisla.end(),
bind2nd(greater<int>(), 0));
// prvnφ zßporn² (<0)
find_if(cisla.begin(), cisla.end(),
bind1st(greater<int>(), 0));
... nebo negovat v²sledek
Negovat v²sledek u₧ takΘ umφme z minula. P°φsluÜn² adaptΘr se naz²vß negßtor. V STL jsou k dispozici dva: jeden pro unßrnφ a druh² pro binßrnφ funkce (predikßty), viz tabulka 5.
Tφm jsme probrali vÜechny standardnφ funktory i adaptΘry a nastal Φas na n∞jak² komplexn∞jÜφ p°φklad. ╪ekn∞me, ₧e kontejner v obsahuje °et∞zce (typ string) a funkce porovnej je analogiφ standardnφ funkce strcmp pro °et∞zce typu string. Tipn∞te si, co ud∞lß nßsledujφcφ p°φkaz:
replace_if(v.begin(), v.end(),
not1(bind2nd(ptr_fun(porovnej), "C")),
"C++");
Odpov∞∩ najdete na Chip CD 2/02 (hrajte fΘr a zkuste nejd°φve potrßpit vlastnφ hlavu...).
Jak napsat vlastnφ funktor
P°i prßci s STL se obΦas dostaneme do situace, kdy pot°ebujeme generickΘmu algoritmu vnutit n∞jakou Φinnost, kterou mß provΘst s prvky kontejneru a kterou nelze realizovat prost°edky STL. Nezb²vß ne₧ napsat bu∩ klasickou funkci, nebo jeÜt∞ lΘpe - vytvo°it funktor.
P°edem si musφme ujasnit n∞kolik otßzek:
* P∙jde o unßrnφ, nebo binßrnφ funkci?
* JakΘ jsou typy argument∙ a v²sledku?
* StaΦφ nßm klasickß funkce, nebo to musφ b²t funktor?
* Pot°ebujeme adaptabilnφ, nebo postaΦφ neadaptabilnφ funktor?
* Odvodit (nebo neodvodit) nßÜ funktor jako potomka t°φdy unary_function, nebo binary_function?
╪eÜenφ prvnφch dvou otßzek je zßsadnφ, odpov∞di na ostatnφ otßzky pouze urΦujφ kvalitu implementace. Nesmφme takΘ zapomenout, ₧e instance funktor∙ se p°edßvajφ hodnotou.
Uva₧ujme jednoduch² p°φklad. Mßme kontejner cisla hodnot typu double a chceme n∞jak zpracovat jejich odchylky od jistΘ hodnoty (t°eba jejich aritmetickΘho pr∙m∞ru). Ud∞lßme to tak, ₧e odchylky budeme uklßdat jednu po druhΘ do jinΘho, p°edem vyprßzdn∞nΘho kontejneru, kter² pojmenujeme t°eba odchylky. NapφÜeme si funktor, kter² bude poΦφtat odchylky (nebo p°φmo rovnou jejich mocniny). V naÜem p°φpad∞ p∙jde o unßrnφ funktor (zkuste si rozmyslet proΦ). NejjednoduÜÜφ je neadaptabilnφ funktor, t°eba takov²:
class cOdchylkaNeadapt
{
public:
cOdchylkaNeadapt(double odceho,
int mocnina)
: od_ceho_(odceho),
mocnina_(mocnina)
{}
double operator ()(double x);
private:
double od_ceho_;
int mocnina_;
};
Funktor v tΘto podob∞ by nßm te∩ staΦil, ale zkusme jej zm∞nit na adaptabilnφ. (Je to takovß investice do budoucna - nikdy nevφme, kdy se to bude hodit.) StaΦφ bu∩ doplnit vno°enΘ definice typ∙, stejn∞ jako v minulΘm dφlu, nebo jeÜt∞ lΘpe - odvodit nßÜ funktor od STL t°φdy unary_function:
class cOdchylkaAdaptSTL : public
unary_function<double, double>
{
public:
cOdchylkaAdaptSTL(double odceho,
int mocnina)
: od_ceho_(odceho),
mocnina_(mocnina)
{}
double operator ()(double x);
private:
double od_ceho_;
int mocnina_;
};
Vno°enΘ definice typ∙ se zd∞dφ od p°edka. P°φklady pou₧itφ obou funktor∙ se prakticky neliÜφ, tak₧e jeden za oba:
transform(cisla.begin(), cisla.end(),
odchylky.begin(), cOdchylkaNeadapt(0.0, 2));
Jist∞ jste poznali, ₧e zde poΦφtßme kvadratickΘ odchylky od nuly za pomoci neadaptabilnφho funktoru.
Jak napsat vlastnφ adaptΘr
Podobn∞ postupujeme p°i vytvß°enφ adaptΘru funktoru - bude to toti₧ takΘ funktor. P°i zjiÜ¥ovßnφ typ∙ argument∙ a v²sledku se m∙₧eme "zeptat" adaptovanΘho funktoru. Tvorb∞ r∙zn²ch ukßzkov²ch adaptΘr∙ jsme se v∞novali u₧ minule, nynφ si ukß₧eme adaptΘr, kter² implementuje sklßdßnφ dvou funkcφ. Mßme stßle kontejner cisla hodnot typu double a chceme vÜechna Φφsla nejprve nahradit jejich absolutnφ hodnotou a pak odmocnit.
// pomocnß definice typu
typedef double (* FUNC)(double);
class cSkladani
{
public:
cSkladani(FUNC prvni, FUNC druha)
: prvni_(prvni), druha_(druha)
{}
double operator ()(double x)
{
return druha_(prvni_(x));
}
private:
FUNC prvni_;
FUNC druha_;
};
Vytvo°ili jsme neadaptabilnφ adaptΘr, kter² se postarß o slo₧enΘ volßnφ dvou unßrnφch funkcφ typu FUNC. Pou₧itφ by pak mohlo vypadat t°eba takto:
transform(cisla.begin(), cisla.end(),
cisla.begin(), cSkladani(fabs, sqrt));
┌skalφ, podrazy a pr∙Üvihy
ObΦas pot°ebujeme zjistit, kolikrßt byl dan² funktor volßn. Takov² pokus ale v STL obvykle skonΦφ krachem. Dejme tomu, ₧e jsme do funktoru p°idali ΦφtaΦ, kter² se p°i ka₧dΘm zavolßnφ zv²Üφ o jedniΦku:
class cFunktor
{
public:
int operator ()(int x)
{
++pocet_;
// n∞jakΘ akce ...
}
int get_pocet() { return pocet_; }
void reset_pocet() { pocet_ = 0; }
private:
int pocet_;
// ...
};
A pak jej pou₧ijeme n∞jak takto:
// POZOR, TAKHLE TO NEFUNGUJE
cFunktor funktor;
funktor.reset_pocet();
transform(cisla.begin(), cisla.end(),
cisla.begin(), funktor);
cout << "pocet volani = "
<< funktor.get_pocet() << endl;
A¥ je Φφsel, kolik chce, v₧dy se vypφÜe nula. U vÜech generick²ch algoritm∙ v STL se toti₧ funkce Φi funktor p°edßvajφ hodnotou. To znamenß, ₧e se vytvo°φ kopie, kterß bude ·sp∞Ün∞ poΦφtat, kolikrßt byla volßna, ale my se to nedozvφme, nebo¥ tato kopie zanikne p°i nßvratu z funkce transform. Jednou z mo₧nostφ nßpravy by bylo pou₧φt v definici funktoru ukazatel Φi referenci na ΦφtaΦ le₧φcφ n∞kde vn∞ funktoru (ale to s sebou nese zase jinß rizika...).
DalÜφ "zßdrhel", na kter² je t°eba pamatovat: P°i pou₧itφ funkce transform standard negarantuje, ₧e se prvky budou prochßzet od zaΦßtku a po jednom. Jedinou jistotou je, ₧e funktor (nebo funkce) se zavolß pro ka₧d² prvek v danΘm rozsahu prßv∞ jednou. Co to znamenß? M∞jme unßrnφ predikßt, kter² vracφ true pro t°etφ prvek a false pro vÜechny ostatnφ:
Bude to fungovat, jak chceme? Odpov∞∩ znφ: Mo₧nß, jak kde. Jde toti₧ o nep°enositeln² k≤d, kter² se v r∙zn²ch p°ekladaΦφch m∙₧e chovat r∙zn∞, a standard to dovoluje! (Pravda vÜak je, ₧e ve vÜech mn∞ znßm²ch implementacφch se chovß stejn∞ - prochßzφ prvky od zaΦßtku do konce a po jednom, ale standard je standard...)
Jinou zßle₧itost, na ni₧ je t°eba upozornit, bych bez vßhßnφ oznaΦil za "p∞kn² podraz". V nßsledujφcφm progrßmku chceme odstranit t°etφ prvek z kontejneru cisla (funkce remove_if vracφ iterßtor na konec rozsahu po odebrßnφ prvk∙; pokud tam zbude n∞jak² "cancour", zlikvidujeme jej pomocφ metody erase):
// POZOR, NEMUS═ FUNGOVAT!
cisla.erase(remove_if(cisla.begin(),
cisla.end(),
cTreti()),
cisla.end());
Je-li p∙vodnφ posloupnost
1 2 3 4 5 6 7 8 9,
mß tedy v²slednß posloupnost b²t
1 2 4 5 6 7 8 9.
K naÜemu velkΘmu p°ekvapenφ se vÜak m∙₧eme doΦkat v²sledku
1 2 4 5 7 8 9.
Jak je to mo₧nΘ? Odpov∞∩ nalezneme v definici ÜablonovΘ funkce remove_if. Ta m∙₧e vypadat t°eba takto:
template <class ITER, class PREDIKAT>
ITER remove_if(ITER beg, ITER end,
PREDIKAT op)
{
beg = find_if(beg, end, op); // !!
if (beg == end) { return beg; }
else {
ITER next = beg;
return remove_copy_if(++next,
end, beg, op); // !!
}
}
Na °ßdcφch oznaΦen²ch dv∞ma vyk°iΦnφky se volajφ dalÜφ funkce z STL a nßÜ funktor je jim p°edßn hodnotou. To znamenß, ₧e se vytvß°ejφ kopie, kterΘ pak p°ed nßvratem do funkce remove_if op∞t zaniknou. A mßme problΘm: nßÜ predikßt mß sv∙j vnit°nφ stav (nastavenφ slo₧ky pocet_), pomocnΘ funkce ale tento stav zm∞nφ u kopie, kterß zanikne, tak₧e se o zm∞n∞ nedozvφme. Co je vÜak jeÜt∞ horÜφ - standard p°edepisuje pro funkci remove_if pouze rozhranφ, nikoli implementaci. Tak₧e u n∞kter²ch implementacφ to m∙₧e fungovat, jak Φekßme, u jin²ch ne.
Vezm∞me si z toho alespo≥ toto pouΦenφ: Pozor na predikßty (ale i obecnΘ funktory) s vnit°nφm stavem, kter² zßvisφ na jednotliv²ch volßnφch predikßtu (funktoru). ObΦas nahlΘdnout do zdrojov²ch k≤d∙ implementace STL se urΦit∞ vyplatφ...
Optimistick² zßv∞r
AΦkoli p°edchozφ °ßdky nevyzn∞ly zvlßÜt∞ pozitivn∞, pova₧uji funktory za mocn² nßstroj a takΘ jej s ·sp∞chem vyu₧φvßm ve sv²ch programech. JistΘ je, ₧e pokud programujete pomocφ STL a jejφch generick²ch algoritm∙, bez funktor∙ se prost∞ neobejdete. Budi₧ vßm tento Φlßnek oporou...
Jaroslav Fran∞k
infotipy
[1] Mezinßrodnφ standard jazyka C++, ICO/IEC 14882:1998
[2] J. Fran∞k: Jak se na funktor volß... (1), Chip 1/02
[3] J. Fran∞k: Nebojte se STL, Chip 12/01
[4] S. Meyers: Effective STL, ISBN 0-201-74962-9
[5] dokumentace knihovny STL od SGI: www.sgi.com/tech/stl
[6] zdrojov² k≤d v rubrice Chip Plus na Chip CD 2/02
