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

Вектори (vector), двосторонні черги (deque) і списки (list) підтримують різні набори операцій, серед яких є співпадаючі операції. Вони можуть бути реалізовані з різною ефективністю:

Операція	Метод	vector	deque	list
Вставка в початок	push_front	-	+	+
Видалення з початку	pop_front	-	+	+
Вставка в конец	push_back	+	+	+
Видалення з кінця	рор_bаск	+	+	+
Вставка в довільне місце	Insert	(+)	(+)	+
Видалення з довільного місця	Erase	(+)	(+)	+
Довільний доступ до елементу	[ ], at	+	+	-

Знак (+) означає, що відповідна операція реалізується за постійний час, не залежний від кількості елементів n в контейнері. Знак (+) означає, що відповідна операція реалізується за час, пропорційний n. Для малих n час операцій, позначених (+), може перевищувати час операцій, позначених (+), але для великої кількості елементів останні можуть виявитися дуже дорогими. Як видно з таблиці, такими операціями є вставка і видалення довільних елементів черги і вектора, оскільки при цьому всі наступні елементи потрібно переписувати на нові місця.

Отже, вектор – це структура, що ефективно реалізовує довільний доступ до елементів, додавання в кінець та видалення з кінця. Двостороння черга ефективно реалізує довільний доступ до елементів, додавання в обидва кінці і видалення з обох кінців. Список ефективно реалізує вставку та видалення елементів в довільне місце, але не має довільного доступу до своїх елементів.

Приклад роботи з вектором. У файлі знаходиться довільна кількість цілих чисел. Програма зчитує їх у вектор і виводить на екран в тому ж порядку.

#include <iostream>

#include <fstream>

#include <vector>

using namespace std;

Void main()

{

ifstream in ("text.txt");

vector<int> v;

int x;

while (!in.eof(), in >> x)

v.push_back(x);

for (vector<int>::iterator i=v.begin(); i!=v.end(); ++i)

cout << *i << " ";

}

Оскільки файл містить цілі числа, використовується відповідна спеціалізація шаблону vector – vector<int>. Для створення вектора v використовується конструктор за умовчанням. Організовується цикл до кінця файлу, в якому з нього зчитується чергове ціле число. За допомогою методу push_back воно заноситься у вектор, розмір якого збільшується автоматично. Для проходу по всьому вектору вводиться змінна i як ітератор відповідного типу тобто тут оголошується змінна i типу "ітератор". За допомогою цього ітератора здійснюється доступ до всіх по порядку елементам контейнера, починаючи з першого. Метод begin() повертає вказівку на перший елемент, метод end() – на елемент, наступний за останнім. Порівнювати поточне значення з граничним слід саме за допомогою операції "!=", оскільки операції "<" або "<=" можуть бути для даного типу не визначені. Операція інкременту (++i) реалізована так, щоб після неї ітератор вказує на наступний елемент контейнера в порядку обходу. Доступ до елементу вектора виконується за допомогою операції розадресації, як для звичайних вказівок. У даному прикладі замість вектора можна було використовувати будь-який послідовний контейнер шляхом простої заміни слова vector на deque або list. При цьому змінилося б внутрішнє представлення даних і набір доступних операцій. Приведені операції в прикладі використовуються для будь-якого послідовного контейнера. Проте якщо замість циклу for вставити фрагмент

for (int i = 0; i<v.size(); i++) cout << v[i] << " ";

у якому використана операція доступу по індексу [ ], програма не працюватиме для контейнера типу list, оскільки в ньому ця операція не визначена.