Obsah
- Kontejnery
- Kontejnery
- Základní kategorie kontejnerů
- Kontejnery - rozhraní, nepovinné metody
- Kontejnery - souběžný přístup, výjimky
- Iterátory
- Kolekce
- Seznamy
- Seznamy a obyčejné iterátory - příklad
- Iterátor po seznamu - příklad
- Množiny
- Množina - příklad
- Uspořádané množiny
- Uspořádaná množina - příklad s chybou
- Uspořádaná množina - příklad OK
- Mapy
- Mapa - příklad
- Uspořádané mapy
- Uspořádaná mapa - příklad
- Uspořádaná mapa - příklad s komparátorem
- Srovnání implementací kontejnerů
- Historie
- Odkazy
- Zadání úlohy 6.
-
Kontejnery jako základní dynamické struktury v Javě
-
Kolekce, iterátory (Collection, Iterator)
-
Seznamy (rozhraní List, třídy ArrayList, LinkedList)
-
Množiny (rozhraní Set, třída HashSet), uspořádané množiny (rozhraní SortedSet, třída TreeSet), rozhraní Comparable, Comparator
-
Mapy (rozhraní Map, třída HashMap), uspořádané mapy (rozhraní SortedMap, třída TreeMap)
-
Klasické netypové vs. nové typové kontejnery - generické datové typy
-
Iterace cyklem foreach
-
Starší typy kontejnerů (Vector, Stack, Hashtable)
Kontejnery (containers) v Javě
-
slouží k ukládání objektů (ne hodnot primitivních typů!)
-
v Javě koncipovány dosud jako beztypové - to se ve verzi 1.5 částečně změní!
-
tím se liší od např. Standard Template Library v C++
Většinou se používají kontejnery hotové, vestavěné, tj. ty, jež jsou součastí Java Core API:
seznam (List) - lineární struktura
množina (Set) - struktura bez uspořádání, rychlé dotazování na přítomnost prvku
asociativní pole, mapa (Map) - struktura uchovávající dvojice klíč->hodnota, rychlý přístup přes klíč
-
Funkcionalita vestavěných kontejnerů je obvykle předepsána výhradně rozhraním, jenž implementují.
-
Rozhraní však připouštějí, že některé metody jsou nepovinné, třídy jej nemusí implementovat!
-
V praxi se totiž někdy nehodí implementovat jak čtecí, tak i zápisové operace - některé kontejnery jsou „read-only“
-
Moderní kontejnery jsou nesynchronizované, nepřipouštějí souběžný přístup z více vláken.
-
Standardní, nesynchronizovaný, kontejner lze však „zabalit“ synchronizovanou obálkou.
-
Při práci s kontejnery může vzniknout řada výjimek, např. IllegalStateException apod.
-
Většina má charakter výjimek běhových, není povinností je odchytávat - pokud věříme, že nevzniknout.
Iterátory jsou prostředkem, jak "chodit" po prvcích kolekce buďto
v neurčeném pořadí nebo
v uspořádání (u uspořádaných kolekcí)
Každý iterátor musí implementovat velmi jednoduché rozhraní Iterator se třemi metodami:
jsou kontejnery implementující rozhraní Collection - API doc k rozhr. Collection
Rozhraní kolekce popisuje velmi obecný kontejner, disponující operacemi: přidávání, rušení prvku, získání iterátoru, zjišťování prázdnosti atd.
Mezi kolekce patří mimo Mapy všechny ostatní vestavěné kontejnery - List, Set
Prvky kolekce nemusí mít svou pozici danou indexem - viz např. Set
-
lineární struktury
-
implementují rozhraní List (rozšíření Collection) API doc k rozhr. List
-
prvky lze adresovat indexem (typu int)
-
poskytují možnost získat dopředný i zpětný iterátor
-
lze pracovat i s podseznamy
Vytvoříme seznam, naplníme jej a chodíme po položkách seznamovým iterátorem, vytvořeným na určité pozici (indexu) v seznamu.
K procházení seznamovým iterátorem lze použít metody next, previous.
-
jsou struktury standardně bez uspořádání prvků (ale existují i uspořádané, viz dále)
-
implementují rozhraní Set (což je rozšíření Collection)
Cílem množin je mít možnost rychle (se složitostí O(log(n))) provádět atomické operace:
vkládání prvku (add)
odebírání prvku (remove)
dotaz na přítomnost prvku (contains)
lze testovat i relaci „je podmnožinou“
Standardní implementace množiny:
hašovací tabulka (HashSet) nebo
vyhledávací strom (černobílý strom, Red-Black Tree - TreeSet)
-
Implementují rozhraní SortedSet -API doc k rozhraní SortedSet
-
Jednotlivé prvky lze tedy iterátorem procházet v přesně definovaném pořadí - uspořádání podle hodnot prvků.
-
Existuje vestavěná impl. TreeSet - černobílé stromy (Red-Black Trees) API doc ke třídě TreeSet
Vložíme prvky do uspořádané množiny. Prvky musejí implementovat rozhraní Comparable, nebo musíme poskytnout komparátor. Když neuděláme ani jedno:
Prvky implementují rozhraní Comparable:
Funguje, prvky třídy Clovek jsou porovnatelné, množina je uspořádána podle příjmení lidí.
Mapy (asociativní pole, nepřesně také hašovací tabulky nebo haše) fungují v podstatě na stejných principech a požadavcích jako Set:
Ukládají ovšem dvojice (klíč, hodnota) a umožnují rychlé vyhledání dvojice podle hodnoty klíče.
Základními metodami jsou: dotazy na přítomnost klíče v mapě (containsKey),
výběr hodnoty odpovídající zadanému klíči (get),
možnost získat zvlášt množiny klíčů, hodnot nebo dvojic (klíč, hodnota).
Mapy mají:
-
Implementují rozhraní SortedMap - API doc k rozhraní SortedMap
-
Dvojice (klíč, hodnota) jsou v nich uspořádané podle hodnot klíče.
-
Existuje vestavěná impl. TreeMap - černobílé stromy (Red-Black Trees) - API doc ke třídě TreeMap
-
Uspořádání lze ovlivnit naprosto stejným postupem jako u uspořádané množiny.
Jsou-li klíče uspořádané (pomocí implementace Comparable nebo komparátorem), mohou se prvky procházet podle uspořádání klíčů:
Příklad, kdy jsou klíče uspořádané komparátorem:
Obrázek 1.15. Vložení účtů do mapy pod uspořádaným klíčem člověka - vlastníka
package tomp.ucebnice.kolekce;
import java.util.*;
public class SortedMapComparatorDemo {
public static void main(String[] args) {
// vytvoříme mapu
SortedMap sm = new TreeMap(new ClovekComparator());
// naplníme ji třemi lidmi
Clovek c1 = new Clovek("Josef", "Vykoukal");
Ucet u1 = new Ucet(100);
sm.put(c1, u1);
Clovek c2 = new Clovek("Dalimil", "Brabec");
Ucet u2 = new Ucet(50);
sm.put(c2, u2);
Clovek c3 = new Clovek("Viktor", "Kotrba");
Ucet u3 = new Ucet(2000);
sm.put(c3, u3);
// projdi abecedně všechny vlastníky účtů v mapě
// proto je třeba získat iterátor nad množinou klíčů
for(Iterator i = sm.keySet().iterator(); i.hasNext(); ) {
Clovek majitel = (Clovek)i.next();
Ucet ucet = (Ucet)sm.get(majitel);
majitel.vypisInfo();
System.out.println(" je majitelem uctu se zustatkem "
+ ucet.zustatek + " Kc");
}
}
static class Ucet {
double zustatek;
public Ucet(double z) {
zustatek = z;
}
}
static class Clovek { // nemusí být Comparable
String jmeno, prijmeni;
Clovek (String j, String p) {
jmeno = j;
prijmeni = p;
}
public void vypisInfo() {
System.out.print("Clovek "+jmeno+" "+prijmeni);
}
}
static class ClovekComparator implements Comparator {
public int compare(Object o1, Object o2) {
// porovnává jen lidi a to podle příjmení
if (o1 instanceof Clovek && o2 instanceof Clovek) {
Clovek c1 = (Clovek)o1;
Clovek c2 = (Clovek)o2;
return c1.prijmeni.compareTo(c2.prijmeni);
} else
throw new IllegalArgumentException(
"Nelze porovnat objekt typu Clovek s objektem jineho typu");
}
}
}
na bázi pole (ArrayList) - rychlý přímý přístup (přes index)
na bázi lineárního zřetězeného seznamu (LinkedList) - rychlý sekvenční přístup (přes iterátor)
téměř vždy se používá ArrayList - stejně rychlý a paměťově efektivnější
na bázi hašovacích tabulek (HashMap, HashSet) - rychlejší, ale neuspořádané (lze získat iterátor procházející klíče uspořádaně)
na bázi vyhledávacích stromů (TreeMap, TreeSet) - pomalejší, ale uspořádané
spojení výhod obou - LinkedHashSet, LinkedHashMap - novinka v Javě 2, v1.4
Existují tyto starší typy kontejnerů (-> náhrada):
Hashtable -> HashMap, HashSet (podle účelu)
Vector -> List
Stack -> List
Roli iterátoru plnil dříve výčet (enumeration) se dvěma metodami:
Demo efektivity práce kontejnerů - Demo kolekcí
Velmi podrobné a kvalitní seznámení s kontejnery najdete na Trail: Collections