Послідовний контейнер

В програмуванні, послідовний контейнер це ціла група шаблонів класів стандартної бібліотеки мови C++, які реалізують логіку контейнера, що виконує функцію зберігання елементів даних. Будучи шаблонами, вони можуть використовуватися для зберігання довільних елементів, як для цілих чисел так і для користувацьких класів. Спільною властивістю всіх послідовних контейнерів в тому, що доступ до елементів відбувається послідовно. Як і всі інші стандартні компоненти бібліотеки, вони знаходяться в просторі імен std.

Стандартна бібліотека C++
Стандартна бібліотека шаблонів
Стандартна бібліотека С
Інші заголовки:

В останньому стандарті С++ визначені наступні контейнери: array, vector, list, forward_list, deque. Кожен з цих контейнерів реалізує різні алгоритми зберігання даних, це означає, що вони мають різну швидкодію при виконанні різних операцій:[1]

  • array реалізує масив незмінного розміру, що створюється під час компіляції.
  • vector реалізує масив із швидким довільним доступом і можливістю автоматичної зміни розміру при додаванні елементів.
  • deque реалізує двобічну чергу з порівняно швидким довільним доступом до елементів.
  • list реалізує двобічно зв'язаний список.
  • forward_list реалізує однобічно зв'язаний список.

Оскільки кожен з контейнерів потребує можливості копіювати свої елементи для правильного функціонування, тип даних елементу має виконувати вимоги CopyConstructible і Assignable (мати конструктор копій і оператор присвоювання).[2] У даного контейнера, всі елементи мають бути одного типу. Наприклад, не можливо одночасно зберігати дані типу char і int в одному контейнері.

Історія

Спочатку, тільки були визначені лише класи vector, list, deque. До стандартизації мови C++ в 1998, вони були частиною Стандартної бібліотеки шаблонів, що була опублікована компанією SGI.

Контейнер array вперше з’явився у декількох книжках під різними назвами. Згодом він був вбудований в в набір бібліотек Boost C++ і був запропонований в стандартну бібліотеку C++. Мотивацією додавання контейнера array було те, що він вирішував дві проблеми масивів Cі-стилю: нестачу STL-подібного інтерфейсу і неможливість копіювати його як будь-який інший об'єкт. Він вперше з’явився в C++ TR1 і згодом став частиною стандарту C++11.

Контейнер forward_list було додано до C++11 як більш просторово-ефективна альтернатива стандартному контейнеру list для випадків, коли зворотній прохід ітератора не потрібний.

Властивості

array, vector і deque - всі ці контейнери підтримують довільний доступ до елементів. list підтримує двонаправлену ітерацію, тоді як forward_list підтримує ітерування лише в одному напрямку.

array не має функції додавання чи видалення елементів. vector дозволяє швидко додавати чи видаляти елементи в кінці вектора. Будь-яке додавання чи видалення елементів не в кінці вектора потребує виконувати операцію копіювання елементів від позиції додавання елементів до кінця вектору. Ітератори над елементами, з якими відбулися такі дії стають недійсними. Насправді, будь-яке додавання має шанс порушити і зробити недійсними всі ітератори. Крім того, якщо виділене сховище пам'яті у vector замале, для додавання нових елементів, буде виділено новий масив в пам'яті, всі елементи будуть скопійовані і перенесені у новий масив, а старий масив буде вивільнено. Контейнери deque, list і forward_list підтримують операції швидкого додавання або видалення елементів, в будь-яке місце контейнеру. list і forward_list зберігають валідність ітераторів при таких операціях, а deque робить їх всі недійсними.

Вектор

Елементи контейнера vector зберігаються послідовно.[3] Як і всі реалізації динамічних масивів, вектори дозволяють ефективно використовувати пам'ять і мають добру локалізацію посилань і оптимальне використання кешу. На відміну від інших STL контейнерів, таких як двобічні черги (deque) і списки (list), вектори дозволяють вказувати початковий розмір контейнера.

Вектори дозволяють здійснювати довільний доступ; таким чином, що до елементів вектору можна доступатися таким самим чином як і до елементів масивів (по індексу в масиві).

Примітки
  1. Josuttis, Nicolai (1999). C++ Standard Library - A Tutorial and Reference. Addison-Wesley.
  2. ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages - C++ §23.1 Container requirements [lib.container.requirements] para. 4
  3. ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages - C++ §23.2.4 Class template vector [lib.vector] para. 1
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.