/ janturon.cz / Od kodéra k analytikovi / Pole, Kolekce, Iterátor, Šablona

Kolekce, Iterátor, Šablona

Kolekce

Pole

Mladým vysokoúrovňovým programátorům přijde zvláštní, že v C se implementuje řetězec jako konstantní ukazatel na znak. V nízkoúrovňovém programování je ale třeba vyhradit proměnným množství paměti odpovídající jejím typům. Řetězce však mohou být různé délky, a zabírají proto různé množství paměti. Proto na ně bylo pohlíženo jako na posloupnost znaků ukončených binární nulou. Syntakticky např. const char* str = "Hello"; (\0 je připojena kompilátorem). Na další znak je možné dostat se posunutím ukazatele o velikost typu, např. char e = *(str+sizeof(char)). Protože tento zápis je nepohodlný a nepřehledný, vyvinul se před mnoha lety první implementovaný vzor: přístup ke znakům řetězce přes index. Nově bylo možné zapsat char str[] = "Hello"; char e = str[1]; - vzniklo pole (jeho prvky samozřejmě mohou být i jiného typu než char).

Seznam

Implementační nevýhodou pole je nutnost vyhradit mu předem paměť pro konstantní počet prvků. Jejich počet ale nemusí být předem znám, např. při objednávání zboží e-shopu do košíku. Řeší se to tak, že se stanoví rozumná výchozí velikost pole (výchozí často 10) a před pokusem o překročení kapacity se vyhradí nové pole dvojnásobné velikosti, do něhož se prvky překopírují a původní pole se uvolní. Tento stereotyp za nás dělá v jazyce C# třída ArrayList. Ta obsahuje (mimo jiné) metodu Add(), která na konec seznamu přidá další prvek, koncový uživatel se nemusí starat o překročení kapacity.

Šablona

Je-li proměnná typu ArrayList, syntaxe neříká nic o jejich prvcích. Z důvodu kompatibility se všemi typy proto bývá typu object, což je referenční datový typ nacházející se na haldě. Chceme-li ukládat hodnotový datový typ (např. int), provedeme jeho zabalení (boxing) a při čtení vybalení (unboxing). Přestože zabalení je prováděno implicitně, vybalení při čtení je obtěžující, i u referenčních typů je nutné explicitní přetypování.

ArrayList numbers = new ArrayList(); numbers.Add(1); // implicitní zabalení int n = (int)numbers[0]; // vybalení nutně explicitní

Moderní syntaxe proto umožňuje dát do špičatých závorek typovou proměnnou prvků (často označovanou jako T (type), případně dvojice K (key) a V (value). Tomu se říká šablona (je to návod pro definici pole s konkrétním typem) a má využití také ve funkcích a třídách. Kolekcím využívající šablony se říká generické kolekce. Díky typové proměnné není nutné provádět při čtení přetypování. V C# je generickým ekvivalentem ArrayListu třída List.

List<int> numbers = new List<int>(); numbers.Add(1); int n = numbers[0]; // implicitní: typ je určen šablonou

Dnes se už používají téměř výhradně generické kolekce. Podle přístupu k prvkům se nejvíce používají (názvy metod se liší dle jazyka):

Iterátor

Iterátor slouží k univerzálnímu procházení kolekcí objektů: tj. jeden zápis pro libovolný typ prvků, nejčastěji pomocí konstrukce foreach nebo alternativy standardního for.

Přestože se obecně Iterátor řadí mezi návrhové vzory, díky rozvinutým kolekcím a podpoře mnoha jazyků se málokdy implementuje, proto jsem ho zařadil už mezi implementované vzory. Jazyková podpora je následující (specializovaná syntaxe je ztučněna):

C++ string data[] = {"one","two","three","four","five"}; vector v(data,data+5); vector::iterator it; for(it=v.begin(); it!=v.end(); it++) cout << *it; C# string[] data = {"one","two","three","four","five"}; IEnumerator en = data.getEnumerator(); while(en.MoveNext()) Console.WriteLine(en.Current()); foreach(String item in data) Console.WriteLine(item); Java String[] data = {"one","two","three","four","five"}; for(String s: data) System.out.println(s); PHP $data = array("one","two","three","four","five"); foreach($data as $s) echo $s; while(list($key,$val)=each($data)) echo $val; /* Viz dále konstrukty a funkce foreach, each, list, key, current, next, prev, reset, end */

Iterátor často využívá následujících "podvzorů" (koncepcí), zapsatelných jako rozhraní:

Třídy kolekcí

 seznamslovníkzásobníkfronta
C#ArrayList
List
LinkedList
SortedList
Dictionary
SortedDictionary HashTable
StackQueue
C++ (STL)array
bitset
list
vector
map
set
bitset
stackqueue
deque

Poznámky