TP

.NET - Kolekce a seznamy objektů

Co tento článek ukazuje

Datové struktury které pro ukládání seznamu prvků, nebo jiné kolekce jsou potřeba ve (skoro) každé aplikaci. Prostředí .NET obsahuje kromě obvyklého pole (se kterým se ale pracuje v každém jazyce mírně odlišně) ještě několik dalších typů kolekcí. Tento tutoriál slouží jako přehled několika základních typů kolekcí a snaží se zodpovědět otázku, kdy je vhodné použít jaký typ kolekce.

Práce s polem

Základní datový typ pro ukládání seznamu objektů je pole. Pole je narozdíl od ostatních obecných datových struktur typové (takže do pole objektů typu MujObjekt nelze vložit nic jiného než MujObjekt). Hlavním omezením pole je, že jeho délka se určuje při vytvoření, takže pokud předem nevíte kolik prvků v seznamu bude, je práce s polem nešikovná. Pracovat s polem (v C#) pravděpodobně již umíte, ale pro zopakování pár základních konstrukcí:

// Vytvoreni (prazdneho) pole
int[] cisla1=new int[5];

// Inicializace pole cisel
int[] cisla2=new int[] {1,2,3,4,5}´ů

// Prochazeni prvku v poli
foreach(int i in cisla2)
  Console.WriteLine("{0}\n",i);

To byl pouze krátký úvod, protože v .NET lze s poli dělat ještě další zajímavé věci a to pomocí třídy Array. Pole je možné setřídit (a to i v případě, že v něm jsou uloženy nějaké vaše objekty) a v setřízeném poli je možno hledat (pomocí algoritmu binárního vyhledávání, který dokáže v setřízeném poli rychle vyhledávat prvek). K řazení nebo hledání v poli, které obsahuje nějaké vaše prvky je potřeba, nějakým způsobem poli umožnit porovnávat dva prvky. Existují dvě možnosti jak toto dosáhnout. První možností je předat poli objekt implementující rozhraní IComparer (obsahuje metodu, která porovnává dva prvky) a druhou možností je implementovat v prvku rozhraní IComparable (umožňuje porovnat daný prvek s jiným).

// Pole z minuleho prikladu je serazene a int
// implmentuje IComparable, tedy muzeme hledat takto: 
int pos=Array.BinarySearch(cisla,2);

Předchozí ukázka vrátí pozici 1, což je správně, protože v C# se k prvnímu prvku v poli přistupuje přes index 0 (tedy cisla[0]).
Nyní se podívejme na složitější příklad:

// V poli budeme ukladat tyto objekty
class Zamestnanec
{
  public string Jmeno;
  public int Plat;

  public Zamestnanec(string jmeno,int plat)
  {
    Jmen=jmeno; Plat=plat;
  }
}

// Objekt, ktery porovnava zamestnance podle platu
public class PorovnatPodlePlatu : IComparer
{
  // x<y - zaporne cislo; x=y - nula; x>y - kladne cislo
  public int Compare(object x, object y)
  {
    return ((Zamestnanec)x).Plat-((Zamestnanec)y).Plat;
  }
}

Zamestnanec[] zam=new Zamestnanec[5];
zam[0]=new Zamestnanec("Martin",15);
zam[1]=new Zamestnanec("Libor",10);
zam[2]=new Zamestnanec("David",5);
zam[3]=new Zamestnanec("Jiri",20);
zam[4]=new Zamestnanec("Tomas",15);

// Setridit pole podle platu
Array.Sort(zam,new PorovnatPodlePlatu());

Další kolekce

ArrayList

ArrayList je velmi užitečná kolekce, která je podobná poli, ale je "nafukovací", tedy nepotřebuje při vytváření znát celkovou délku. To je velmi vhodné při načítání dat, pokud předem neznáte počet prvků. Vnitřně ArrayList funguje tak, že si vytvoří pole nějaké délky a s ním pracuje. Pokud je kapacita nedostačující, tak si vytvoří nové delší pole a prvky do něj zkopíruje. V konstruktoru je možné předat výchozí kapacitu, takže pokud víte, že budete vkládat řádově stovky prvků je velmi vhodné vytvořit ArrayList přibližně s touto kapacitou. Vzhledem k tomu, že ArrayList vnitřně pracuje s polem, není překvapující, že existují metody ArrayList.Sort a ArrayList.BinarySearch (a další), které dělají přesně totéž co v případě pole. Další užitečnou metodou je metoda ToArray, pomocí které je možné z objektu typu ArrayList vytvořit obyčejné pole (metodě je potřeba předat jako parametr typ položky v seznamu a vrátí pole těchto položek).

Vytvorit a naplnit seznam
ArrayList list=new ArrayList();
list.Add(new Zamestnanec("Ondrej",10));
list.Add(new Zamestnanec("Jan",1));

Seradit a prevest na pole
list.Sort(new PorovnatPodlePlatu());
Zamestnanec[] zam2=
  (Zamestnanec[])list.ToArray(typeof(Zamestnanec));

Hashtable

Další zajímavá kolekce je Hashtable. Tato kolekce umožňuje podle klíče ukládat objekty, ale nepamatuje si pořadí v jakém jsou vkládány ani není možné ji třídit a není možné vložit dvakrát stejný objekt! Umožňuje ale velmi rychlý (nejrychlejší možný) přístup k prvkům podle klíče, takže pokud potřebujete například přistupovat k zaměstnancům podle jejich jména je toto ideální datová struktura.

Hashtable funguje ve zkratce tak, že objekty ukládá do nějakého vnitřního pole a index v tomto poli vypočítá z klíče pomocí hashovací funkce (GetHashCode), kterou má každý objekt. Při vkládání se objekt ukládá na takto spočítaný index a při hledání objektu podle klíče se vypočte index v poli a pokud tam je objekt s příslušným klíčem tak je vrácen. Toto samo o sobě nestačí, protože je možné že index v poli se vypočte pro dva různé objekty stejný (ikdyž je to málo pravděpodobné). V tomto případě se musí nějakým způsobem spočítat nový index v poli, dokud se nenalezne prázdné místo.

// Ulozime k zamestnanci jeho plat
Hashtable tab=new Hashtable();
tab.Add("Tomas",15);
tab.Add("Jiri",20);
tab.Add("David",5);

// .. nyni lze podle jmena rychle zjistit plat
int plat=(int)tab["Tomas"];

V tomto příkladě ukládáme k zaměstnanci přímo jeho plat, ale ve skutečné aplikaci je výhodné ukládat do Hashtable objekt, který obsahuje kompletní informace o zaměstnanci (tedy objekt Zamestnanec).

SortedList

Poslední datová struktura o které napíšu více se jmenuje SortedList a jak již jméno napovídá jedná se o seřazený seznam prvků. Do seznamu je možné jednak vkládat dvojice klíč-hodnota (řadí se podle klíče) a klíč musí být jedinečný. Pokud chcete ukládat pouze seřazený seznam objektů můžete objekty vkládat jako klíče a položku hodnota nechat prázdnou (tedy vkládat null). Vnitřně funguje SortedList velmi podobně jako ArrayList s jediným rozdílem a to, že při vkládání prvku zařadí prvek na správné místo a ne na konec seznamu. K prvkům uloženým v seznamu SortedList lze přistupovat podle klíče (sorted[klic]) a nebo podle indexu (sorted.GetByIndex(2)). Dále lze přistupovat ke kolekci obsahující vložené klíče (sorted.Keys) a hodnoty (sorted.Values).

// Seznam bude radit podle jmena
SortedList sorted=new SortedList(new PorovnatPodleJmena());

// Vlozime zamestnance jako klice
sorted.Add(new Zamestnanec("Martin",15),null);
sorted.Add(new Zamestnanec("Libor",10),null);
sorted.Add(new Zamestnanec("Jiri",20),null);

// .. zamestnanci jsou automaticky razeni
foreach(Zamestnanec zamestnanec in sorted.Keys)
  Console.WriteLine("{0} ({1})",zamestnanec.Jmeno,zamestnanec.Plat);

Další datové typy

Ve jmenném prostoru System.Collections jsou ješě dvě další třídy, které nejsou v tomto článku popsány. První z těchto tříd je zásobník (Stack), který umožňuje přidávat a odebírat prvky z vrcholu (tedy odebírají se naposledy vložené prvky). Druhá datová struktura je fronta (Queue), která umožňuje prvky z jedné strany vkládat a z druhé odebírat.

Existuje ještě mnoho dalších datových struktur, které je občas potřeba použít. .NET Framework bohužel neobsahuje implementaci žádných obecných stromových struktur, ale na www.codeproject.com naleznete několik velmi zajímavých článků na toto téma, takže pokud se chcete dozvědět více prohlédněte si odkazy v následujícím odstavci.

Soubory na stažení a odkazy

Published: Sunday, 5 June 2005, 9:19 PM
Author: Tomas Petricek
Typos: Send me a pull request!
Tags: