Колекція (програмування)

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

Колекція дозволяє записувати в себе значення і витягати їх. Призначення колекції - служити сховищем об'єктів і забезпечувати доступ до них. Зазвичай колекції використовуються для зберігання груп однотипних об'єктів, що підлягають стереотипної обробці. Для звернення до конкретного елементу колекції можуть використовуватися різні методи, в залежності від її логічної організації. Реалізація може допускати виконання окремих операцій над колекціями в цілому. Наявність операцій над колекціями у багатьох випадках може істотно спростити програмування.


1. Колекції та контейнери

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

2. Класифікація

2.1. За загальним характеристикам

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

2.2. За логікою організації

В залежності від того, як логічно організований доступ до даних колекції, виділяються наступні основні типи:

  • Вектор - елементи колекції впорядковані, кожен має власний номер, званий індексом, по якому до нього можна в будь-який момент звернутися. Як правило, в якості індексів виступають послідовні цілі числа або значення, що наводяться до них. Для звернення до елемента вектора використовується ім'я вектора і значення індексу. При додаванні нового елементу він додається або в кінець вектора, або в позицію із заданим індексом. Видалення елемента зі вектора приводить до утворення порожнього елемента.
  • Матриця - елементи мають два впорядкованих індексу, кожен з яких є цілим числом або значенням, що приводиться до цілого. Для доступу до елемента потрібно вказати ім'я матриці і обидва індекси. Новий елемент може бути доданий тільки в позицію із заданою парою індексів. Видалення призводить до залишення порожнього елемента.
  • Багатовимірний масив - логічний розвиток ідеї вектора і матриці до більшого (у загальному випадку - довільного) числа індексів.
  • Список - елементи колекції впорядковані, ідентифікаторів у елементів немає. Список - колекція з послідовним доступом. У будь-який момент доступний перший елемент колекції (зазвичай також доступний і останній). Від будь-якого елементу колекції можна отримати доступ до наступного по порядку, таким чином, можна послідовно дійти від першого елементу списку до будь-якого бажаного. Можлива реалізація, що допускає зворотний прохід (до попереднього елемента від відомого). Новий елемент може додаватися в початок або в кінець списку. При видаленні елемента з початку списку першим елементом стає наступний за ним, при видаленні з кінця - попередній, з середини - попередній і наступний елементи стають, відповідно, попереднім і подальшим один для іншого.
  • Стек - колекція, що реалізує принцип зберігання "LIFO" ("останнім прийшов - першим вийшов"). У стеці постійно доступний тільки один елемент - той, який був доданий останнім. Новий елемент може бути доданий в стек, він стане поточним. Поточний елемент завжди можна видалити ("взяти") з стека, після цього стає доступний елемент, який був доданий безпосередньо перед ним.
  • Черга - колекція, що реалізує принцип зберігання " FIFO "(" першим прийшов - першим вийшов "). У черзі постійно доступний тільки один елемент - той, який був доданий найпершим з наявних. При додаванні нового елементу він потрапляє в чергу. Поточний елемент можна видалити - тоді поточним стане елемент, доданий першим з залишилися.
  • Асоціативний масив (словник) - неупорядкована колекція, що зберігає пари "ключ - значення". Доступ до елементів проводиться по ключу. В якості ключа можуть використовуватися значення різних типів, єдине обмеження - тип ключа повинен допускати порівняння на рівність. Будь-яка пара може бути в будь-який момент видалена. Додаватися може тільки пара (з певним ключем). Може вводитися заборона на дублювання ключів в колекції. Якщо такого обмеження немає, то при зверненні за дублюючий ключу може видаватися або n-е знайдене значення (де n або постійно, або визначається формою запиту), або всі значення з даними ключем.
  • Безліч - неупорядкована колекція, що зберігає набір унікальних значень і підтримуюча для них операції додавання, видалення і визначення входження. Як правило, для множин підтримуються операції, аналогічним операціям з математичними множинами: об'єднання, перетин, симетрична різниця множин і несиметрична різниця множин.
  • Мультімножество - неупорядкована колекція, аналогічна безлічі, але допускає наявність в колекції одночасно двох і більше однакових значень.

2.3. З реалізації

На рівні реалізації колекція може являти собою одну з наступних структур даних:

3. Операції над колекціями

В залежності від логічного типу колекції і від реалізації можуть підтримуватися різні операції над колекціями в цілому. У всіх випадках операції можуть проводитися тільки над парами колекцій одного типу (і, якщо колекції не гетерогенні, з одним типом елементів). Можуть підтримуватися також наступні операції:

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

4. Відомі реалізації

  • Glib - бібліотека, що реалізує більшість колекцій під ліцензією GNU LGPL
  • STL - реалізація у вигляді бібліотеки шаблонів для C + +.

Примітки