Bredyho blog - Ondřej Novák

Seznamy typů a jejich použití

Opět inspirován známým C++ guru: Andrei Alexandrescu jsem se vrhnul na implementaci seznamů typů "po svém". V této části si povíme co to je a k čemu to slouží.


Seznamy typů

Seznamy typů: tímto termínem se označuje zpravidla třída nebo obecně typ, který v sobě nějakým způsobem uchovává několik dalších typů. Dalo by se to přirovna vektoru, nebo listu jak známe z stl, rozdíl je v tom, že to neuchovává žádné konkrétní hodnoty, ani objekty, ale pouze typy, tedy čistě abstraktní záležitost.

Abysme pochopili k čemu je to dobré, je třeba si nejprve vysvětlit roli typů v šablonovém programování. Zatímco v každém programu existují objekty představující zpravidla instance nějakých tříd, obecně typů, a tyto objekty jsou zpravidla uloženy v proměnných, nebo kdesi v paměti aplikace, u šablon je takovým "objektem" typ a i tyto "objekty" ... tedy typy ... lze držet v proměnných. Konečně, jakákoliv deklarace se šablonou tuto proměnnou obsahuje

template<typename T>
T min(const T &a, const T &b) {return a<b?a:b;}

Ve výše uvedeném příkladě nás nebudou zajímat ani tak proměnné a,b, jako proměnná T, která bude obsahovat typ. A právě seznamy typů jsou takové vektory, které místo konkrétních objektů sdružují pouze typy.

Jak někteří tuší, nebo vědí, v C++ nenajdeme žádné nástroje na vytváření vektorů typů, něco jako template T[], prostě nehledejte. V nové verzi C++0x lze najít variadické šablony, pomocí kterých lze taková pole snadněji deklarovat. Uvedu příklad opět na funkci.

template<typename T, typename ...Rest>
void foo(const T &a, Rest... rest);

Ve výše uvedeném příkladě je seznam typů představován třemi tečky za klíčovým slovem typename . Analogicky tři tečky v parametrech funkce představují seznam dalších proměnných. Předtím, než se vrátím k čistému C++ jen dodám, že tato novinka je velice příjemná, ale problém seznamů za nás nevyřeší úplně. Proměnná s třítečkovým operátorem se totiž nedá nijak zpracovávat, třeba kdybychom chtěli seznam listovat a podobně. Seznamy typů tedy budeme potřebovat i zde, jen se nám zjednoduší deklarace takového seznamu (a padnou některé limity)

Deklarace seznamu typů v C++

Začnu od konce, a ukážeme si konečný produkt našeho článku, Totiž, jak budeme seznam typů deklarovat. Uvedu jednoduchý příklad:

using namespace TLists;
typedef List<int, bool, float, std::string> MujList;

Co si pod touto deklarací představit? Výsledkem deklarace je třída MujList, která v sobě nějakým způsobem sdružuje 4 typy: int, bool float a std::string. V tuto chvíli ale ještě nevíme, jak se k ním dostat. To si přiblížíme v následujících odstavcích. Aby to bylo dobře pochopitelné, musím nejprve vystvělit jak je seznam vnitřně uspořádán.

Implementace seznamu typů

Protože C++ nemá variadické šablony, musíme reprezentaci seznamu, kde může být teoreticky přítomno nekonečné množství prvků převést na reprezentaci, kde je omezený počet prvků. Nám budou stačit 2 prvky.

Pokud znáte jazyky LISP nebo Prolog, určitě pro vás bude nebude překvapením uspořádání do podoby "H|T". Tedy že seznam lze reprezentovat jako hlavičku, což je první prvek seznamu a následovanou tělíčkem, což je zbytek seznam. A toto tělíčko má úplně stejnou strukturu, opět rozdělenou na halvičku a tělíčko:

(int,bool,float,string) => (int,(bool,float,string)) 
=> (int,(bool,(float,string))) => (int,(bool,(float,(string, Empty))))

Vidíte, že zde máme rekurzivní strukturu dvojic. Každou tuto dvojic nazývám Node.

    Node
/ \
int Node
/ \
bool Node
/ \
float Node
/ \
string Empty

Všimněte si, že poslední Node obsahuje místo dalšího uzlu pouze jakýsi typ Empty. Ten představuje prázdný seznam a slouží jako zarážka. Bude se výborně hodit zastavování rekurzí při psaný šablon... pomocí specializace.

