std::vector, std::deque, std::list

1. Вступ

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

Ми говоритимемо про послідовні контейнери — контейнери, у яких елементи йдуть у певному порядку: перший, другий, третій… Але в памʼяті вони влаштовані по‑різному. У C++ до них належать, наприклад, std::vector, std::deque, std::list і ще кілька інших, але сьогодні нас цікавлять саме ці три. У стандарті їх виділено в окремі «сімейства» з власною специфікацією.

Щоб не загубитися, зафіксуймо головну ідею дня: вибір контейнера — це вибір компромісу. Десь ви виграєте на вставках, десь — на обході, десь — на доступі за індексом. А безплатним буває лише сир у мишоловці, та й то не для миші.

2. std::vector: швидкий, доки не вставляєш на початок

std::vector зазвичай стає «контейнером за замовчуванням», і це нормально. Він добре «дружить» із процесором: елементи лежать підряд у памʼяті, тож обхід усіх елементів на практиці часто виходить швидким. Але у vector є й характерна слабкість: коли ви вставляєте або видаляєте елементи на початку чи всередині, йому доводиться «зсувати хвіст». Це схоже на ситуацію, коли ви вставляєте рядок в Excel, і вся таблиця зʼїжджає вниз.

Інтуїція про vector

У std::vector<T> усередині є один великий «шматок памʼяті» для елементів T. Звідси випливають дві ключові властивості.

Перша — швидкий доступ за індексом: v[i] зазвичай працює дуже швидко, бо i‑й елемент можна знайти, знаючи «початкову адресу + i * sizeof(T)».

Друга — зростання. Коли vector переповнюється, йому іноді доводиться виділити новий, зазвичай більший, шматок памʼяті й перенести туди всі елементи. У попередніх темах ви вже бачили reserve() як спосіб зменшити кількість таких дорогих кроків.

Дуже спрощена візуалізація:

flowchart LR
  A["vector: суцільний блок памʼяті"] --> B["[0][1][2][3][4]..."]

Міні‑приклад: індекс і швидкий обхід

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{10, 20, 30};

    std::cout << v[1] << '\n'; // 20
}

Цей приклад здається надто простим, але тут важливе головне: vector справді задуманий як «динамічний масив». Індексування тут природне й зручне.

Міні‑приклад: вставка на початок

#include <vector>

int main() {
    std::vector<int> v{2, 3, 4};
    v.insert(v.begin(), 1); // елементи зсуваються праворуч
}

Ми поки не заглиблюємося в деталі вартості й у те, «що буде з ітераторами та посиланнями», — це тема наступної лекції дня. Зараз достатньо запамʼятати головну інтуїцію: insert ближче до початку у vector — потенційно дорога операція, бо потрібно «посунути» елементи.

3. std::deque: операції на двох кінцях

Якщо vector — це коридор з одними дверима, де зручно додавати в кінець, то deque — це коридор із дверима і спереду, і ззаду. Назва буквально так і розшифровується: double‑ended queue. Він чудово підходить, коли ви хочете часто додавати й видаляти елементи на обох кінцях: push_front, push_back, pop_front, pop_back.

Водночас deque, на відміну від list, усе ще підтримує доступ за індексом d[i]. Але всередині він зазвичай влаштований не як один суцільний блок, а як набір блоків. Ми спрощуємо, але саме цю картинку й варто запамʼятати.

Спрощена схема:

flowchart LR
  A["deque: набір блоків"] --> B["[ ][ ][ ]"]
  A --> C["[ ][ ][ ]"]
  A --> D["[ ][ ][ ]"]

Навіщо deque, якщо є vector

Тому що для vector «швидко додавати на початок» — це біль, а deque саме для цього й створений. У реальних задачах часто трапляються сценарії на кшталт «черга задач», «буфер повідомлень», «історія останніх подій», де природно працювати з двома кінцями.

Міні‑приклад: операції на обох кінцях

#include <deque>
#include <iostream>

int main() {
    std::deque<int> d{2, 3};
    d.push_front(1);
    d.push_back(4);

    std::cout << d.front() << ' ' << d.back() << '\n'; // 1 4
}

Тут немає жодної магії — просто видно ключову роль deque: обидва кінці для нього «рідні».

Важливе уточнення

deque не зобовʼязаний бути «поліпшеним vector». Це окремий компроміс. Як правило, він жертвує частиною «ідеальної суцільності розміщення в памʼяті» заради зручності операцій на обох кінцях. Детально вплив памʼяті на швидкість ми обговоримо у фінальній лекції дня, але вже зараз можна запамʼятати просту фразу: deque часто «про зручність на обох кінцях», а vector — «про щільність даних».

4. std::list: вузли й робота за позиціями

std::list — це двозвʼязний список. Уявіть намисто: кожен елемент — окрема намистина, тобто вузол, і кожна така намистина має посилання на попередню та наступну. На відміну від vector і deque, елементи списку не зобовʼязані лежати підряд у памʼяті. Це називається вузловий контейнер (node‑based): кожен вузол зазвичай виділяється окремо.

Схема на пальцях:

flowchart LR
  A["[10]"] <--> B["[20]"] <--> C["[30]"]

Чим list відрізняється від vector і deque

Головна «психологічна» різниця така: list — це не про індекси, а про позиції.

У std::list немає operator[]. І це не тому, що автори STL «забули додати», а тому, що сама ідея «швидко дістати i‑й елемент» погано поєднується зі списком: щоб дістатися до i‑го, потрібно пройти за посиланнями i кроків.

Зате у list є сильна сторона: вставка й видалення у відомій позиції — тобто коли у вас уже є ітератор — зазвичай не потребують зсуву всіх інших елементів. Знову ж таки, сьогодні ми тримаємо це на рівні інтуїції: «не рухаємо хвіст» — у цьому й сенс.

Міні‑приклад: вставка за ітератором

#include <list>
#include <iostream>

int main() {
    std::list<int> lst{10, 30};

    auto it = lst.begin();
    ++it;                 // позиція на 30
    lst.insert(it, 20);   // вставили 20 перед 30

    for (int x : lst) {
        std::cout << x << ' ';
    }
    std::cout << '\n';    // 10 20 30
}

Ітератор тут — це «маркер позиції». Список особливо зручний, коли ви часто працюєте «всередині» послідовності й для вас важливіше швидко вставляти або видаляти на місці, ніж швидко індексувати.

Пастка мислення про O(1) вставку

Новачок часто чує: «у list вставка O(1)» — і робить висновок: «значить, list завжди кращий для вставок». Але це лише половина правди. Вставка може бути швидкою, якщо ви вже знаєте місце, тобто маєте ітератор. А от «знайти місце» — це окрема частина вартості, яка часто потребує лінійного проходу.

Сьогодні ми просто запамʼятаємо формулу:

«знайти позицію» + «вставити в позицію» = дві різні задачі.

list прискорює другу частину, але не зобовʼязаний прискорювати першу.

5. Як вибирати контейнер: порівняння й міні‑сценарії

Порівняльна таблиця

Коли ви наступного разу вибиратимете контейнер, корисно мати перед очима невелику «мапу місцевості». Зараз ми зробимо її максимально практичною: не як табличку зі стандарту, а як шпаргалку для розробника, який уже одного разу намагався зробити чергу на vector, а потім довго дивився в стелю.

std::vector

std::deque

std::list

push_back / pop_back

push_front / pop_front

Ця таблиця — не «математика на всі часи», а робоче наближення. Але воно дуже допомагає не вибирати контейнер «за настроєм». І так, стандартна бібліотека справді виділяє deque, list і vector як окремі контейнери зі своєю специфікацією та власними «сімействами» операцій.

Міні‑сценарії з TaskKeeper

До цього моменту курсу ми умовно розвивали консольний застосунок TaskKeeper: зберігали задачі, виводили список, фільтрували, сортували, шукали за умовами. Насправді для більшості таких задач std::vector<Task> — чудовий вибір, і ви не зобовʼязані ускладнювати собі життя лише тому, що «у C++ є ще контейнери».

Але бувають ситуації, коли інший контейнер пасує природніше. Давайте подивимося на три міні‑сценарії. Тут наша мета — не переписати застосунок, а навчитися розпізнавати такі ситуації.

Для прикладів введемо найпростішу модель задачі:

#include <string>

struct Task {
    int id{};
    std::string title;
};

Сценарій A: «список задач» — найчастіше vector

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

#include <iostream>
#include <vector>

int main() {
    std::vector<int> ids{101, 102, 103};
    for (int id : ids) {
        std::cout << id << ' ';
    }
    std::cout << '\n'; // 101 102 103
}

Ключовий момент: лінійний обхід у vector — це «рідний сценарій». Саме його ви найчастіше й виконуватимете.

Сценарій B: «черга подій» — проситься deque

Уявіть, що ми додали в TaskKeeper обробку подій інтерфейсу: користувач вводить команди, а ми хочемо зберігати «чергу команд на виконання» так, щоб інколи додавати термінову команду на початок черги. Це вже дуже схоже на роботу з двома кінцями.

#include <deque>
#include <iostream>
#include <string>

int main() {
    std::deque<std::string> q;
    q.push_back("load");
    q.push_front("help"); // терміново показати help

    std::cout << q.front() << '\n'; // help
}

Ідея проста: deque зручний, коли «спереду теж є життя», а не лише хвіст.

Сценарій C: «активні задачі й перестановки» — можливий list

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

#include <list>
#include <iostream>

int main() {
    std::list<int> active{1, 2, 3};

    auto it = active.begin();
    ++it;                 // вказує на 2
    active.erase(it);     // прибрали 2

    std::cout << active.front() << '\n'; // 1
}

Зверніть увагу: ми поки не обговорюємо, «що буде з ітераторами» і «які гарантії в кого». Це тема наступної лекції дня. Тут важлива сама модель: список — це контейнер, де природно мислити ітераторами‑позиціями, а не індексами.

6. Типові помилки

Помилка № 1: вибирати std::list, бо «там вставка O(1)», і очікувати пришвидшення всього застосунку.
Це поширена пастка: звучить науково, виглядає переконливо, а потім зʼясовується, що ви все одно виконуєте лінійний пошук потрібного місця, просто тепер ще й обхід став менш дружнім до памʼяті. Правильніше розділяти задачу на дві частини: спочатку зрозуміти, як ви знаходите позицію, і лише потім думати, як саме вставляєте.

Помилка № 2: намагатися звертатися до std::list за індексом, як до масиву.
Іноді рука сама тягнеться написати lst[i], бо «ну я ж хочу третій елемент». У list немає operator[], і це чесне попередження від STL: контейнер не створено для сценарію «третій елемент за O(1)». Якщо вам потрібен індекс, то майже напевно vector або deque буде ближчим за змістом.

Помилка № 3: вважати std::deque «тим самим vector, тільки крутішим».
deque справді підтримує індексацію й додавання в кінець, але його ключова роль — ефективні операції на обох кінцях. Якщо ваш сценарій — «багато читаємо підряд, рідко змінюємо», то vector часто простіший і передбачуваніший. deque варто діставати тоді, коли вам справді потрібні push_front/pop_front.

Помилка № 4: намагатися оптимізувати контейнер «про всяк випадок», не маючи профілю операцій.
Дуже хочеться вибрати «найправильніший» контейнер наперед, але правильний вибір залежить від того, що ви робите найчастіше: обхід, вставки, доступ за індексом чи робота з кінцями. Тому здоровий порядок міркувань такий: спочатку виписуємо типові операції, потім добираємо контейнер під них, і лише після цього думаємо про тонкощі.

Помилка № 5: змішувати моделі мислення: зберігати дані як у vector, а працювати як зі списком.
Наприклад, робити багато вставок на початок vector у циклі й дивуватися, чому все стало повільно. Контейнери дуже «виховують»: якщо працювати всупереч їхній природі, вони починають мститися. Тихо, без попереджень, — просто все стає повільнішим.