Collections

Summary

A collection is a data structure that manages a group of elements and, unlike a raw array ([[CON-0012]]), can grow, shrink, and offer operations suited to a particular access pattern — lookup by key, first-in-first-out ordering, uniqueness. Collections are how "I need to store many of these, and I don't know how many in advance" gets solved without hand-rolling array resizing every time.

Mental Model

If an array is a fixed row of bolted-together lockers, a collection is a service that manages lockers for you. You never touch the raw row yourself — you ask the service to "store this," "give me the one labeled X," or "remove this one," and it handles finding space, growing the row when it runs out, and shifting things around, using an array internally to do it.

Different collection types are different services built on that same idea, optimized for different questions:

• A List answers "give me element number N" and "what's everything, in order" — it's an array that grows itself.
• A Dictionary answers "give me the value for this key" without scanning every entry — it trades some memory for near-instant lookup.
• A Queue answers "what's the next thing that was added" (first in, first out); a Stack answers "what's the most recent thing that was added" (last in, first out).
• A HashSet answers "have I already seen this?" and guarantees no duplicates.

Choosing a collection is choosing which question you'll be asking most often — the rest of this document, and the type's own documentation, exists to help make that choice deliberately instead of by habit.

Core Explanation

Collections share a few ideas across languages even though the exact API differs:

• Dynamic sizing. A List<T> (C#) or TArray<T> (Unreal C++) grows automatically as elements are added — internally, when it runs out of room, it allocates a new, larger array and copies the old elements over. This copy is why appending is usually fast but occasionally slow (the resize moment) — see Common Mistakes.
• Generic typing. List<int>, List<string>, Dictionary<string, int> — the type of element (and, for maps, the key) is specified once, and the compiler enforces it everywhere the collection is used, unlike an ArrayList-style untyped bag.
• Interface-driven usage. Code that only needs to iterate a collection should depend on IEnumerable<T> or IReadOnlyList<T> rather than a concrete List<T>, so the caller can pass any collection that fulfills the contract (see [[CON-0011]]) — this is the same principle that makes interfaces useful for objects, applied to data.
• Ordering guarantees vary. A List<T> preserves insertion order; a Dictionary<K, V>'s enumeration order is not guaranteed by the language spec even if it appears stable in practice; a HashSet<T> makes no ordering promise at all.

Syntax / Examples

C# (Unity) — List and Dictionary

using System.Collections.Generic;

public class QuestLog : MonoBehaviour
{
    private List<string> activeQuests = new List<string>();
    private Dictionary<string, int> questProgress = new Dictionary<string, int>();

    public void StartQuest(string questId)
    {
        activeQuests.Add(questId);
        questProgress[questId] = 0;
    }

    public void AdvanceQuest(string questId, int amount)
    {
        if (questProgress.TryGetValue(questId, out int current))
        {
            questProgress[questId] = current + amount;
        }
    }

    public void CompleteQuest(string questId)
    {
        activeQuests.Remove(questId);
        questProgress.Remove(questId);
    }
}

C++ (Unreal) — TArray and TMap

TArray<FString> ActiveQuests;
TMap<FString, int32> QuestProgress;

void UQuestLog::StartQuest(const FString& QuestId)
{
    ActiveQuests.Add(QuestId);
    QuestProgress.Add(QuestId, 0);
}

void UQuestLog::AdvanceQuest(const FString& QuestId, int32 Amount)
{
    if (int32* Current = QuestProgress.Find(QuestId))
    {
        *Current += Amount;
    }
}

Unreal Blueprint

A variable's type dropdown offers Array, Set, and Map container modes directly on any type — a Map of String → Integer is Blueprint's Dictionary<string, int>. Add, Remove, Contains, and Find appear as dedicated nodes for each container type in the right-click menu.

Practical Example

An enemy spawner needs to track which enemies are currently alive so it can cap concurrent spawns and clean up references when enemies die.

public class EnemySpawner : MonoBehaviour
{
    private HashSet<GameObject> aliveEnemies = new HashSet<GameObject>();
    public int MaxConcurrent = 10;

    public bool TrySpawn(GameObject prefab, Vector3 position)
    {
        if (aliveEnemies.Count >= MaxConcurrent) return false;

        GameObject enemy = Instantiate(prefab, position, Quaternion.identity);
        aliveEnemies.Add(enemy);
        return true;
    }

    public void OnEnemyDied(GameObject enemy)
    {
        aliveEnemies.Remove(enemy);
    }
}

A HashSet<GameObject> is chosen deliberately: the spawner never needs "the 3rd enemy," only "how many are alive" (.Count) and "is this specific one still alive" (implicit in Remove being safe to call even if the enemy is already gone) — a List<GameObject> would work but Remove would be an O(n) scan instead of O(1).

Common Mistakes

• Modifying a collection while iterating it. foreach (var q in activeQuests) { if (Done(q)) activeQuests.Remove(q); } throws an InvalidOperationException in C# — the collection detects it changed mid-enumeration. Collect items to remove in a separate list first, or iterate backwards with an indexed for loop.
• Using a List<T> for lookups by key. Scanning a list with .Find() or a manual loop to answer "is X in here" is O(n); a Dictionary<K, V> or HashSet<T> answers the same question in roughly O(1). If lookups by a key happen often, the collection choice should reflect that.
• Ignoring resize cost in a hot loop. Appending to a List<T> one item at a time in a loop that runs thousands of times per frame can trigger several internal resize-and-copy operations. If the final size is known or estimable, pre-size the collection (new List<T>(capacity)) once.
• Choosing Dictionary/HashSet and relying on enumeration order. Iterating a Dictionary<K, V> and expecting entries in insertion order is not guaranteed by the language — use a List<T> (or an ordered structure) if order matters.

Best Practices

• Pick the collection type based on the dominant operation: index access → List/array; key lookup → Dictionary; membership test → HashSet; strict FIFO/LIFO ordering → Queue/Stack.
• Depend on the narrowest interface a piece of code actually needs (IReadOnlyList<T> for read-only iteration) rather than a concrete collection type, so the caller isn't forced into one implementation.
• Pre-size a collection with an estimated capacity when the approximate final count is known ahead of time, to avoid repeated internal resizes.
• Never mutate a collection while foreach-iterating it; either iterate a snapshot/copy or collect changes to apply afterward.

Exercises

1. Implement TrySpawn/OnEnemyDied from the Practical Example first with a List<GameObject> and then with a HashSet<GameObject>. Write down which operations got simpler or harder with each choice.
2. Given a Dictionary<string, int> of item name → quantity, write a method that returns the name of the most abundant item, handling the empty-dictionary case explicitly.
3. Reproduce the "modifying while iterating" exception on purpose, then fix it using a collect-then-remove pattern.
4. Given 10,000 quest IDs to check membership against repeatedly, compare (by reasoning, not necessarily by benchmarking) why a HashSet<string> is the right choice over a List<string> for that specific access pattern.

Related Concepts

• Arrays — the fixed-size building block most collections use internally to store their elements contiguously.
• Structs — value-type elements stored inside a collection copy on insertion, which changes some of a collection's performance and mutation characteristics.
• Enums — often used as dictionary keys or set members when the set of possible values is small and fixed (e.g. Dictionary<ItemRarity, int>).

References

• KNOWLEDGE_SCHEMA.md — GDKB's concept maturity ladder and cross-linking rules, which this document follows.
• Unity/.NET — System.Collections.Generic overview: https://learn.microsoft.com/dotnet/api/system.collections.generic
• Unreal Engine C++ documentation — Containers (TArray, TMap, TSet): https://dev.epicgames.com/documentation/en-us/unreal-engine/array-containers-in-unreal-engine