Jak tedy Node vypadá?


template<typename Head, typename Tail = Empty>
struct Node {

typedef Head H;
typedef Tail T;

};
struct Empty {};

Nějaká překvapení? Žádné proměnné, jen typedefy? Prvek hlavičky najdeme v H, telíčko najdeme v T.

Poznámka
Konečná podoba obou tříd je komplexnější, bude to předmětem některého dalšího dílu.

Převod List na Node

Z výkladu však není zřejmé, jak bude proveden převod z Listu na Node. Řekli jsme si, že C++ nemá variadické šablony a přesto to vypadá, jako by List tuto vlastnost uměl. Jedná se o trik. Šablona List má totiž následující deklaraci (pouze pro otrlé!)

template<
typename T1,typename T2 = Empty,typename T3 = Empty,typename T4 = Empty,
typename T11 = Empty,typename T12 = Empty,typename T13 = Empty,typename T14 = Empty,
typename T21 = Empty,typename T22 = Empty,typename T23 = Empty,typename T24 = Empty,
typename T31 = Empty,typename T32 = Empty,typename T33 = Empty,typename T34 = Empty,
typename T41 = Empty,typename T42 = Empty,typename T43 = Empty,typename T44 = Empty>
struct List: OptiNode<T1,Node<T2,Node<T3,Node<T4,
Node<T11,Node<T12,Node<T13,Node<T14,
Node<T21,Node<T22,Node<T23,Node<T24,
Node<T31,Node<T32,Node<T33,Node<T34,
Node<T41,Node<T42,Node<T43,Node<T44
> > > > > > > > > > > > > > > > > > > >::T {};

template<typename T1>
struct List<T1,Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty,
Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty>
:Node<T1> {};

Trik je zřejmý, šablona využívá výchozí hodnoty a nastavuje nevyužité pozice na Empty. Je zde vidět, že šablona List má limit na 20 typů. Není to ale fyzický limit knihovny, je to pouze limit této deklarace. Ukážeme si, že zřetězením několika takovýchto šablon lze vytvořit seznamy delší.

Ještě je potřeba zmínit, co je to OptiNode...to je optimalizátor Nodů, ten zajistí, aby nevznikaly seznamy obsahující prázdné položky Node<Empty,Node<Empty,Node<Empty,...Node<Empty,Empty> ...>>>

template<typename Head,typename Tail>
struct OptiNode {
typedef Node<Head,typename OptiNode<typename Tail::H, typename Tail::T>::T > T;
};

template<typename Tail>
struct OptiNode<Empty,Tail> {
typedef Empty T;
};

Je vidět, že OptiNode se přepisuje na adekvátní Node a pouze v případě, že je v hlavičce Empty, ukončí seznam. Aby překladač netahal původní šablonu List v celé své kráse včetně volitelných hodnot po celé aplikaci ... nechtějte vidět, jak pak vypadá výpis chyby... je lepší definovat vlastní seznam typů přes struct místo typedef.

using namespace TLists;
struct MujList: List<int, bool, float, std::string> {};

Rozdíl je v tom, že zatímco typedef pouze přiřazuje šabloně zástupné jméno (alias), struct vytváří komplet nový typ a protože potomky jsou tvořeny z Nodů, po původní šabloně List nebude ani vidu ani slechu.

Operace se seznamem

Podívejme se na možné operace se seznamem.

Délka seznamu

To je asi nejzákladnější funkce seznamu, totiž zjištění délky.

struct Empty {
//delka prazdneho seznamu je 0
static const unsigned int length = 0;
}

template<typename Head, typename Tail = Empty>
struct Node: Tail {

typedef Head H;
typedef Tail T;

//delka seznamu je delka podseznamu + 1
static const unsigned int length = T::length + 1;
};

(používám namespace _internal, pro ukrytí pomocných deklarací)

Všiměte si: proměnná length je vlastně konstantou. Překladač jí spočítá už během překladu a proto s ní můžeme nakládat jako s konstantou a používat jí v parametrech šablon!.

 std::cout << MujList::length << std::endl;

Vypíše se 4.

Zjištění typu na pozici

Velice často potřebujeme zjistit typ na zadané pozici adresované indexem stejně jako u vektoru (kde první položka má index 0). Jak na to?


