Egyéb adatszerkezetek

Korábban már megismertünk olyan összetett adatszerkezeteket, mint a tömb, lista vagy az összetett típusok (struktúra és osztály).

Tömbök Listák és a Foreach ciklus Összetett típusok és példányaik fork

A fentiekkel ellentétben a következő adatszerkezetek bár a C# részei, de nem szerializálhatók automatikusan a Unity-ben. Ez azt jelenti, hogy a játék futása közben bármikor használhatók arra, hogy információkat tároljunk bennük, de arra nem, hogy [SerializeField] mezőként adatokat mentsünk benne.

Mátrix - A több dimenziós tömb

Létre tudsz hozni a következő módon olyan tömböket, amit nem csak 1, de több int számmal tudsz indexelni. Ezeket nevezzük más néven gyakran mátrixoknak.

// Indexelés:
array1 [1] = "alma";
matrix2 [1,0,2] = "banán";
matrix3 [1,0,2] = "citrom";

Méret és rang lekérdezése

Egy 2D tömb kezelhető úgy mint egy “táblázat”, ahol a mátrix első dimenziója a sorok száma, a második pedig az oszlopoké. Persze mindez fordítva is elképzelhető. A mátrix értékei valójában nem a fizikai térben lesznek tárolva több dimenzióban, ez csak a vizualizálást tudja segíteni.

Végig-iterálás több dimnenziós mátrix elemein:

string[,] matrix2 = new string[10,10];

for(int i = 0; i < matrix2.GetLength(0); i++)
		for(int j = 0; j < matrix2.GetLength(1); j++)
		{
			matrix2[i, j] = (i*j).ToString();
		}

Unity-ben a több dimenziós tömböket használhatjuk például arra, hogy 2D vagy 3D térbeli adatokat tároljunk benne: Procedurálisan generált 2D négyzetrács vagy 3D voxel alapú játékok ideális példák lehetnek.

Spelunky (Remake - 2013)

Minecraft (2011)

⚠️ A programozási mátrix fogalom nem összekeverendő a matematikai mátrix fogalommal ⚠️

(A lineáris matematika mátrixai szintén “táblázatok”, de mindig 2 dimenziósak és speciális mátrix műveletek értelmezettek rajtuk. Lásd: Transzformációs mátrixok (Hamarosan) )

Szerializálható mátrixok

TODO: Leírás

Dictionary-k

A Dictionary vagy más néven Hash-Map olyan adatszerkezet, amely kulcs-érték párokat tárol. A kulcsok egyediek és indexálásra használhatók a hozzájuk tartozó értékek lekérdezésére.

A tömbök indexelésével szemben a Dictionary index típusa bármi lehet.

A Dictionary elnevezés találó, hiszen ahogy egy szótár is egy könnyen kereshető kulcshoz (szó neve) tárol el egy extra adatot (szó definíciója) ugyanúgy ezt teszi a Dictionary is.

Egyéb hasznos Dictionary műveletek:

// Dictionary bejárása kulcs-érték párok szerint
foreach (KeyValuePair<string, int> pair in studentGrades)
{
	Debug.Log("Name: " + pair.Key + ", Grade: " + pair.Value);
}

A Dictionary egyik nagy előnye, hogy a keresés nagyon gyorsan történik bennük.

A C# Dictionary osztály implementációja hash táblát használ a kulcs-érték párok tárolására. Ennek köszönhetően a keresési műveletek nagyon gyorsak lehetnek. A hash táblák hatékonyak a kulcs alapú keresésekben az alábbi okok miatt:

Hash függvények: A Dictionary használata során

Hashset

A HashSet, egyedi elemek kollekcióját tárolja sorrend nélkül. Használata hasonló a Listához a következő különbségekkel:

A HashSet-ben egy elem csak egyszer szerepelhet. Ha új elemet tennénk bele, ami már szerepel benne, nem történik semmi.
A HashSet elemeinek nincs sorrendje.
Mivel az elemeknek nincs sorrendjük, nem indexelhetők, csak foreach ciklussal lehet végig iterálni rajta.
Az elemek hozzáadása, és kivétele, valamint annak vizsgálata, hogy a set tartalmaz-e egy elemet nagy mennyiségű adathalmazon is igen gyorsan történik. (Ideális esetben O(1) a keresés sebessége a kollekció méretére nézve: )

Használata:

Tehát a HashSet akkor hasznos, ha egyedi elemeket kell tárolnunk, és gyorsan szeretnénk ellenőrizni, hogy egy adott elem már benne van-e a halmazban.

Stack

