Огляд основних типів колекцій

1. Вступ

Відверто кажучи, масиви — чудова річ, але вони мають обмеження. Потрібно змінити розмір? Доведеться створювати новий масив і вручну копіювати елементи. Треба швидко знайти елемент за ключем? Масив скаже: «Ну, спробуйте зробити це самі».

Реальне життя повне ситуацій, де масиви незручні. Уявіть, що ви створюєте застосунок для обліку книжок у бібліотеці (як у нашій навчальній мінісистемі). Спочатку у вас 5 книжок — масиву начебто досить. За тиждень їх уже 500, а за місяць хтось повернув книжку, а хтось загубив… Тут на допомогу приходять колекції!

Колекції — це контейнери, які вміють:

• Автоматично змінювати свій розмір.
• Забезпечувати швидкий пошук, додавання, видалення.
• Пропонувати зручні способи обробки даних: сортування, фільтрування, групову обробку.

У .NET є кілька ключових «родин» колекцій. Сьогодні ми познайомимося з основними: списки (List<T>), словники (Dictionary<TKey, TValue>), множини (HashSet<T>), черги, стеки, а також з інтерфейсами, що лежать в їхній основі.

2. Основні види колекцій

Хоч ми ще не занурювалися у конкретні типи узагальнених колекцій, важливо розуміти, які існують основні категорії колекцій і для яких завдань вони підходять. Уявляйте їх як різні типи «контейнерів», кожен із власними перевагами:

Списки (Lists)

Що це? Впорядкована послідовність елементів. Як звичайний список покупок або список студентів у журналі.

Ключові особливості: Елементи мають порядок (можна отримати за індексом, як у масиві). Можуть містити повторювані елементи. Розмір динамічний.

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

Приклад з життя: Черга на касі, список учасників вебінару, послідовність кадрів в анімації.

Словники/Відображення (Dictionaries/Maps)

Що це? Набір пар «ключ–значення». Схоже на справжній словник, де у кожного слова (ключа) є своє значення (визначення).

Ключові особливості: Кожен ключ унікальний. Ключ використовується для швидкого пошуку відповідного значення. Порядок елементів зазвичай не гарантується.

Коли використовувати? Коли треба швидко знайти значення за якимось унікальним ідентифікатором (ключем).

Приклад з життя: Записник (імʼя — телефон), база даних товарів (ID товару — опис), налаштування застосунку (імʼя налаштування — значення).

Множини (Sets)

Що це? Неупорядкований набір унікальних елементів. Як математична множина.

Ключові особливості: Не можуть містити повторювані елементи. Порядок елементів не гарантується. Оптимізовані для перевірки наявності елемента і виконання операцій над множинами (об’єднання, перетин).

Коли використовувати? Коли треба зберігати унікальні значення і швидко перевіряти, чи є елемент у наборі.

Приклад з життя: Список унікальних відвідувачів сайту, набір тегів для статті, список слів для автодоповнення (без повторів).

Черги (Queues)

Що це? Колекція, що працює за принципом «перший прийшов — перший пішов» (FIFO — First-In, First-Out).

Ключові особливості: Елементи додаються в кінець черги і видаляються з початку.

Коли використовувати? Для моделювання процесів, де важливий порядок обробки, наприклад система тікетів підтримки, черга на друк.

Стеки (Stacks)

Що це? Колекція, що працює за принципом «останній прийшов — перший пішов» (LIFO — Last-In, First-Out).

Ключові особливості: Елементи додаються і видаляються з одного кінця (вершини стеку).

Коли використовувати? Відстеження історії дій (скасування дії в редакторі), обробка вкладених структур, рекурсія.

Відмінності між типами колекцій

3. Список: List<T>

Список — це найчастіше використовувана колекція в C#. Навіть частіше за масив. Список — колекція, схожа на масив, але вміє розширюватися сам. Можна додавати й видаляти елементи без зайвих клопотів.

using System;
using System.Collections.Generic;

var numbers = new List<int>();         // Створюємо порожній список цілих чисел
numbers.Add(10);                      // Додаємо елемент
numbers.Add(15);
numbers.Add(42);

Console.WriteLine(numbers[0]);        // 10

numbers.Remove(15);                   // Видаляємо елемент за значенням

foreach (var number in numbers)
{
    Console.WriteLine(number);
}
// Виведе: 10 і 42

Чому List<T> кращий за масив для колекції даних, розмір якої наперед невідомий?
— Бо не потрібно вручну виділяти більше пам’яті й копіювати масив під час додавання елементів — усе робить колекція!

Коли використовувати List<T>?

• Динамічний список, коли елементи можна додавати, видаляти, змінювати.
• Не потрібен швидкий пошук за ключем (це вже про словники).
• Часто використовують для роботи з упорядкованими наборами.

4. Словник Dictionary<TKey, TValue>

Масив (і список) дає змогу зберігати список значень у комірках масиву, і в кожної комірки є індекс. А от словник — це колекція, яка дозволяє замість числа (індексу) використовувати рядок (імʼя). Таке імʼя комірки називається ключем.

Якщо треба за якимось ключем швидко отримати значення (наприклад, за номером читацького квитка — імʼя читача), то потрібен словник.

using System.Collections.Generic;

var phoneBook = new Dictionary<string, string>();
phoneBook["Аня"] = "+79992221133";
phoneBook["Максим"] = "+79998887766";

Console.WriteLine(phoneBook["Аня"]);      // +79992221133

// Можна перевірити, чи є ключ:
if (phoneBook.ContainsKey("Вася"))
{
    Console.WriteLine(phoneBook["Вася"]);
}
else
{
    Console.WriteLine("Немає такого номера!");
}

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

Ключові особливості

• Ключ унікальний: у словнику не може бути двох однакових ключів.
• Значення можуть повторюватися.
• Дуже швидко шукає, додає, видаляє елементи за ключем.

5. Множина: HashSet<T>

Окрім списків і словників, також дуже популярні множини. Це майже як список, але простіше: без фіксованого порядку елементів. Множина зберігає набір значень для ситуацій, коли порядок не має значення.

Наприклад, потрібно просто знати, чи є щось у наборі, без дублікатів і без важливості порядку — тоді використовуємо множину.

using System.Collections.Generic;

var knownUsers = new HashSet<string>();
knownUsers.Add("admin");
knownUsers.Add("guest");
knownUsers.Add("admin");    // Повторне додавання — ігнорується

Console.WriteLine(knownUsers.Contains("admin"));  // True
Console.WriteLine(knownUsers.Count);              // 2

Множина дуже швидко перевіряє наявність елемента.

Навіщо потрібні множини?
— Якщо, наприклад, хочете зберігати всіх унікальних користувачів, які відкрили застосунок за місяць, або, скажімо, список унікальних авторів книжок.

Особливості

• Зберігає тільки унікальні елементи (вставлення дубліката ігнорується).
• Немає індексів, як у списку.
• Швидка перевірка наявності.

6. Черги і стеки

Є ще структури для спеціальних випадків: черга і стек. Це спеціалізовані структури з контрольованим додаванням і вилученням елементів.

Queue<T>: черга (first in — first out)

Іноді треба тримати «чергу»: новий елемент стає в кінець, а забирати їх потрібно з початку.

using System.Collections.Generic;

var queue = new Queue<string>();
queue.Enqueue("Перший");
queue.Enqueue("Другий");
queue.Enqueue("Третій");

Console.WriteLine(queue.Dequeue()); // "Перший"
Console.WriteLine(queue.Peek());    // "Другий", але не видаляє

Stack<T>: стек (first in — last out)

Стек працює навпаки: останній зайшов — перший вийшов. Використовується у парсерах, обробці викликів функцій і навіть під час скасування дій у редакторах.

using System.Collections.Generic;

var stack = new Stack<string>();
stack.Push("Один");
stack.Push("Два");
stack.Push("Три");

Console.WriteLine(stack.Pop());  // "Три"
Console.WriteLine(stack.Peek()); // "Два"

7. Таблиця: порівняння основних колекцій

List<T>

Dictionary<K,V>

HashSet<T>

Queue<T>

Stack<T>

У наступних лекціях ми детально розглянемо кожну колекцію. А почнемо — із загадкової букви <T>…