template<typename List, unsigned int i>
struct TypeAt {
typedef typename TypeAt<typename List::T,i-1>::T T;
};
template<typename List>
struct TypeAt<List,0> {
typedef typename List::H T;
};

Pokud potřebuji vytvořit proměnnou typu, která je na pozici 2, zapíšu to takto:

typename TypeAt<MujList,2>::T prom;

V tomto případě bude proměnná typu float.

Sloučení dvou seznamů

Sloučení dvou seznamů se zdá, že bude komplikované, protože díky své rekurzivní struktuře nebude jednoduché nahradit u jednoho seznamu koncové Empty pokračováním seznamu druhého.

Až takový problém to není, viz následující šablona:

template<typename List1, typename List2>
struct Concat: Node<typename List1::H, Concat<typename List1::T,List2> > {};
template<typename List2>
struct Concat<Empty,List2>: List2 {};
template<typename List1>
struct Concat<List1,Empty>: List1 {};

Šablona je konstruována tak, že se vytváří nový seznam, kde se nejprve rozebírá první seznam hlavičku
po hlavičce. Jakmile je seznam prázdny (Empty), připojí se na chvost druhý seznam.

Zkuste si, co získáte pokud vytvoříte seznam:

struct MujList2:List<long *, const char *, unsigned long> {};
struct MujPokus: ConCat<MujList,MujList2> {};

Nově vzniklý seznam MujPokus bude obsahovat sloučené seznamy MujList a MujList2. Můžete se zeptat na délku i na kterýkoliv typ.

Převrácení seznamu

Někdy se hodí seznam převrátit, tedy aby na začátku byl poslední prvek a na konci byl první prvek. Opět navzdory tomu, že se jedná o rekurzivní strukturu, řešení je celkem primitivní.

template<typename L, typename R = Empty>
struct Reverse: Reverse<typename L::T, Node<typename L::H, R> > {};
template<typename R>
struct Reverse<Empty,R>: R {};

Pár řádek k vysvětlení: Šablona používý vychozí hodnotu Empty jako počáteční stav, a definuje tak chvost nového seznamu. Šablona se instacuje tak, že vždy dědí šablonu ve stavu, kdy v prvním parametru je zbytek tělíčka bez hlavičky a v druhém parametru se přidá hlavička před předchozí stav, který má na začátku hodnotu Empty. Tímto způsobem se hlavičky zepředu dostávají na konec. Po tom, co se poslední hlavička přesune na začátek druhého seznamu zbude v původním seznamu Empty a specializace šablony zajistí, že konečným výsledkem je převrácený seznam

Reverse((A,(B,(C,(D,-)))),-) => Reverse((B,(C,(D,-))),(A,-)) => Reverse((C,(D,-)),(B,(A,-)))
=> Reverse((D,-),(C,(B,(A,-)))) => Reverse(-,(D,(C,(B,(A,-)) => (D,(C,(B,(A,-))))

Hledání

Někdy může být užitečné nalezení indexu daného prvku.

template<typename List, typename Item, unsigned int pos = 0>
struct IndexOf:IndexOf<typename List::H, Item, pos + 1> {};
template<typename List, unsigned int pos>
struct IndexOf<List, typename List::H, pos>:{
const unsigned int result = pos;
};

Výše uvedená deklarace skončí chybou překladu v případě, že zadaný prvek nebude v seznamu přítomen. Pokud si to nepřejeme, musíme dodat ještě jednu specializaci, která bude tuto skutečnost nějakým způsobem indikovat, třeba číslem -1;

template<typename Item, unsigned int pos>
struct IndexOf<Empty, Item, typename List::H, pos>:{
const unsigned int result = ~0;
};

Odříznutí na pozici

Odříznutí na zadané pozici je také užitečné:

template<typename List, unsigned int pos>
struct Cut: Cut<typename List::T, pos - 1> {};
template<typename List>
struct Cut<List,0>:List {};

Například Cut<MujList,2> vytvoří dvojprvkový seznam obsahujcí typy float a string. Jak by bylo možné odříznout první polovinu seznamu?

struct MojePulka: Reverse<Cut<Reverse<MujList,2> > > {};

Využíváme převrácení seznamu, odříznutí levé půlku a převrácení zbytku zpět.

Ještě se podívejme na hledání od pozice N

template<typename List, typename Item, unsigned int pos = 0>
struct IndexOf2: IndexOf<Cut<List,pos>,Item,pos> {};

Využíváme dvou operací. Nejprve odřízneme levou část na zadné pozici a následně hledáme na pravé části. Využijeme i možnost předefinovat výchozí hodnotu pozice v šabloně IndexOf tak aby výsledkem byl správný index.

Domácí úkol
1) Napište definici nalezení posledního prvku (něco jako v C strrchr).
2) Napište definici nalezení nejbližšího prvku zprava od zadané pozice.
3) Napište definici vymazání prvku na pozici
4) Napište definici funkce Repeat - funkce má dva parametry: seznam a počet. Má fungovat tak, že zadaný vytvoří seznam jako opakování téhož seznamu.
5) Pro šílence: Napište řazení seznamu, pokud máte definovanou relaci mezi typy, například pomocí šablony Less<T1,T2>, která vrací true, když existuje relace. Není třeba to optimalizovat.