A Stack azaz verem egyik beépített adatszerkezet a C# nyelvben, és LIFO - Last-In, First-Out működést valósítja meg: A legutóbb hozzáadott elem mindig az első, amelyet eltávolíthatunk.

Fontos speciális műveletei:

Push: Az elem hozzáadása a veremhez. Az új elem mindig a legfelső pozícióra kerül.
Pop: Az elem eltávolítása a veremből. A legfelső elem kerül eltávolításra, és visszaadja azt.
Peek: A verem legfelső elemének lekérdezése anélkül, hogy az eltávolításra kerülne. Csak az elemet adja vissza.

A Stack működés szempontjából egy listához hasonló, csupán más interface-szel (függvényekkel) férünk hozzá az elemeihez.

A Stack-et használják a programozási nyelvek, például a C#, hogy nyomon kövessék egy program futását egymásba ágyazott függvényhívások mellett. Ezt a Stack-et gyakran "call stack"-nek vagy "execution stack"-nek nevezik.

A call stack egy verem, amelyben a program futása során minden függvényhívás nyomot hagy. Amikor egy függvényt meghívunk, a hívás helye, paraméterei és más releváns információk a verem tetejére kerülnek. Amikor a függvény végrehajtása befejeződik, a hívás a veremből eltávolításra kerül, és a program folytatja a következő függvény vagy utasítás végrehajtását.

Ennek a mechanizmusnak a segítségével a programok nyomon követhetik a függvényhívások sorrendjét és az aktuális visszatérési pontokat. Ez lehetővé teszi a programnak, hogy a helyes sorrendben és helyen térjen vissza a függvényekből, és tudja, a memóriában hova kell ugrani a folytatáshoz.

A call stack mérete általában véges lenni. Ez azt jelenti, hogy a call stack csak bizonyos számú függvényhívást tud tárolni, mielőtt megtelik.

Amikor egy függvény meghívódik, a szükséges hely a call stack-en a függvényhívás adatainak (visszatérési cím, paraméterek, lokális változók stb.) tárolására kerül. Ha egy program túl sok függvényt hív egymásba ágyazottan, vagy ha egy függvény túl mélyen rekurzív hívást végez, akkor a call stack megtelhet.

Amikor a call stack megtelik, akkor az újabb függvényhívások nem tudnak megtörténni, és a program futása a "StackOverflowException” hibával elszáll.

Erről kapta a nevét a népszerű programozói fórum, a stackoverflow.com

Queue

A Queue, azaz sor, egy másik beépített adatszerkezet a C# nyelvben, a Stack párja. Míg a Stack a LIFO (Last-In, First-Out) elvet követi, addig a Queue az FIFO (First-In, First-Out) elvet alkalmazza. Ez azt jelenti, hogy a Queue-ba az elemeket az egyik végén helyezzük el, és a másik végéntávolítjuk el.

Elképzelhetjük a Queue-t úgy, mint emberek sorbanállását egy pénztárnál. Aki korábban állt be, az korábban kerül kiszolgálásra

Fontos műveletei:

Enqueue: Az elem hozzáadása a sorhoz. Az új elem mindig a legutolsó pozícióra kerül.
Dequeue: Az elem eltávolítása a sorból. A legelső elem kerül eltávolításra, és visszaadja azt.
Peek: A legelső (következőre sorra kerülő) elem lekérdezése anélkül, hogy az eltávolításra kerülne.

Használata:

Miért használnék Stack-et vagy Queue-t egy feladatra, mikor a List tud mindent és még többet is?

Előnyük, hogy mivel a Queue és a Stack specifikus működést valósítanak meg, azaz egyfajta adott műveletekre fókuszálnak kifejezőbb, olvashatóbb lehet a kód.

Egyéb adatszerkezetek

Korábban már megismertünk olyan összetett adatszerkezeteket, mint a tömb, lista vagy az összetett típusok (struktúra és osztály).

Tömbök Listák és a Foreach ciklus Összetett típusok és példányaik fork

Mátrix - A több dimenziós tömb

Létre tudsz hozni a következő módon olyan tömböket, amit nem csak 1, de több int számmal tudsz indexelni. Ezeket nevezzük más néven gyakran mátrixoknak.

string[] array1 = new string[4];           // Tömb     Mérete: 4
string[,] matrix2 = new string[4,2];       // 2D tömb  Mérete: 4*2
string[,,] matrix3 = new string[4,2,3];    // 3D tömb  Mérete: 4*2*3

// Ha előre tudjuk, hogy milyen elemeket szeretnénk tárolni a mátrixban:
int[,] matrix = { { "a", "b", "c" }, { "d", "e", "f" }, { "g", "h", "i" } };
// Ebben az esetben a mátrix automatikusan inicializálódik a megfelelő méretben

// Indexelés:
array1 [1] = "alma";
matrix2 [1,0,2] = "banán";
matrix3 [1,0,2] = "citrom";

Méret és rang lekérdezése

string[,,] matrix3 = new string[5, 10, 3];  // 3D tömb  Mérete: 5*10*3
int lengt = matrix2.Length;                 // 150 = 5 * 10 * 3
int rank = matrix2.Rank;                    // 3 (Mivel 3 dimanziós a tömb)
int length0 = matrix2.GetLength(0);         // 5  - 0. dimenzió mérete
int length1 = matrix2.GetLength(1);         // 10 - 1. dimenzió mérete
int length2 = matrix2.GetLength(2);         // 3  - 2. dimenzió mérete

Végig-iterálás több dimnenziós mátrix elemein:

string[,] matrix2 = new string[10,10];

for(int i = 0; i < matrix2.GetLength(0); i++)
		for(int j = 0; j < matrix2.GetLength(1); j++)
		{
			matrix2[i, j] = (i*j).ToString();
		}

Spelunky (Remake - 2013)

Minecraft (2011)

⚠️ A programozási mátrix fogalom nem összekeverendő a matematikai mátrix fogalommal ⚠️

(A lineáris matematika mátrixai szintén “táblázatok”, de mindig 2 dimenziósak és speciális mátrix műveletek értelmezettek rajtuk. Lásd: Transzformációs mátrixok (Hamarosan) )

Szerializálható mátrixok

TODO: Leírás

[Serializable]
class SerializableMatrix<T>
{
	[SerializeField] int rows;
	[SerializeField] int columns;
	[SerializeField] T[] data;

	public int Rows => rows;
	public int Columns => columns;

	public SerializableMatrix(int rows, int columns)
	{
		this.rows = rows;
		this.columns = columns;
		data = new T[rows * columns];
	}

	public T this[int row, int column]  // Indexelő operátor
	{
		get => data[row * columns + column];
		set => data[row * columns + column] = value;
	}
}

Dictionary-k

A Dictionary vagy más néven Hash-Map olyan adatszerkezet, amely kulcs-érték párokat tárol. A kulcsok egyediek és indexálásra használhatók a hozzájuk tartozó értékek lekérdezésére.

A tömbök indexelésével szemben a Dictionary index típusa bármi lehet.

A Dictionary elnevezés találó, hiszen ahogy egy szótár is egy könnyen kereshető kulcshoz (szó neve) tárol el egy extra adatot (szó definíciója) ugyanúgy ezt teszi a Dictionary is.

using System.Collections.Generic;

//...

// Létrehozás
Dictionary<string, Vector3> positions = new Dictionary<string, Vector3>();
// Kulcs: string
// Érték: Vector3

// Kulcs-érték párok hozzáadása
positions.Add("John", new(1,2,4));
positions.Add("Emily", new(1,3,0));
positions.Add("Michael", new(7,2,2));

// Lekérdezés
Vector3 johnPsoition = positions ["John"];

// Felülrás
positions["Michael"] = new(7,3,3);

// Kulcs-érték párok törlése
studentGrades.Remove("John");

Egyéb hasznos Dictionary műveletek:

// Kulcs-érték párok száma:
int count = dictionary.Count;

// Ellenőrizzük, hogy a Dictionary tartalmazza-e a megadott kulcsot:
bool containsKey = dictionary.ContainsKey("key");

// Ellenőrizzük, hogy a Dictionary tartalmazza-e a megadott értéket.
bool containsValue = dictionary.ContainsValue(42);

// Megpróbálunk megtalálni egy értéket egy kulcs alapján
bool isFound = dictionary.TryGetValue("key", out Vector3 value);

// Az összes kulcs-érték pár eltávolítása a Dictionary-ből:
dictionary.Clear();

// Dictionary bejárása kulcs-érték párok szerint
foreach (KeyValuePair<string, int> pair in studentGrades)
{
	Debug.Log("Name: " + pair.Key + ", Grade: " + pair.Value);
}

A Dictionary egyik nagy előnye, hogy a keresés nagyon gyorsan történik bennük.

Hash függvények: A Dictionary használata során

Hashset

A HashSet, egyedi elemek kollekcióját tárolja sorrend nélkül. Használata hasonló a Listához a következő különbségekkel:

A HashSet-ben egy elem csak egyszer szerepelhet. Ha új elemet tennénk bele, ami már szerepel benne, nem történik semmi.
A HashSet elemeinek nincs sorrendje.
Mivel az elemeknek nincs sorrendjük, nem indexelhetők, csak foreach ciklussal lehet végig iterálni rajta.
Az elemek hozzáadása, és kivétele, valamint annak vizsgálata, hogy a set tartalmaz-e egy elemet nagy mennyiségű adathalmazon is igen gyorsan történik. (Ideális esetben O(1) a keresés sebessége a kollekció méretére nézve: )

