Kolekce (programování)
Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od
verze recenzované 28. srpna 2018; kontroly vyžadují
9 úprav .
Kolekce v programování je programový objekt, který tak či onak obsahuje sadu hodnot jednoho nebo různých typů a umožňuje vám k těmto hodnotám přistupovat.
Kolekce umožňuje zápis a načítání hodnot. Účelem sbírky je sloužit jako úložiště objektů a poskytovat k nim přístup. Kolekce se obvykle používají k ukládání skupin objektů stejného typu, které podléhají stereotypům. Pro přístup k určitému prvku kolekce lze použít různé metody v závislosti na její logické organizaci. Implementace MŮŽE umožňovat provádění jednotlivých operací na kolekcích jako celku. Přítomnost operací s kolekcemi v mnoha případech může značně zjednodušit programování.
Sbírky a kontejnery
Kolekce nebo kontejner seskupuje nějaký proměnný (možná nulový) počet datových prvků, které mají nějakou společnou hodnotu pro řešení problému. Jsou nějakým způsobem operováni. Obvykle jsou datové prvky stejného typu nebo (v jazycích, které podporují dědičnost ) budou typy odvozeny od nějakého společného typu předka. Kolekce je koncept aplikovaný na abstraktní datové typy a nepředepisuje konkrétní implementaci prostřednictvím konkrétní datové struktury, i když často existuje dobře zavedená volba. Kontejnery v teorii typů jsou abstrakce, které umožňují reprezentovat kolekce různých struktur, jako jsou seznamy a stromy , nějakým jednotným způsobem. ( unární ) kontejner je definován indexy S a rodinou typů na pozicích P indexovaných S: je dána funkce od typů indexu po typ prvku. Kontejnery lze považovat za kanonické třídy pro kolekce různých typů. Seznamy jsou indexovány prostřednictvím přirozených čísel (včetně nuly ). Seznamy mají maximální index. U stromů může být struktura stromu vyjádřena pomocí indexů bez konkrétních informací o obsahu uzlů. Indexy prvků struktury v paměti jsou izomorfní s cestami od kořene stromu k jeho uzlům .
Klasifikace
Podle obecných charakteristik
- Sbírka může mít konstantní nebo dynamicky se měnící velikost. V prvním případě lze do sbírky zapsat pouze striktně definovaný počet objektů, ve druhém sbírka umožňuje umístění tolika předmětů, kolik je potřeba (samozřejmě v mezích daných technickými omezeními). Ve většině případů, když mluvíme o kolekci, mají na mysli dynamickou kolekci, tedy kolekci druhého druhu, ačkoli například běžné statické pole je také kolekce.
- Kolekce může ukládat pouze objekty stejného typu nebo různých typů. V druhém případě se hovoří o heterogenní sbírce.
Podle logiky organizace
V závislosti na tom, jak je přístup k datům kolekce logicky organizován, se rozlišují následující hlavní typy:
- Vektor - prvky kolekce jsou seřazeny, každý má své vlastní číslo, nazývané index , pomocí kterého je k němu kdykoli přístup. Postupná celá čísla nebo hodnoty, které jsou jim předány, zpravidla fungují jako indexy. K prvku vektoru se přistupuje pomocí názvu vektoru a hodnoty indexu. Při přidávání nového prvku se přidává buď na konec vektoru nebo na pozici s daným indexem. Odebráním prvku z vektoru vznikne prázdný prvek.
- Matice – Prvky mají dva uspořádané indexy, z nichž každý je celé číslo nebo hodnota, kterou lze převést na celé číslo. Chcete-li získat přístup k prvku, musíte zadat název matice a oba indexy. Nový prvek lze přidat pouze na pozici s daným párem indexů. Odstraněním zůstane prázdný prvek.
- Vícerozměrné pole je logickým vývojem myšlenky vektoru a matice k většímu (obecně libovolnému) počtu indexů.
- Seznam - prvky kolekce jsou seřazeny, prvky nemají žádné identifikátory. Seznam je kolekce se sekvenčním přístupem. Kdykoli je k dispozici první prvek kolekce (obvykle je k dispozici i poslední prvek). Z libovolného prvku kolekce můžete přistupovat k dalšímu v pořadí, takže se můžete postupně dostat od prvního prvku seznamu k libovolnému požadovanému. Je možná implementace, která umožňuje zpětný průchod (na předchozí prvek ze známého). Nový prvek lze přidat na začátek nebo konec seznamu. Když je prvek odstraněn ze začátku seznamu, další prvek se stává prvním prvkem, když je odstraněn z konce - předchozí, ze středu - předchozí a následující prvky se stávají předchozím a následujícím prvkem pro jiný.
- Zásobník je kolekce, která implementuje princip úložiště LIFO (poslední dovnitř, první ven). V zásobníku je vždy k dispozici pouze jeden prvek - ten, který byl přidán jako poslední. Do zásobníku lze přidat nový prvek, stane se aktuálním. Aktuální prvek lze vždy odebrat ("vzít") ze zásobníku a poté prvek, který byl přidán bezprostředně předtím, než bude dostupný.
- Fronta je kolekce, která implementuje princip úložiště FIFO (first in, first out). Ve frontě je vždy dostupný pouze jeden prvek – ten, který byl přidán jako úplně první z dostupných. Když je přidán nový prvek, vstoupí do fronty. Aktuální prvek lze smazat - potom se prvek přidaný jako první ze zbývajících stane aktuálním.
- Asociativní pole (slovník) je neuspořádaná kolekce, která ukládá páry klíč–hodnota. Prvky jsou přístupné pomocí klíče. Jako klíč lze použít hodnoty různých typů, jediným omezením je, že typ klíče musí umožnit srovnání pro rovnost. Jakýkoli pár lze kdykoli odstranit. Lze přidat pouze pár (se specifickým klíčem). Může být zaveden zákaz duplikace klíčů ve sbírce. Pokud takové omezení neexistuje, lze při přístupu k duplicitnímu klíči vrátit buď n-tou nalezenou hodnotu (kde n je buď konstantní nebo určené formulářem dotazu), nebo všechny hodnoty s tímto klíčem.
- Sada je neuspořádaná kolekce, která ukládá sadu jedinečných hodnot a podporuje operace přidávání, odebírání a definování jejich výskytu. Obecně jsou pro množiny podporovány operace podobné matematickým operacím množin: sjednocení, průnik, rozdíl symetrických množin a rozdíl asymetrických množin .
- Multiset je neuspořádaná kolekce, podobná množině, ale umožňuje, aby kolekce měla dvě nebo více identických hodnot současně.
Podle implementace
Na úrovni implementace může být kolekce jednou z následujících datových struktur:
Operace s kolekcemi
V závislosti na booleovském typu kolekce a na implementaci mohou být obecně podporovány různé operace s kolekcemi. Ve všech případech lze operace provádět pouze na párech kolekcí stejného typu (a pokud kolekce nejsou heterogenní, se stejným typem prvků). Podporovány mohou být také následující operace:
- Pro všechny typy kolekcí - unie. Výsledkem takové operace je kolekce stejného typu jako operandy, obsahující všechny prvky obsažené v operandech.
- Pro vektory a matice obsahující číselné hodnoty - typické matematické operace se stejnojmennými objekty: sčítání, odčítání, násobení, transpozice.
- Pro vektory extrahujte řadu indexů. Výsledkem takové operace bude vektor stejného typu, obsahující pouze ty prvky originálu, které spadají do určitého zadaného rozsahu.
- U vektorů a seznamů řazení.
- Pro množiny sjednocení, průnik, rozdíl a symetrický rozdíl.
Pozoruhodné implementace
- Glib je knihovna, která implementuje většinu sbírek pod licencí GNU LGPL .
- STL je implementace ve formě knihovny šablon pro C++.
Viz také
Poznámky
Odkazy