K čemu je to dobré

Hrátky se seznamy typů jsou jistě zajímavé, ale určitě se ptáte k čemu je to dobré, když výsledkem překladu kolikrát není žádný kód. Uplatnění by se našlo spoustu.

Programování pomocí šablon funguje jako celkem mocný nástroj pro generování kódu. Mít možnost nagenerovat kód podle zadaného seznamu typů tak nemusí být úplně od věci. Zvlašť, pokud díky tomuto způsobu, můžeme generování ovlivňovat "na dálku" ... to znamená například skrze parametry šablon, které s něčím takovým nepočítají.

Například, pokud mám šablonu, která přijímá jeden parametr a z nějakého důvodu jí potřebuju předat víc parametrů s tím, že si následně vytvořím specializaci k dané šabloně pro tyto parametry, je tohle jedna z možností jak toho docílit.

Neopominu ani základní použití seznamů a to k vytváření tuplů. Tuple je objekt, který vznikl tak, že se za pomocí seznamu vytvoří třída, která obsahuje tolik proměnných, kolik je položek v seznamu, kde každá proměnná je příslušného typu. Pak lze zařídit, aby návratová hodnota z funkce nebyla jedna hodnota, ale několik hodnot zkrze instanci tuple.

V další části bych se tedy zaměřil na vytváření tuplů pomocí seznamu typů, Nadefinujeme si šablonu Tuple<List<....> >. Ukážeme si, jak přistupovat k položkám tuplu a jak hodnoty v tuplech serializovat, což je výborná funkce například pro RPC komunikaci, kde za každou vzdálenou procedurou se skrývá funkce, která jedním parametrem přijímá argumenty... zpravidla jako tuple... a vrací jeden výsledek ... zpravidla také jako tuple. Díky tomu, že větší část kódu kolem tuplů nám vygeneruje překladač, práce se nám velice zjednoduší,

vytvořeno: 6.5.2010 16:56:22, změněno: 6.5.2010 18:24:02
Jsou informace v článku pro Vás užitečné?
  • (0)
  • (0)
  • (0)
  • (0)
  • (4)
Nick nebo OpenID
Vzkaz
 
28.3.2016 13:03:38

Gucci Handbags

Color: neutral color easily with a suit
Gucci Handbags http://www.charopf.com/gucci-outlet/

Podobné články

Funkce s volitelným počtem argumentů v C++ II

V předchozím díle jsme si ukázali, jak pomocí templatů vytvořit funkci přijímající libovolný počet argumentů stejného typu. Šlo by to udělat i pro argumenty libovolných typů?

Funkce s volitelným počtem argumentů v C++

Leckterý programátor v C jistě zná syntaxtický zápis funkce s volitelným počtem argumentů. V následujícím článku se podíváme na nevýhody tohoto nástroje a způsoby jak to implementovat jinak

Výletník v kostce - praktické použití domovské stránky Seznamu

VýletníkChcete mít přehled o chystaných výletech?

Dědičnost šablon, CRTP a Invoker

OOP prvky lze používat i při generickém programování pomocí šablon. Dědit šablony je snadné, podívejme se i na polymorfické šablony.

Delegování zpracování výjimky

V situacích, kdy potřebujeme určité typy výjemek zpracovat stejným způsobem, můžeme jejich zpracování delegovat do jiné funkce.
Reklama: