Knihovna STL jazyka C++
Jak se na funktor volá...  (1)
Důležitou součástí knihovny STL jazyka C++ jsou tzv. funktory, mezi programátory však o nich mnoho známo není. V tomto dvoudílném příspěvku se o nich dozvíte více; mimo jiné také poznáte, že jde o staré známé věci převlečené do nového kabátu.

Funkce a funktor
Volání funkce je neodmyslitelně spjato s kulatými závorkami (), do kterých vepisujeme argumenty funkce. Přitom identifikátor nebo výraz představující funkci stojí nalevo od těchto kulatých závorek. Otázka zní: Co všechno může nalevo od kulatých závorek představujících volání funkce vlastně stát? Asi nejstručnější a nejvýstižnější odpověď dá obrázek 1.
Klasická funkce
Klasická funkce je to, co známe ze základního kurzu jazyka C++ (nebo i céčka). Někdy se jim také říká (klasické) céčkovské funkce, ale to není příliš vhodné, protože funkce v C++ může mít třeba definovány implicitní hodnoty argumentů, a to (zatím) v céčku možné není. Zkusme si uvést jednoduchý příklad - druhou mocninu celého čísla:
int druha_mocnina(int cislo) 
{ return cislo * cislo; }
S klasickými funkcemi pracujeme buď přímo, tj. použijeme identifikátor funkce, nebo pomocí ukazatelů či referencí. 
Operátor
Speciálním případem klasických funkcí jsou operátorové funkce neboli krátce operátory. Jsou natolik speciální, že si zaslouží vlastní kategorii. Zde je výčet jejich zvláštností:
* Umožňují zkrácený zápis volání bez kulatých závorek.
* Při zkráceném zápisu volání mohou argumenty stát nalevo (postfixový operátor), napravo (prefixový operátor), z obou stran (infixový operátor) nebo i jinak.
* Operátory pro vestavěné typy jsou přímo součástí překladače; nelze tedy získat jejich adresu (ukazatel) či referenci a nelze je volat pomocí kulatých závorek (více viz standard [1], sekce 13.6.).
Vše objasní několik příkladů.
int operator +(int, int);
Toto je jeden z vestavěných binárních operátorů, konkrétně součet dvou celých čísel se znaménkem. Jeho typické použití vypadá např. takto:
int a = 1, b = 2, c;
c = a + b;
Jazyk C++ umožňuje definovat si vlastní verze operátorů pro výčtové nebo objektové typy. Takže pokud máme jednoduchou třídu sInt (definici naleznete v souboru f01_klasika.cpp na Chip CD 1/02) a definovali jsme (přetížený) operátor +
sInt operator +(const sInt & a,
                const sInt & b);
můžeme psát
sInt a(1), b(2), c;
c = a + b;
Také bychom mohli napsat
c = operator +(a, b);
ale to se používá málokdy. Pak by totiž operátory byly k ničemu a vystačili bychom s klasickými funkcemi. Stejně jako u klasických funkcí, pokud se rozhodneme pro volání pomocí kulatých závorek, můžeme s operátory pracovat přímo, nebo pomocí ukazatelů či referencí.
Členská funkce 
V objektově orientovaném programování narazíme na další typ funkce - tou je členská funkce (member function) nebo také metoda objektu. (Pojem metoda třídy je vyhrazen pro statickou metodu objektu, která je v podstatě ekvivalentní s klasickou funkcí.) Členská funkce je součástí definice třídy. Krátký příklad osvětlí definici i použití členské funkce:
class cNeco
{
public:
   int clenska_funkce();
private:
   int soukroma_data;
};

int cNeco::clenska_funkce()
   { return soukroma_data; }

int main() {
   sNeco a;
   cout << a.clenska_funkce();
}
S členskými funkcemi pracujeme buď přímo (použijeme identifikátor funkce), nebo prostřednictvím ukazatelů do třídy. Zde je ale situace složitější než u obyčejných ukazatelů na klasické funkce, protože k tomu potřebujeme navíc příslušnou instanci. Uvažujme třídu cNeco z předchozího příkladu:
int main() {
   int (cNeco::* pf)() =
            &cNeco::clenska_funkce;
   sNeco a;
   cout << (a.*pf)();
   cout << ((&a)->*pf)();
}
Samotný ukazatel nestačí, musíme použít nějakou instanci a jeden z operátorů .* nebo ->* (podle situace). Teprve pak lze použít volání funkce (to má vyšší prioritu než oba operátory, proto je musíme uzavřít do závorek). Je tu jedna kuriozita: V C++ má výraz vždy nějaký typ, přesněji řečeno skoro vždy - kromě výrazů se zmíněnými dvěma operátory. Výraz a.*pf nebo (&a)->*pf je ve skutečnosti beztypová (!) entita a jediné, co se s ní dá dělat, je bezprostřední volání funkce pomocí kulatých závorek.
Pro úplnost: Členské metody lze ještě dále rozdělit na obyčejné, operátory, metody třídy, speciální (konstruktor, destruktor) atd.; to pro nás však nyní není podstatné. Podstatné ale je, že mezi členskými operátory je i operátor volání funkce (). A když pro třídu přetížíme tento operátor, dostaneme funktor.
Funktor
Funktor je tedy obecně každá třída, která má veřejně přístupný přetížený operátor volání funkce. Uveďme si jako příklad analogii úvodní klasické funkce:
class cDruhaMocnina
{
public:
   int operator()(int cislo) 
      { return cislo * cislo; }
};
Použití je nasnadě:
int a = 1, b;
cDruhaMocnina sqr;  // instance
b = sqr(a);   // použití
Vidíme tedy, že použití funktoru se téměř vůbec neliší od použití klasické funkce - a o to tu jde. Dále je jasné, že funktor lze takto použít pouze přímo nebo přes referenci. Ukazatel na funktor je obyčejný ukazatel na nějakou instanci, takže bychom ho museli buď dereferencovat, nebo použít nezkrácené volání operátoru:
cDruhaMocnina * psqr = &sqr;
// dereferencování
b = (*psqr)(a); 
// nezkrácený zápis 
b = psqr->operator()(a);
Což je skoro jako pěst na oko ve srovnání s elegantním zápisem sqr(a).
Jelikož nám půjde především o srovnání funktorů s ostatními funkcemi, pro "nefunktor" zavedeme pojem obyčejná funkce. Obyčejnou funkcí pro nás tedy bude jak klasická funkce a operátor, tak i členská funkce.

Trocha motivace
K čemu jsou funktory vlastně dobré? Jaké mají výhody oproti obyčejným funkcím? Vyplatí se je vůbec používat? Zkusme se nad těmito otázkami zamyslet hlouběji.
Funkce parametrem šablony
Zabrusme na chvilku do STL. Máme nějakou posloupnost celých čísel a chceme jejich druhé mocniny. Čísla jsou uložena v nějakém vhodném kontejneru (je jedno, jestli je to vector, deque, list nebo klasické pole), který se jmenuje cisla. Běžný programátor by napsal asi toto:
for ( int i = 0; i != N; ++i ) 
      // N je velikost kontejneru
{
   cisla[i] *= cisla[i];
}
My zkušenější bychom ale spíš použili (dopředné) iterátory:
for ( iterator i = cisla.begin();
      i != cisla.end(); ++i )
{
   *i *= *i;  // pozor na hvězdičky
}
kde iterator je typ příslušného iterátoru na našem kontejneru (pokud jde o klasické pole, nebude to nic jiného než ukazatel int *; pak ovšem budou meze zadány trochu jinak - viz zdrojový kód na Chip CD 1/02). 
Ale proč pořád psát smyčky, když to už někdo udělal za nás? V STL nalezneme funkci transform, která udělá přesně to, co chceme:
transform(cisla.begin(), cisla.end(),
          cisla.begin(), druha_mocnina);