Használata:

using System.Collections.Generic;

// HashSet létrehozása és elemek hozzáadása
HashSet<string> set = new HashSet<string>();
set.Add("alma");
set.Add("körte");
set.Add("szilva");
set.Add("alma"); // Duplikált elem, nem kerül hozzáadásra - Nincs error sem

// Elemek megjelenítése
foreach (string elem in set)
{
    Debug.Log(elem);
}

// Elemek számának lekérdezése
Debug.Log("Elemek száma: " + set.Count);

// Elemek eltávolítása
set.Remove("körte");

// Elemek újra megjelenítése
Debug.Log("Elemek a körte eltávolítása után:");
foreach (string elem in set)
{
    Debug.Log(elem);
}

// Ellenőrzés, hogy egy elem a halmazban van-e
bool containsAlma = set.Contains("alma");
Debug.Log("Tartalmazza az 'alma' elemet? " + containsAlma);

// HashSet ürítése
set.Clear();

Tehát a HashSet akkor hasznos, ha egyedi elemeket kell tárolnunk, és gyorsan szeretnénk ellenőrizni, hogy egy adott elem már benne van-e a halmazban.

Stack

A Stack azaz verem egyik beépített adatszerkezet a C# nyelvben, és LIFO - Last-In, First-Out működést valósítja meg: A legutóbb hozzáadott elem mindig az első, amelyet eltávolíthatunk.

Fontos speciális műveletei:

Push: Az elem hozzáadása a veremhez. Az új elem mindig a legfelső pozícióra kerül.
Pop: Az elem eltávolítása a veremből. A legfelső elem kerül eltávolításra, és visszaadja azt.
Peek: A verem legfelső elemének lekérdezése anélkül, hogy az eltávolításra kerülne. Csak az elemet adja vissza.

using System.Collections.Generic;

//...

Stack<string> stack = new Stack<string>();

stack.Push("elem1");
stack.Push("elem2");
stack.Push("elem3");

Debug.Log("A legfelső elem: " + stack.Peek());  // Elem kivétele nélkül

string removedElement = stack.Pop();
Debug.Log("Az eltávolított elem: " + removedElement);

// Elemek számának lekérdezése
Debug.Log("Elemek száma a veremben: " + stack.Count);

// Kollekció törlése
stack.Clear();

A Stack működés szempontjából egy listához hasonló, csupán más interface-szel (függvényekkel) férünk hozzá az elemeihez.

A call stack mérete általában véges lenni. Ez azt jelenti, hogy a call stack csak bizonyos számú függvényhívást tud tárolni, mielőtt megtelik.

Amikor a call stack megtelik, akkor az újabb függvényhívások nem tudnak megtörténni, és a program futása a "StackOverflowException” hibával elszáll.

Erről kapta a nevét a népszerű programozói fórum, a stackoverflow.com

Queue

Elképzelhetjük a Queue-t úgy, mint emberek sorbanállását egy pénztárnál. Aki korábban állt be, az korábban kerül kiszolgálásra

Fontos műveletei:

Enqueue: Az elem hozzáadása a sorhoz. Az új elem mindig a legutolsó pozícióra kerül.
Dequeue: Az elem eltávolítása a sorból. A legelső elem kerül eltávolításra, és visszaadja azt.
Peek: A legelső (következőre sorra kerülő) elem lekérdezése anélkül, hogy az eltávolításra kerülne.

Használata:

Queue<string> queue = new Queue<string>();

// Elemek hozzáadása a sorhoz
queue.Enqueue("Első elem");
queue.Enqueue("Második elem");
queue.Enqueue("Harmadik elem");

// Az első elem kiolvasása a sorból
string frontElement = queue.Dequeue();
Debug.Log("Az első elem a sorban: " + frontElement);

// A sor elején lévő elem lekérdezése, de nem törlése
string peekedElement = queue.Peek();
Debug.Log("A sor elején lévő elem: " + peekedElement);

// Elemek száma a sorban
Debug.Log("Elemek száma a sorban: " + queue.Count);

// Kollekció törlése
queue.Clear();

Miért használnék Stack-et vagy Queue-t egy feladatra, mikor a List tud mindent és még többet is?

Előnyük, hogy mivel a Queue és a Stack specifikus működést valósítanak meg, azaz egyfajta adott műveletekre fókuszálnak kifejezőbb, olvashatóbb lehet a kód.