Контейнер (абстрактний тип даних)

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Контейнер у комп'ютерній науці — клас, структура даних[1][2], або абстрактний тип даних, який дозволяє створювати колекції інших об'єктів. Іншими словами, контейнери застосовуються для зберігання об'єктів у вигляді організованої структури на основі конкретних правил збереження і доступу до елементів.

Застосування контейнерів

[ред. | ред. код]

Навіщо варто використовувати контейнери, а не звичайні масиви:

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

Стандартні проблеми і помилки, які часто трапляються при використанні масивів[3]:

  • При використанні індексованих масивів у мовах програмування системного рівня, такий як С чи C++, не існує перевірки, якщо індекс виходить за рамки масиву. Це зауваження не стосується багатьох мов, які вважаються простішими і більш захищеними від помилок програміста, таких як Pascal, Java тощо. Такі помилки важко відстежувати, адже в момент коли це трапляється ви можете отримати непередбачувану поведінку програми. Слід відмітити, що в деяких контейнерах, таких як std::vector, немає перевірки виходу за межі масиву, в методах доступу до елементів вектора.
  • У мовах, які не мають автоматичного прибирання сміття, використання масивів часто потребує виділення пам'яті з купи, і в таких випадках програмісту необхідно власноруч подбати про те, щоб пам'ять виділена під масив була в кінці звільнена (враховуючи наявність всіх виключних ситуацій). Коли ви використовуєте контейнери, управління пам'яттю для вас відбувається автоматично.
  • Ви не можете вставити елемент в середину масиву, або навіть додати один в кінець масиву, якщо ви не використовуєте динамічне виділення пам'яті для масиву, і навіть тоді вам доведеться виділяти пам'ять під новий масив і копіювати його елементи.
  • Контейнери дозволяють вам звертатися до них за допомогою посилання чи за значенням, але масиви не дають вам такої можливості: до них завжди слід звертатися за посиланням. Якщо ви хочете зімітувати звернення до масиву за значенням, вам необхідно власноруч написати код, який явно копіює елементи масиву у коді, в тому числі знищувати ці копії, коли вони вже не потрібні. Все це відбувається автоматично, якщо ви використовуєте класи контейнерів.
  • Якщо ваша функція має не статичний локальний масив, ви не можете повертати його за допомогою ключового слова return, але таке можливо при використанні об'єктів контейнерів.

Різні контейнери С++ мають різні переваги і недоліки, але для кожної конкретної задачі зазвичай один із них підходить краще — зрозуміліше, безпечніше, простіше в підтримці і часто навіть більш ефективний — ніж простий масив. Наприклад:

  • краще використати std::map ніж писати власний код для таблиці пошуку.
  • std::map також можна використати для розріджених масивів чи розріджених матриць.
  • std::vector стандартний клас контейнеру, який дуже схожий на масив, але пропонує декілька додаткових можливостей, дозволяючи перевіряти межі масиву використовуючи метод at(), додавання і видалення елементів, автоматичне управління пам'яттю навіть у разі виникнення виключних ситуацій, можливість звертатися за значенням і за допомогою посилання.
  • std::string також можна розглядати як клас контейнер, і він майже завжди набагато краще ніж масив символів.

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

Типи контейнерів

[ред. | ред. код]

Контейнери, що містять значення

[ред. | ред. код]

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

Контейнери, що містять посилання

[ред. | ред. код]

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

Примітки

[ред. | ред. код]
  1. Paul E. Black (ed.), entry for data structure in Dictionary of Algorithms and Data Structures. US National Institute of Standards and Technology.15 December 2004. Accessed on Oct 04, 2011.
  2. Entry data structure in the Encyclopædia Britannica (2009) Online entry [Архівовано 2 травня 2015 у Wayback Machine.] Accessed on Oct 04, 2011.
  3. C++ FAQ [Архівовано 7 липня 2014 у Wayback Machine.] [34.1] Why should I use container classes rather than simple arrays?