Anebo s použitím funktoru (musíme vytvořit jeho instanci, nejlépe nepojmenovanou, pak má totiž překladač volné ruce k optimalizaci):
transform(cisla.begin(), cisla.end(),
          cisla.begin(), cDruhaMocnina());
První dva parametry jsou vstupní iterátory, které ohraničují zpracovávané prvky, třetí parametr je výstupní iterátor - od toho místa se budou ukládat výsledky (v našem případě přepíšeme původní prvky). Čtvrtým parametrem je funkce, tj. to, co se má provést s každým prvkem v daném rozsahu - může to být jak klasická funkce, tak funktor. 
Zde ještě nejsou výhody funktoru patrné, ale zkusme se zamyslet nad tím, jak funkci transform vnutit libovolnou mocninu. Pokud bychom trvali na použití klasických funkcí, nezbylo by nic jiného, než pro každý případ napsat zvláštní funkci. To by pak vypadalo třeba takto:
int treti_mocnina(int cislo) { /* ... * / }
int ctvrta_mocnina(int cislo) { /* ... */ }
// ... a tak nějak pořád dál, prostě hrůza...
Nezkušený programátor by si teď asi řekl: "Sbohem STL, vracím se ke smyčkám." My, kteří už víme o funktorech, ovšem napíšeme:
class cMocnina
{
public:
   cMocnina(int stupen)
      : stupen_(stupen) {}
   int operator()(int cislo) 
      { /* ... */ }
private:
   int stupen_;
};
Třeba šestá mocnina by pak vypadala takto:
transform(cisla.begin(), cisla.end(),
          cisla.begin(), cMocnina(6));
Výhoda funktoru je jasná: Protože to je (jakkoli složitá) třída, může obsahovat libovolná data, která můžeme (nebo musíme) inicializovat v konstruktoru. Tato data mohou "parametrizovat" danou funkci, v našem případě mocninu. Tohle obyčejné funkce neumějí (alespoň ne tak elegantně).
Typové informace
Další důležitou vlastností funktorů je, že mohou obsahovat vnořené definice typů. Tyto definice mohou například definovat typ vracené hodnoty nebo typy argumentů. Tentokrát budeme pro změnu hledat první záporné číslo v posloupnosti cisla (použitím algoritmu find_if), a použijeme navíc obecnější funktor, který bude zjišťovat, zda daná hodnota je menší než nějaké předem zadané číslo. A když už jsme v tom, implementujeme funktor jako šablonu.
template <class T> class cJeMensiNez
{
public:
   // typ výsledku
   typedef bool result_type;
   // typ argumentu
   typedef T argument_type;

   cJeMensiNez(T co) : co_(co) {}
   result_type operator()(T cislo) 
      { return cislo < co_; }
private:
   T co_;
};

iterator prvni_zaporne = 
   find_if(cisla.begin(), cisla.end(),
           cJeMensiNez<int>(0));
