Collections (Колекції)

Вступ та Контекст

Уявіть, що ви розробляєте систему управління завданнями. Вам потрібно зберігати список задач, швидко знаходити завдання за ідентифікатором, відстежувати історію змін і забезпечити безпечний доступ з різних потоків. Спроба вирішити це за допомогою звичайного масиву (T[]) швидко виявить його обмеження:

• Фіксований розмір: Масиви створюються з визначеною довжиною, яку неможливо змінити. Якщо вам потрібно додати більше елементів, ніж було заплановано, єдиний вихід — створити новий, більший масив і скопіювати в нього всі старі елементи. Це вкрай неефективно.
• Відсутність вбудованих операцій: Масиви не пропонують готових методів для пошуку, вставки чи видалення елементів. Пошук елемента вимагає ручного перебору в циклі (складність O(n)), а вставка в середину — складного зсуву елементів вручну.
• Не потокобезпечність (Not Thread-Safe): Якщо декілька потоків одночасно намагаються читати й записувати в масив, можуть виникнути стани гонитви (race conditions). Наприклад, один потік може перезаписати значення, яке інший потік ще не встиг прочитати, що призведе до пошкодження даних або непередбачуваної поведінки програми.

Саме для вирішення цих та багатьох інших проблем .NET надає багатий набір колекцій (Collections) — спеціалізованих структур даних, кожна з яких оптимізована під конкретні завдання. Це не просто "динамічні масиви", а складні інструменти, що реалізують класичні алгоритми та структури даних (хеш-таблиці, дерева, зв'язні списки), надаючи розробнику простий та ефективний API. Від динамічних списків до потокобезпечних словників, від незмінних колекцій до асинхронних каналів — кожна колекція має своє чітке призначення та компроміси у продуктивності.

Еволюція колекцій у .NET

Навіщо потрібні різні колекції?

Вибір правильної колекції напряму впливає на продуктивність вашого застосунку. Ключовим критерієм вибору є асимптотична складність операцій, яку описують за допомогою нотації Big O. Вона показує, як час виконання операції (або використання пам'яті) зростає зі збільшенням кількості елементів (n) у колекції.

Розглянемо основні сценарії:

Ось порівняльна таблиця для найпоширеніших колекцій:

• Амортизована складність (Amortized): List<T> має амортизовану складність O(1) для додавання в кінець. Більшість додавань справді виконуються за O(1), але час від часу відбувається дорога операція розширення масиву (O(n)). Однак, оскільки розширення трапляються рідко, середня вартість операції, "розмазана" по великій кількості додавань, наближається до O(1).
• Середня складність (Average): Dictionary та HashSet мають середню складність O(1) для операцій додавання, пошуку та видалення. Це означає, що за умови якісної хеш-функції та рівномірного розподілу елементів, операція виконується за константний час. У найгіршому випадку (коли всі ключі потрапляють в один "бакет" через колізії), складність може деградувати до O(n).

Фундаментальні Концепції

Ієрархія інтерфейсів

graph TB
    IEnumerable[IEnumerable<T>]
    ICollection[ICollection<T>]
    IList[IList<T>]
    IDictionary[IDictionary<TKey,TValue>]
    ISet[ISet<T>]

    IEnumerable --> ICollection
    ICollection --> IList
    ICollection --> IDictionary
    ICollection --> ISet

    List[List<T>]
    Dictionary[Dictionary<TKey,TValue>]
    HashSet[HashSet<T>]
    LinkedList[LinkedList<T>]

    IList -.-> List
    IDictionary -.-> Dictionary
    ISet -.-> HashSet
    ICollection -.-> LinkedList

    style IEnumerable fill:#3b82f6,stroke:#1d4ed8,color:#ffffff
    style ICollection fill:#3b82f6,stroke:#1d4ed8,color:#ffffff
    style List fill:#f59e0b,stroke:#b45309,color:#ffffff
    style Dictionary fill:#f59e0b,stroke:#b45309,color:#ffffff

В основі всіх колекцій .NET лежить продумана ієрархія інтерфейсів. Розуміння цієї ієрархії дозволяє писати більш гнучкий та абстрактний код. Наприклад, якщо ваш метод лише перебирає елементи, він повинен приймати IEnumerable<T>, а не конкретний List<T>. Це дозволить передавати в нього будь-яку колекцію, включаючи масиви.

Ключові інтерфейси:

• IEnumerable<T>: Це найпростіший і найфундаментальніший інтерфейс. Його єдина мета — надати можливість послідовного перебору елементів колекції, наприклад, у циклі foreach. Він визначає лише один метод — GetEnumerator(), який повертає ітератор. Цей інтерфейс реалізують абсолютно всі колекції в .NET.
• ICollection<T>: Розширює IEnumerable<T>, додаючи базові операції для модифікації колекції та отримання її розміру. Він включає такі члени, як Add(T), Remove(T), Clear(), Contains(T) та властивість Count. Цей інтерфейс підходить, коли вам потрібно не тільки перебирати елементи, а й керувати їх складом.
• IList<T>: Розширює ICollection<T> і представляє колекцію, до елементів якої можна отримати доступ за індексом (порядковим номером). Він додає такі члени, як індексатор this[int], Insert(int, T) та RemoveAt(int). List<T> є основною реалізацією цього інтерфейсу.
• IDictionary<TKey,TValue>: Розширює ICollection<KeyValuePair<TKey, TValue>>. Представляє колекцію пар "ключ-значення". Ключі мають бути унікальними. Надає швидкий доступ до значень за ключем через індексатор this[TKey]. Реалізується Dictionary<TKey, TValue>.
• ISet<T>: Розширює ICollection<T> і представляє колекцію, що містить тільки унікальні елементи. Надає методи для виконання стандартних математичних операцій над множинами, таких як UnionWith (об'єднання), IntersectWith (перетин) та ExceptWith (різниця). Реалізується HashSet<T>.

Generic Collections

List<T>

Це найпопулярніша і найуніверсальніша колекція в .NET. Вона надає функціональність динамічного масиву (dynamic array), що означає, що її розмір може збільшуватися за потребою, на відміну від звичайних масивів. List<T> ідеально підходить для сценаріїв, де потрібен швидкий доступ до елементів за індексом та часте додавання або видалення елементів у кінці списку.

Внутрішньо List<T> є обгорткою над звичайним масивом (T[]). Ця внутрішня структура і визначає її характеристики продуктивності.

Внутрішня структура

graph LR
    subgraph "List<int> capacity=4, count=3"
        A[0: 42]
        B[1: 17]
        C[2: 99]
        D[3: empty]
    end
    style A fill:#3b82f6,stroke:#1d4ed8,color:#ffffff
    style B fill:#3b82f6,stroke:#1d4ed8,color:#ffffff
    style C fill:#3b82f6,stroke:#1d4ed8,color:#ffffff
    style D fill:#64748b,stroke:#334155,color:#ffffff

Розуміння різниці між Count та Capacity є ключовим для ефективного використання List<T>:

• Count — це публічна властивість, що показує, скільки елементів фактично міститься в списку. Це те, з чим ви зазвичай працюєте.
• Capacity — це внутрішня характеристика, що вказує на розмір внутрішнього масиву, який List<T> використовує для зберігання елементів. Capacity завжди більше або дорівнює Count.

Різниця між цими двома значеннями — це резерв вільних місць, який дозволяє додавати нові елементи без необхідності негайного розширення масиву.

Стратегія зростання

Коли Count стає рівним Capacity і ви намагаєтеся додати новий елемент, List<T> виконує таку операцію:

1. Створює новий масив удвічі більшого розміру (поведінка за замовчуванням, може відрізнятися в деталях реалізації різних версій .NET).
2. Копіює всі елементи зі старого масиву в новий.
3. Старий масив позначається для збирання сміття (GC).
4. Внутрішнє посилання оновлюється, щоб вказувати на новий, більший масив.

Цей процес ілюструє приклад:

var list = new List<int>(2); // Початкова capacity = 2
Console.WriteLine($"Capacity: {list.Capacity}, Count: {list.Count}"); // 2, 0

list.Add(10); // Додаємо 1-й елемент
list.Add(20); // Додаємо 2-й, capacity ще достатньо
Console.WriteLine($"Capacity: {list.Capacity}, Count: {list.Count}"); // 2, 2

list.Add(30); // Потрібно розширити! 2 * 2 = 4
Console.WriteLine($"Capacity: {list.Capacity}, Count: {list.Count}"); // 4, 3

list.Add(40);
list.Add(50); // Знову розширення: 4 * 2 = 8
Console.WriteLine($"Capacity: {list.Capacity}, Count: {list.Count}"); // 8, 5

Основні методи

List<string> tasks = new();

// Додавання в кінець - O(1) амортизована
tasks.Add("Fix bug #123");

// Додавання діапазону
tasks.AddRange(new[] { "Code review", "Write docs" });

// Вставка в позицію - O(n), бо зсув елементів
tasks.Insert(0, "URGENT: Deploy hotfix");

Console.WriteLine(string.Join(", ", tasks));
// URGENT: Deploy hotfix, Fix bug #123, Code review, Write docs

List<int> numbers = [5, 12, 3, 19, 7, 12];

// Пошук за значенням - O(n)
bool exists = numbers.Contains(12); // true
int index = numbers.IndexOf(12);   // 1 (перший збіг)
int lastIdx = numbers.LastIndexOf(12); // 5

// Пошук за умовою
int? firstBig = numbers.Find(x => x > 10); // 12
List<int> allBig = numbers.FindAll(x => x > 10); // [12, 19, 12]
int idx = numbers.FindIndex(x => x > 10); // 1

List<string> items = ["apple", "banana", "cherry", "banana"];

// Видалення першого збігу - O(n)
items.Remove("banana"); // ["apple", "cherry", "banana"]

// Видалення за індексом - O(n)
items.RemoveAt(0); // ["cherry", "banana"]

// Видалення за умовою
items.RemoveAll(x => x.StartsWith("b")); // ["cherry"]

// Очищення
items.Clear(); // []

Сортування

List<int> nums = [42, 3, 17, 99, 5];

// In-place сортування (QuickSort) - O(n log n)
nums.Sort();
Console.WriteLine(string.Join(", ", nums)); // 3, 5, 17, 42, 99

// Reverse sort
nums.Sort((a, b) => b.CompareTo(a));
Console.WriteLine(string.Join(", ", nums)); // 99, 42, 17, 5, 3

// Custom sorting
List<Person> people = [
    new("Alice", 30),
    new("Bob", 25),
    new("Charlie", 30)
];

people.Sort((p1, p2) => {
    int ageComp = p1.Age.CompareTo(p2.Age);
    return ageComp != 0 ? ageComp : p1.Name.CompareTo(p2.Name);
});
// Bob(25), Alice(30), Charlie(30)

record Person(string Name, int Age);

Dictionary<TKey, TValue>

Це одна з найважливіших та найефективніших колекцій, що реалізує структуру даних хеш-таблиця (hash table). Її головне призначення — надзвичайно швидке зберігання та пошук даних за ключем. Середня асимптотична складність для операцій додавання, пошуку та видалення становить O(1), що робить її ідеальною для кешування, індексації даних та будь-яких сценаріїв, де швидкість пошуку є критичною.

Принцип роботи Hash Table

Магія швидкості Dictionary полягає в тому, як вона організовує дані. Замість послідовного перебору, вона миттєво обчислює "адресу" елемента на основі його ключа.

graph TB
    subgraph "Dictionary Buckets"
        B0["Bucket 0: (Key1, Val1)"]
        B1["Bucket 1: (Key2, Val2) → (Key5, Val5)"]
        B2["Bucket 2: empty"]
        B3["Bucket 3: (Key3, Val3)"]
    end
    style B1 fill:#f59e0b,stroke:#b45309,color:#ffffff
    style B0 fill:#3b82f6,stroke:#1d4ed8,color:#ffffff
    style B3 fill:#3b82f6,stroke:#1d4ed8,color:#ffffff

На схемі вище показано, що Key2 і Key5 мали хеш-коди, які після обчислення індексу вказали на Bucket 1. Відбулася колізія, і Dictionary сформував у цьому кошику зв'язаний список, де (Key2, Val2) стоїть першим, а (Key5, Val5) — наступним. При пошуку, наприклад, Key5, Dictionary спочатку перевірить Key2, і, не знайшовши збігу, перейде до наступного елемента у списку.

Використання

Dictionary<string, int> scores = new();

// Додавання - O(1) середня
scores.Add("Alice", 95);
scores["Bob"] = 87; // Індексатор (додає або оновлює)

// Спроба додати існуючий ключ
try {
    scores.Add("Alice", 100); // ArgumentException!
} catch (ArgumentException) {
    Console.WriteLine("Key already exists");
}

// Безпечне додавання (.NET 5+)
bool added = scores.TryAdd("Charlie", 92); // true
added = scores.TryAdd("Alice", 100); // false

Dictionary<string, int> scores = new() {
    ["Alice"] = 95,
    ["Bob"] = 87
};

// Небезпечний спосіб
int aliceScore = scores["Alice"]; // 95
// int eveScore = scores["Eve"]; // KeyNotFoundException!

// Безпечний спосіб
if (scores.TryGetValue("Eve", out int eveScore)) {
    Console.WriteLine($"Eve: {eveScore}");
} else {
    Console.WriteLine("Eve not found");
}

// Отримання з fallback (.NET 6+)
int defaultScore = scores.GetValueOrDefault("Eve", 0); // 0

Dictionary<string, int> scores = new() {
    ["Alice"] = 95,
    ["Bob"] = 87
};

// Перевірка існування ключа
bool hasAlice = scores.ContainsKey("Alice"); // true
bool hasValue87 = scores.ContainsValue(87); // true (повільно, O(n)!)

// Видалення
bool removed = scores.Remove("Bob"); // true, повертає success
removed = scores.Remove("Eve"); // false

// Clear
scores.Clear();

Якість Hash Function

// ❌ ПОГАНА hash function (всі об'єкти в одному bucket)
public class BadPerson {
    public string Name { get; init; }
    public int Age { get; init; }

    public override int GetHashCode() => 42; // Завжди однаковий!
}

// ✅ ХОРОША hash function
public class GoodPerson {
    public string Name { get; init; }
    public int Age { get; init; }

    public override int GetHashCode() => HashCode.Combine(Name, Age);

    public override bool Equals(object? obj)
    {
        // Перевіряємо, чи об'єкт не null і чи є він екземпляром GoodPerson
        if (obj is not GoodPerson p)
        {
            return false;
        }
        // Порівнюємо ключові поля
        return Name == p.Name && Age == p.Age;
    }
}

HashSet<T>

HashSet<T> — це колекція, що гарантує зберігання тільки унікальних елементів. Вона реалізована на основі тієї ж хеш-таблиці, що й Dictionary<TKey, TValue>, але зберігає лише ключі (без значень).

Завдяки цьому HashSet<T> забезпечує надзвичайно високу продуктивність (в середньому O(1)) для операцій додавання, видалення та перевірки наявності елемента. Це робить її ідеальним інструментом для:

• Дедуплікації: швидкого видалення повторюваних елементів з іншої колекції.
• Перевірки унікальності: ефективного відстеження елементів, які ви вже обробили.
• Математичних операцій над множинами: об'єднання, перетину, різниці тощо.

Операції над множинами (Set Operations)

Сила HashSet<T> полягає в ефективній реалізації класичних операцій над множинами. Усі ці операції виконуються дуже швидко, зазвичай за час, пропорційний сумі розмірів колекцій.

HashSet<int> setA = [1, 2, 3, 4, 5];
HashSet<int> setB = [4, 5, 6, 7, 8];

// Union (об'єднання): A ∪ B
HashSet<int> union = new(setA);
union.UnionWith(setB);
Console.WriteLine(string.Join(", ", union)); // 1, 2, 3, 4, 5, 6, 7, 8

// Intersect (перетин): A ∩ B
HashSet<int> intersect = new(setA);
intersect.IntersectWith(setB);
Console.WriteLine(string.Join(", ", intersect)); // 4, 5

// Except (різниця): A \ B
HashSet<int> except = new(setA);
except.ExceptWith(setB);
Console.WriteLine(string.Join(", ", except)); // 1, 2, 3

// Symmetric Except (симетрична різниця): (A \ B) ∪ (B \ A)
HashSet<int> symExcept = new(setA);
symExcept.SymmetricExceptWith(setB);
Console.WriteLine(string.Join(", ", symExcept)); // 1, 2, 3, 6, 7, 8

Практичний приклад: Дедуплікація

List<string> duplicates = ["apple", "banana", "apple", "cherry", "banana", "apple"];

// Спосіб 1: Через HashSet
HashSet<string> unique = new(duplicates);
Console.WriteLine(string.Join(", ", unique)); // apple, banana, cherry

// Спосіб 2: LINQ Distinct (під капотом використовує HashSet)
var uniqueLinq = duplicates.Distinct();

// Порівняння продуктивності для 1,000,000 елементів:
// HashSet: ~50ms, Distinct(): ~55ms (overhead від LINQ)

Queue<T> та Stack<T>

Queue<T> — FIFO (First In, First Out)

Queue<string> taskQueue = new();

// Enqueue - додавання в кінець
taskQueue.Enqueue("Task 1");
taskQueue.Enqueue("Task 2");
taskQueue.Enqueue("Task 3");

// Peek - подивитися перший без видалення
string next = taskQueue.Peek(); // "Task 1"

// Dequeue - забрати та видалити перший
string task = taskQueue.Dequeue(); // "Task 1"
Console.WriteLine($"Processing: {task}");

// TryDequeue - безпечний варіант (.NET 5+)
if (taskQueue.TryDequeue(out string? item)) {
    Console.WriteLine($"Got: {item}"); // "Task 2"
}

taskQueue.Clear();

Use Cases:

• Черги завдань (job queues)
• BFS (Breadth-First Search) алгоритми
• Message queues

Stack<T> — LIFO (Last In, First Out)

Stack<string> undoStack = new();

// Push - додавання на вершину
undoStack.Push("Action 1");
undoStack.Push("Action 2");
undoStack.Push("Action 3");

// Peek - подивитися вершину
string last = undoStack.Peek(); // "Action 3"

// Pop - забрати вершину
string undo = undoStack.Pop(); // "Action 3"
Console.WriteLine($"Undo: {undo}");

// TryPop - безпечний варіант (.NET 5+)
if (undoStack.TryPop(out string? item)) {
    Console.WriteLine($"Undo: {item}"); // "Action 2"
}

Use Cases:

• Undo/Redo механізми
• DFS (Depth-First Search) алгоритми
• Expression evaluation (постфіксні вирази)
• Call stack emulation

LinkedList<T>

Doubly linked list (двозв'язний список). Кожен вузол має посилання на наступний та попередній.

graph LR
    HEAD["HEAD"] --> A["Node: 10"]
    A --> B["Node: 20"]
    B --> C["Node: 30"]
    C --> TAIL["TAIL"]

    TAIL -.-> C
    C -.-> B
    B -.-> A
    A -.-> HEAD

    style A fill:#3b82f6,stroke:#1d4ed8,color:#ffffff
    style B fill:#3b82f6,stroke:#1d4ed8,color:#ffffff
    style C fill:#3b82f6,stroke:#1d4ed8,color:#ffffff

LinkedList<int> list = new();

// Додавання в кінець/початок - O(1)
list.AddLast(20);
list.AddFirst(10);
list.AddLast(30);
// 10 ↔ 20 ↔ 30

// Отримання вузла
LinkedListNode<int>? node20 = list.Find(20);

if (node20 != null) {
    // Вставка після вузла - O(1)!
    list.AddAfter(node20, 25);
    // 10 ↔ 20 ↔ 25 ↔ 30

    // Вставка перед вузлом
    list.AddBefore(node20, 15);
    // 10 ↔ 15 ↔ 20 ↔ 25 ↔ 30

    // Видалення вузла - O(1)
    list.Remove(node20);
    // 10 ↔ 15 ↔ 25 ↔ 30
}

Concurrent Collections

Для багатопоточного програмування звичайні колекції небезпечні (race conditions). Concurrent collections надають thread-safe методи.

ConcurrentDictionary<TKey, TValue>

using System.Collections.Concurrent;

ConcurrentDictionary<string, int> cache = new();

// Thread-safe додавання
cache.TryAdd("key1", 100);

// Atomic update: отримати або додати
int value = cache.GetOrAdd("key2", k => {
    Console.WriteLine($"Generating value for {k}");
    return 200; // Викликається тільки якщо ключа немає
});

// Atomic update: оновити або додати
cache.AddOrUpdate(
    key: "key1",
    addValue: 999,  // Значення для додавання
    updateValueFactory: (k, oldValue) => oldValue + 10 // 100 + 10 = 110
);

// Умовне оновлення
bool updated = cache.TryUpdate("key1", newValue: 150, comparisonValue: 110);
// true якщо поточне значення == 110

Console.WriteLine(cache["key1"]); // 150

BlockingCollection<T>

Producer-Consumer pattern для передачі даних між потоками.

using System.Collections.Concurrent;

BlockingCollection<int> queue = new(boundedCapacity: 10);

// Producer thread
Task producer = Task.Run(() => {
    for (int i = 0; i < 20; i++) {
        queue.Add(i); // Блокується якщо queue повна (10 елементів)
        Console.WriteLine($"Produced: {i}");
        Thread.Sleep(100);
    }
    queue.CompleteAdding(); // Сигнал що більше не буде елементів
});

// Consumer thread
Task consumer = Task.Run(() => {
    foreach (int item in queue.GetConsumingEnumerable()) {
        Console.WriteLine($"\tConsumed: {item}");
        Thread.Sleep(200);
    }
});

await Task.WhenAll(producer, consumer);

System.Threading.Channels

Сучасна альтернатива BlockingCollection з async/await підтримкою.

using System.Threading.Channels;

Channel<int> channel = Channel.CreateUnbounded<int>();

// Producer
Task producer = Task.Run(async () => {
    for (int i = 0; i < 10; i++) {
        await channel.Writer.WriteAsync(i);
        Console.WriteLine($"Produced: {i}");
    }
    channel.Writer.Complete();
});

// Consumer
Task consumer = Task.Run(async () => {
    await foreach (int item in channel.Reader.ReadAllAsync()) {
        Console.WriteLine($"\tConsumed: {item}");
    }
});

await Task.WhenAll(producer, consumer);

using System.Threading.Channels;

var options = new BoundedChannelOptions(capacity: 5) {
    FullMode = BoundedChannelFullMode.Wait // Блокувати при переповненні
};

Channel<string> channel = Channel.CreateBounded<string>(options);

// Producer (швидкий)
Task producer = Task.Run(async () => {
    for (int i = 0; i < 20; i++) {
        await channel.Writer.WriteAsync($"Message {i}");
        Console.WriteLine($"[{DateTime.Now:HH:mm:ss.fff}] Produced: {i}");
        await Task.Delay(50);
    }
    channel.Writer.Complete();
});

// Consumer (повільний)
Task consumer = Task.Run(async () => {
    await foreach (var msg in channel.Reader.ReadAllAsync()) {
        Console.WriteLine($"[{DateTime.Now:HH:mm:ss.fff}]\t\tConsumed: {msg}");
        await Task.Delay(200);
    }
});

await Task.WhenAll(producer, consumer);

Immutable Collections

Immutable collections створюють нову версію при кожній зміні (structural sharing для ефективності).

using System.Collections.Immutable;

// Створення immutable list
ImmutableList<int> list1 = ImmutableList.Create(1, 2, 3);

// "Додавання" створює нову версію
ImmutableList<int> list2 = list1.Add(4);

Console.WriteLine(string.Join(", ", list1)); // 1, 2, 3 (незмінний!)
Console.WriteLine(string.Join(", ", list2)); // 1, 2, 3, 4

// Builder для багатьох змін
ImmutableList<int>.Builder builder = ImmutableList.CreateBuilder<int>();
for (int i = 0; i < 1000; i++) {
    builder.Add(i); // Mutable операції
}
ImmutableList<int> final = builder.ToImmutable();

Use Cases:

• Functional programming patterns
• Event sourcing (історія змін)
• Thread-safe reads без локів
• Undo/Redo з efficient storage

IEnumerable<T> та Yield Return

Lazy Evaluation

IEnumerable<int> GetNumbers() {
    Console.WriteLine("Start");
    yield return 1;
    Console.WriteLine("After 1");
    yield return 2;
    Console.WriteLine("After 2");
    yield return 3;
    Console.WriteLine("End");
}

// Виклик НЕ виконує метод!
IEnumerable<int> numbers = GetNumbers();
Console.WriteLine("Enumerable created");

// Виконання починається при ітерації
foreach (int num in numbers) {
    Console.WriteLine($"Got: {num}");
}

// Вивід:
// Enumerable created
// Start
// Got: 1
// After 1
// Got: 2
// After 2
// Got: 3
// End

State Machine

Компілятор генерує state machine для yield return:

// Що пише розробник:
IEnumerable<int> Count(int max) {
    for (int i = 0; i < max; i++) {
        yield return i;
    }
}

// Що генерує компілятор (спрощено):
class CountEnumerator : IEnumerator<int> {
    private int state = 0;
    private int current;
    private int max;
    private int i;

    public bool MoveNext() {
        switch (state) {
            case 0:
                i = 0;
                goto case 1;
            case 1:
                if (i < max) {
                    current = i;
                    state = 1;
                    i++;
                    return true;
                }
                return false;
            default:
                return false;
        }
    }

    public int Current => current;
}

Arrays та Collection Expressions

Multidimensional vs Jagged Arrays

// Rectangular array (багатовимірний)
int[,] matrix = new int[3, 4]; // 3 рядки, 4 стовпці
matrix[0, 0] = 1;
matrix[2, 3] = 99;

// Ініціалізація
int[,] grid = {
    { 1, 2, 3 },
    { 4, 5, 6 },
    { 7, 8, 9 }
};

// Ітерація
for (int i = 0; i < grid.GetLength(0); i++) {
    for (int j = 0; j < grid.GetLength(1); j++) {
        Console.Write($"{grid[i, j]} ");
    }
    Console.WriteLine();
}

// Jagged array (зубчастий) - масив масивів
int[][] jagged = new int[3][];
jagged[0] = new int[] { 1, 2 };
jagged[1] = new int[] { 3, 4, 5, 6 };
jagged[2] = new int[] { 7 };

// Ініціалізація
int[][] triangle = [
    [1],
    [2, 3],
    [4, 5, 6]
];

// Ітерація
for (int i = 0; i < triangle.Length; i++) {
    for (int j = 0; j < triangle[i].Length; j++) {
        Console.Write($"{triangle[i][j]} ");
    }
    Console.WriteLine();
}

Collection Expressions (C# 12)

Новий синтаксис [] для ініціалізації колекцій:

// Масиви
int[] array = [1, 2, 3, 4, 5];

// List
List<string> list = ["apple", "banana", "cherry"];

// Span
Span<int> span = [10, 20, 30];

// HashSet (потрібен explicit type)
HashSet<int> set = [1, 2, 3, 2, 1]; // {1, 2, 3}

// Spread operator ..
int[] first = [1, 2, 3];
int[] second = [7, 8, 9];
int[] combined = [0, ..first, 4, 5, 6, ..second, 10];
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

// Empty collection
List<int> empty = [];

Best Practices

1. Pre-allocate Capacity

// ❌ Погано: багато resizing
var list = new List<int>();
for (int i = 0; i < 10000; i++) {
    list.Add(i);
}

// ✅ Добре
var list = new List<int>(capacity: 10000);
for (int i = 0; i < 10000; i++) {
    list.Add(i);
}

2. TryGetValue замість ContainsKey + indexer

// ❌ Погано: два lookup
if (dict.ContainsKey("key")) {
    int value = dict["key"];
}

// ✅ Добре: один lookup
if (dict.TryGetValue("key", out int value)) {
    // використовуємо value
}

3. Не модифікуйте колекцію під час ітерації

var list = new List<int> { 1, 2, 3, 4, 5 };

// ❌ InvalidOperationException!
foreach (int num in list) {
    if (num % 2 == 0) {
        list.Remove(num);
    }
}

// ✅ Варіант 1: ToList()
foreach (int num in list.ToList()) {
    if (num % 2 == 0) {
        list.Remove(num);
    }
}

// ✅ Варіант 2: RemoveAll
list.RemoveAll(x => x % 2 == 0);

Troubleshooting

InvalidOperationException: Collection was modified

Причина: Модифікація колекції під час foreach.

Рішення:

• Використовуйте ToList() для копії
• RemoveAll(), Where() замість ручного Remove
• Ітеруйте в зворотному порядку через for (для видалення)

KeyNotFoundException

Причина: Доступ до несправжнього ключа через dict[key].

Рішення:

// Замість:
int value = dict[key];

// Використовуйте:
if (dict.TryGetValue(key, out int value)) { ... }
// або
int value = dict.GetValueOrDefault(key, defaultValue: -1);

OutOfMemoryException

Причина: Колекція занадто велика (List capacity doubling при 2GB масиві).

Рішення:

• Використовуйте streaming (IEnumerable + yield)
• Розбийте на chunks
• Memory-mapped files для величезних даних

Practice Tasks

Junior: LRU Cache

Реалізуйте LRU (Least Recently Used) cache використовуючи Dictionary<TKey, LinkedListNode<T>> та LinkedList<T>.

Вимоги:

• Get(key): повертає значення, переміщує елемент в кінець (most recent)
• Put(key, value): додає або оновлює, при переповненні видаляє найстаріший (перший у LinkedList)
• O(1) для обох операцій

Middle: Thread-Safe Producer-Consumer

Створіть систему обробки логів з System.Threading.Channels:

• 3 producer threads генерують лог-повідомлення
• 2 consumer threads записують у файл
• Channel capacity: 100
• Graceful shutdown

Senior: Custom Hash Table

Реалізуйте власну hash table з open addressing (linear probing):

• Dynamic resizing при load factor > 0.7
• Tombstones для видалення
• Generic CustomHashTable<TKey, TValue>
• Benchmark проти Dictionary<TKey, TValue>

Резюме

Наступна тема: High Performance Types (Span<T>, Memory<T>, stackalloc)