Kontejner (abstraktní datový typ)

Kontejner je abstraktní datový typ, který bývá v programování implementován pomocí datové struktury, např. třídy,^[1]^[2], jejíž instance tvoří kolekce jiných objektů. Kontejnery obsahují objekty organizované tak, aby dodržovala jistá (přístupová) pravidla. Velikost kontejneru je závislá na počtu obsažených objektů. Velikost kontejneru závisí na počtu prvků, které kontejner obsahuje. Vnitřní implementace kontejnerů mohou být různě složité a odvíjejí se od způsobu použití konkrétního kontejneru.

Kontejnerové datové struktury se často používají v mnoha typech programovacích jazyků.

Funkce a vlastnosti

Kontejnery lze charakterizován následujícími třemi vlastnostmi:

uložením, způsobem ukládání objektů kontejneru;
přístupem, což je způsob přístupu k objektům kontejneru. V případě pole se přístup uskutečňuje pomocí indexu. V případě zásobníků se přístup provádí podle strategie LIFO (poslední dovnitř, první ven) a v případě fronty podle strategie FIFO (první dovnitř, první ven);
způsobem průchodu udávajícím, jak procházet objekty kontejneru.

Kontejnerové třídy byl měly implementovat operace CRUD:

vytvoření prázdného kontejneru;
vložení objektu do kontejneru;
smazání objektu z kontejneru;
vyprázdnění kontejneru (odstranění všech objektů z kontejneru);
přístup k objektu v kontejneru;
zjištění počtu objektů v kontejneru.

Pro postupný přístup ke všem prvkům kontejneru se často používají iterátory.

Druhy kontejnerů

Kontejnery lze rozdělit na jednohodnotové kontejnery a asociativní kontejnery. Jednohodnotové kontejnery ukládají každý objekt samostatně. K objektům asociativního kontejneru lze přistupovat přímo, pomocí cyklu (například cyklus for) nebo pomocí iterátoru.

Asociativní kontejnery používají asociativní pole, mapy nebo slovníky tvořené dvojicemi klíč-hodnota tak, že každý klíč se může v kontejneru vyskytnout nejvýše jednou. Klíč se používá pro nalezení hodnoty (entity, objektu), pokud je uložen v kontejneru. Asociativní kontejnery mohou být implementovány např. jako šablony tříd.

Ke kontejnerovým abstraktním datovým typům patří:

FIFO fronty
LIFO zásobníky
Prioritní fronty
Vyhledávací tabulky (LUTs)
Asociativní pole
- Množiny obsahující a indexující objekty hodnotou nebo konkrétní vlastností;
- Mapy přiřazující každému klíči „hodnotu“ pro vyhledávání

K obvyklým datovým strukturám, pomocí nichž se implementují tyto abstraktní typy, patří:

Pole a z nich odvozené typy
Spojové seznamy
Binární vyhledávací stromy (BSTs), zvláště vyvážené
Hašovací tabulky

Grafické kontejnery

Kontejnery se používají také ve widget toolkitet. Jde o speciální ovládací prvky (widgety), které sdružují jednodušší widgety, a tvoří např. okna nebo panely. Kromě svých grafických vlastností mají obdobný účel jako kontejnerové třídy, protože udržují seznam widgetů, z nichž jsou složeny (potomků), a umožňují přidávání, odstraňování nebo vyzvedávání dalších prvků mezi své potomky.

Ve staticky typovaných jazycích

Kontejnerové abstrakce lze zapsat v prakticky v libovolném programovacím jazyce, bez ohledu na jeho typový systém.^[3]^:s.273 V silně typovaných objektově orientovaných jazycích však může být vytváření znovupoužitelných homogenních kontejnerů pro vývojáře poměrně složité.

Potřeba ukládat do různých kontejnerů různé typy prvků může v některých programovacích jazycích vést k únavnému procesu psaní a uchovávání sbírky kontejnerů pro každý typ prvku.^[3]^:s.274-276

Mnoho jednoduchých typů (například celá čísla nebo čísla s pohyblivou řádovou čárkou) je ze své podstaty vzájemně nekompatibilních kvůli velikosti paměti, kterou zabírají, a kvůli svému sémantickému významu, a proto vyžadují různé kontejnery (samozřejmě pokud nejsou vzájemně kompatibilní nebo konvertovatelné).^[3]^:s.274-276 Moderní programovací jazyky poskytují různé přístupy pro řešení tohoto problému:^[3]^:s.274-281

Univerzální základní typ: Typ, který je možné přiřadit libovolnému jinému typu (například kořenové třídě Object).
Downcasting;
Substituce tříd: Tři výše uvedené přístupy se používají ve slabě typovaných jazycích; obvykle je využita dědičnost a polymorfismus mezi typy.
Uniony (jazyk C/C++): Umožnění ukládání typů různých velikostí; je však obtížné zajistit, aby v unionu byla skutečně entita předpokládaného typu.
Přetypování
Šablony nebo generické typy: Zajišťují znovupoužitelnost a typovou bezpečnost; lze je považovat za inverzní dědičnost. Tento přístup však může vyžadovat implementaci specializací šablon, což je údajně časově náročný proces, protože typy se liší svými metodami.^[3]^:s.281