Jména pro vnořené typy nebyla, jak posléze uvidíme, zvolena náhodně. Připomeňme ještě, že algoritmus find_if vrátí iterátor cisla.end() v případě, že nenalezne žádné záporné číslo.
Otázka zní: Co s těmi vnořenými definicemi typů? Není to zbytečnost? Možná si ještě vzpomenete na články [4] a [5], kde jsme převáděli výrazy na data. Nešlo o nic jiného než o aplikaci funktorů. Sice jsme nepoužívali přetížený operátor (), ale statickou metodu apply, to je však drobný detail - myšlenka byla stejná. K tomu, abychom zjistili výsledný typ výrazu, jsme potřebovali právě ony vnořené definice typů. Právě při použití šablon vynikne tato vlastnost funktorů. Zkuste se obyčejné funkce zeptat na typ výsledku nebo typy argumentů - to prostě nejde.
Adaptér
Už umíme najít první záporné číslo v nějaké posloupnosti. Dokázali bychom najít také první nezáporné číslo v posloupnosti? Asi nás jako první napadne vzít a zkopírovat předchozí příklad, změnit jméno třídy a změnit znaménko < na >=. Vždyť přece jde jen o negaci toho, co jsme měli předtím. Jistěže, ale do stejné situace (kdy potřebujeme negaci) se můžeme dostat vícekrát a určitě by nebylo nejlepší pokaždé kopírovat a upravovat, zvláště pak v případě hodně složitého funktoru (takové v tomto článku z pochopitelných důvodů nenajdete, ale v praxi na něco takového určitě narazíte). 
Takže jak na to? Nevyhovuje nám přetížený operátor (), potřebujeme totiž jeho negaci. Obecně řečeno, chceme jej pro naše požadavky přizpůsobit (adaptovat) - prostředek, který nám k tomu poslouží, se proto nazývá adaptér. O co jde, naznačí schéma na obr. 2 a následující stručný popis.
Klient chce použít funktor, ale ten nesplňuje jeho požadavky nebo mu prostě nerozumí (analogie s jazykovou bariérou je docela výstižná). Klient proto potřebuje nějakého prostředníka (tlumočníka); adaptér je pro takovou úlohu jako stvořený.
V našem případě je klientem funkce find_if a funktorem šablonová třída cJeMensiNez. Funkce find_if sice ví, co dělat s třídou cJeMensiNez, ale tato třída nesplňuje požadavky pro hledání nezáporných čísel. Pomůže adaptér:
template <class FUNKTOR> class cNegace
{
public:
   typedef typename
      FUNKTOR::result_type result_type;
   typedef typename
      FUNKTOR::argument_type argument_type;

   cNegace(FUNKTOR fc) : func_(fc) {}
   result_type operator()(argument_type x) 
      { return !func_(x); }
private:
   FUNKTOR func_;
};
Adaptér jsme zde napsali dostatečně obecně, takže dokáže znegovat téměř jakoukoli unární funkci. Vynikne zde použití vnořených typů - předem totiž nevíme, co má funktor vracet a jakého typu je jeho argument. Můžeme se ale "zeptat" - to jsou ty první dvě deklarace typedef. Adaptér si také  "pro vlastní potřebu" vytváří kopii funktoru. Je tedy nutné, aby funktor podporoval kopírování a přiřazení, a měl by se proto chovat jako hodnota (value semantics). Netřeba snad zdůrazňovat, že takto vytvořený adaptér je rovněž funktor.
První nezáporné číslo v dané posloupnosti získáme tedy takto:
iterator prvni_nezaporne = 
   find_if(cisla.begin(), cisla.end(), 
      cNegace<cJeMensiNez<int> >(
                  cJeMensiNez<int>(0)));
Tento zápis už je poněkud složitější, proto si ukážeme, jak jej zpřehlednit. Složitost plyne z toho, že při vytváření instance adaptéru musíme uvést typ instance, což je:
cNegace<cJeMensiNez<int> >
Těžko si představit, jak by to vypadalo, kdybychom měli takto vytvořit "adaptér adaptéru adaptéru funktoru" (v praxi věc celkem běžná). Naštěstí jsou tu pokročilé vlastnosti C++, o kterých sice ani nemusíte vědět, ale neškodí si je připomenout - jde o dedukci šablonových argumentů u šablonových funkcí. V praxi to vypadá tak, že vytvoříme "vytvořující" funkci:
template <class FUNKTOR>
cNegace<FUNKTOR> negace(const FUNKTOR & fc)
{
   return cNegace<FUNKTOR>(fc);
}
To je funkce, jejímž jediným úkolem je vytvořit příslušnou instanci funktoru nebo adaptéru funktoru. Díky ní už můžeme psát pouze:
iterator prvni_nezaporne = 
   find_if(cisla.begin(), cisla.end(),
      negace(cJeMensiNez<int>(0)));
Šablonová vytvořující funkce negace si totiž na základě typu svého argumentu, jímž je instance třídy cJeMensiNez<int>, dokáže vydedukovat šablonový argument. Zjistí tak, že FUNKTOR je vlastně cJeMensiNez<int>, a vytvoří instanci příslušného adaptéru.
A proč jsme tvrdili, že náš adaptér dokáže adaptovat téměř jakoukoli unární funkci? Důvodem pro použití slůvka téměř jsou vnořené definice typů. Adaptovaná funkce musí mít vnořené definice typů s pevně danými jmény. Vypadá to tedy na značné omezení, ale jen na první pohled. Pokud funkce nemá ony vnořené definice typů, nebo je má, ale jmenují se jinak, nic nám nebrání, abychom pro tuto funkci napsali speciální adaptér, který to napraví. (Takovou funkci tedy musíme adaptovat nadvakrát.) Následující sekce prozradí, jak na to.
Adaptér obyčejné funkce
Námi vytvořený adaptér cNegace nedokáže adaptovat obyčejné funkce, protože se u nich neumí "zeptat" na typ vracené hodnoty nebo typ parametru - nenajde vnořené definice typů. Naštěstí i tady existuje řešení - adaptér (jak jinak...). Budeme prostě adaptovat funkci na něco, co lze dále adaptovat...
// adaptér libovolné unární klasické funkce
template <class ARGUMENT, class VYSLEDEK>
class cFunkce
{
public:
   typedef VYSLEDEK result_type;
   typedef ARGUMENT argument_type;

   cFunkce(VYSLEDEK (*pfc)(ARGUMENT))
      : pfunc_(pfc) {}
   VYSLEDEK operator()(ARGUMENT x) 
      { return pfunc_(x); }
private:
   VYSLEDEK (*pfunc_)(ARGUMENT);
};

// vytvořující funkce
template <class ARGUMENT, class VYSLEDEK> 
cFunkce<ARGUMENT, VYSLEDEK> 
ptr_funkce(VYSLEDEK (*pf)(ARGUMENT))
{
   return cFunkce<ARGUMENT, VYSLEDEK>(pf);
}
Nyní už máme prostředky na adaptování (adaptovaných) obyčejných funkcí. Snad to trochu osvětlí následující příklad. Hledejme teď znovu první záporné číslo za použití funkce
bool mensi_nez_nula(int x)
   { return x < 0; }
Máme tři možnosti (v podstatě ekvivalentní): bez adaptéru, s adaptérem bez vytvořující funkce a s adaptérem za pomoci vytvořující funkce. Podívejme se na poslední:
iterator prvni_zaporne = 
   find_if(cisla.begin(), cisla.end(), 
      ptr_funkce(mensi_nez_nula));
Nyní se zaměříme znovu na první nezáporné číslo. S použitím vytvořujících funkcí můžeme napsat:
iterator prvni_nezaporne = 
   find_if(cisla.begin(), cisla.end(), 
      negace(ptr_funkce(mensi_nez_nula)));
Tentokrát už to projde, neboť adaptér cNegace adaptuje adaptér cFunkce (už bylo řečeno, že adaptér adaptéru je běžná věc...) a ten má vnořené definice typů.
Troufám si tvrdit, že to je elegantní a přehledné. Nemusíte ani znát detaily implementace vytvořujících funkcí či adaptérů. Stačí jenom vědět, "co to dělá" a "jak se to napíše".
Vazba argumentů
Někdy potřebujeme z binární funkce udělat unární. Jinými slovy: u funkce se dvěma parametry chceme jeden z nich zafixovat a získat tak vlastně funkci s jedním parametrem. I tady existuje elegantní řešení v podobě adaptéru. Ukážeme si to na příkladu, v němž opět hledáme první záporné číslo, ale tentokrát máme k dispozici binární funkci:
bool mensi_nez(int x, int y) 
   { return x < y; }
Chtěli bychom zafixovat druhý argument na hodnotu 0, resp. obecněji na libovolnou danou hodnotu. Vytvoříme tedy adaptér:
// adaptér fixující druhý argument 
// binární funkce bool fc(int, int)
class cFixArg2
{
public:
   cFixArg2(bool (*pfc)(int, int), int fixy) 
      : pfunc_(pfc), fixy_(fixy) {}
   bool operator()(int x) 
      { return pfunc_(x, fixy_); }
private:
   bool (*pfunc_)(int, int);
   int fixy_;
};
Finta spočívá v tom, že adaptér si "zapamatuje" zafixovanou hodnotu a při každém zavolání operátoru () ji "podstrčí" adaptované funkci jako druhý argument. Tento adaptér je tedy unární funktor (má jen jeden parametr). Použití by mohlo vypadat takto:
iterator prvni_zaporne = 
   find_if(cisla.begin(), cisla.end(), 
           cFixArg2(mensi_nez, 0));
To, co vidíte, je pouze vytvoření instance adaptéru - proto dva argumenty. O vlastní volání této (nepojmenované) instance se postará funkce find_if. Že to skutečně funguje, se můžete opět přesvědčit v [7].
Zpožděné volání
Funkce je obyčejný "kus kódu" a jediné, co s ní můžeme udělat (kromě získání adresy), je zavolat ji. Naproti tomu funktor je třída. Nejprve musíme vytvořit instanci a pak teprve můžeme volat přetížený operátor (). Nikde však není řečeno, že obě akce musí proběhnout bezprostředné po sobě. Můžeme vytvořit instanci funktoru, někam si ji uložit, a až se nám bude hodit, zavolat ji (přesněji: její přetížený operátor ()). Označujeme to jako zpožděné volání (delayed call).
Představme si, že v nějaké aplikaci (textovém editoru) zpracováváme text. Naše jednotlivé akce se ukládají jako funktory na zásobník. Stejně tak můžeme zároveň (na jiný zásobník) ukládat "antifunktory", tedy jakési protiakce, které vrací text do původního stavu. Takhle nějak by mohla vypadat implementace funkce Undo/Redo v textovém nebo libovolném jiném editoru.
Na další aplikace zpožděných volání jistě přijdete sami. Je zde ale nutné zmínit další požadavek na funktory vyplývající z toho, že jejich instance se někam ukládají. Takové funktory se totiž musí chovat jako hodnoty (value semantics). To mimo jiné znamená, že musí mít správně implementováno přiřazení a kopírování.

Příště
Po průpravě, kterou jste právě absolvovali (a snad přišli funktorům na chuť), už příště nahlédneme do STL a představíme si funktory, které pro nás tvůrci jazyka přichystali. Dozvíte se také, jak napsat vlastní funktor nebo adaptér tak, aby byly "kompatibilní" s STL, a nezapomeneme ani na nejčastější chyby a "podrazy".
Pokud vás povídání o funktorech zaujalo a chtěli byste vědět víc, doporučuji například [2]. Implementace funktorů, kterou má "na svědomí" šablonový guru A. Alexandrescu, je skutečně na úrovni, není však kompatibilní s funktory z STL (což vůbec neznamená, že by byla horší).

Jaroslav Franěk

infotipy
[1] Mezinárodní standard jazyka C++, ICO/IEC 14882:1998
[2] A. Alexandrescu: Modern C++ Design, ISBN 0-201-70431-5, Kapitola 5, Generalized Functors (Zobecněné funktory)
[3] J. Franěk: Nebojte se STL, Chip 12/01
[4] J. Franěk: Šablony výrazů v C++, Chip 4/01
[5] J. Franěk: Šablonová magie, Chip 5/01
[6] Dokumentace knihovny STL od SGI: www.sgi.com/tech/stl
[7] Zdrojový kód v rubrice Chip Plus na Chip CD 1/02