Kontejner (abstraktní datový typ)

Kontejner je abstraktní datový typ, který bývá v programování implementován pomocí datové struktury, např. třídy,, 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

Související informace naleznete také v článku Typový systém#Statická typová kontrola.

Kontejnerové abstrakce lze zapsat v prakticky v libovolném programovacím jazyce, bez ohledu na jeho typový systém. 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.

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é). Moderní programovací jazyky poskytují různé přístupy pro řešení tohoto problému:

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.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Container (abstract data type) na anglické Wikipedii.

Související články

• Seznam datových struktur
• Standard Template Library
• Kolekce (abstraktní datový typ)
• Java ConcurrentMap

Externí odkazy

• Container Data Structure Declaration and Initialization