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

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

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

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

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

Історія

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

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

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

Властивості

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

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

Вектор

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

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

Примітки

1. (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