Чем отличается std::vector от std::list?

# std::vector vs std::list

Этт два фундаментальных контейнера с противоположными характеристиками. Вот детальное сравнение.

Структура данных

std::vector

Динамический массив с автоматическим расширением (dynamic array).

vector: [elem0 | elem1 | elem2 | ... | elemN | (capacity-size) free slots]
         └────────────────────────────────────────────────────────────┘
         Непрерывная в памяти область

Преимущества:

• Все элементы рядом в памяти → отличная кэш-локальность
• Один блок памяти → меньше фрагментации
• Быстро выделить/переделить

std::list

Двусвязный список (doubly-linked list).

list: [node0] <-> [node1] <-> [node2] <-> ... <-> [nodeN]
      ↑addr1    ↑addr2    ↑addr3              ↑addrM
      Разные адреса в памяти!

Каждый узел содержит:

• Данные элемента
• Указатель на предыдущий узел
• Указатель на следующий узел

Характеристики операций

Случайный доступ

// vector: O(1)
vector<int> v = {1, 2, 3, 4, 5};
int x = v[2];      // ✅ O(1) — просто расчёт адреса
int y = v.at(1);   // ✅ O(1)

// list: O(n)
list<int> l = {1, 2, 3, 4, 5};
int x = l[2];      // ❌ COMPILATION ERROR — нет operator[]
auto it = l.begin();
std::advance(it, 2);  // O(n) — проходим по всем узлам
int y = *it;       // ✅ Но это O(n) всего!

Итерирование

// vector: O(n) итерирование, но FAST
vector<int> v(1000000);
for (int x : v) {}  // ✅ Очень быстро из-за кэша

// list: O(n) итерирование, но МЕДЛЕННО
list<int> l(1000000);
for (int x : l) {}  // ⚠️ Медленно — много кэш-миссов
// Каждый узел в разных местах памяти → CPU cache не помогает

Вставка/Удаление в конце

// vector: O(1) амортизированная
vector<int> v;
for (int i = 0; i < 1000000; ++i) {
    v.push_back(i);  // ✅ O(1) в среднем (sometimes O(n) при resize)
}

// list: O(1)
list<int> l;
for (int i = 0; i < 1000000; ++i) {
    l.push_back(i);  // ✅ O(1) гарантированно
}

Вставка/Удаление в начале

// vector: O(n) — нужно сдвинуть все элементы
vector<int> v = {2, 3, 4};
v.insert(v.begin(), 1);  // ❌ O(n) — сдвигаем все

// list: O(1)
list<int> l = {2, 3, 4};
l.insert(l.begin(), 1);  // ✅ O(1) — просто создаём новый узел

Вставка/Удаление в середине (с известным iterator)

// vector: O(n) — нужно сдвинуть элементы после позиции
vector<int> v = {1, 2, 4, 5};
auto it = v.begin() + 2;        // нашли позицию
v.insert(it, 3);               // ❌ O(n) — сдвигаем 4, 5

// list: O(1) — если есть iterator!
list<int> l = {1, 2, 4, 5};
auto it = std::next(l.begin(), 2);  // O(n) найти позицию
l.insert(it, 3);               // ✅ O(1) — если iterator известен

Память

Использование памяти

vector<int> v(1000);
// Память: 1000 * sizeof(int) = 4000 байт
// Никакого оверхеда на элемент

list<int> l(1000);
// Память: 1000 * (sizeof(int) + 2*sizeof(void*)) 
//       = 1000 * (4 + 16) = 20000 байт (на 64-bit)
// На каждый int тратим 16 байт дополнительно!

Фрагментация

// vector: Монолитный блок, без фрагментации
vector<int> v;
v.reserve(1000000);  // один big allocation
for (int i = 0; i < 1000000; ++i) v.push_back(i);
// Всё в одном куске памяти

// list: Каждый узел может быть в разном месте
list<int> l;
for (int i = 0; i < 1000000; ++i) {
    l.push_back(i);  // каждый раз new для узла
}
// После удаления элементов — фрагментация памяти

Инвалидация итераторов

vector: опасна!

vector<int> v = {1, 2, 3};
auto it = v.begin() + 1;  // указатель на 2

v.push_back(4);           // может произойти reallocation!
// it теперь INVALID (undefined behavior)
std::cout << *it;         // ❌ CRASH или garbage

v.erase(v.begin());       // удаляем первый элемент
// it всё ещё указывает на 2? Нет! Сдвинулся на 1
std::cout << *it;         // ❌ теперь это 3!

list: стабильна

list<int> l = {1, 2, 3};
auto it = std::next(l.begin());  // указатель на узел со значением 2

l.push_back(4);           // ✅ it остаётся валидным
std::cout << *it;         // 2 — всё OK

l.erase(l.begin());       // удаляем 1
std::cout << *it;         // 2 — всё ещё OK

// Единственное: нельзя удалять сам элемент
l.erase(it);              // удалили элемент
// it теперь INVALID

Кэш-производительность

vector: Cache-friendly

vector<int> v(1000000);
for (int x : v) sum += x;  // Sequential memory access

CPU cache hits: 99%+ (один промах за кэш-линию = ~64 байта)

list: Cache-unfriendly

list<int> l(1000000);
for (int x : l) sum += x;  // Random memory access

CPU cache hits: ~5-10% (каждый узел в новой памяти)

Результат: vector итерирует в 10-100x раз быстрее!

Практические примеры

Используй vector

// ✅ Большой массив, нужен случайный доступ
std::vector<int> pixels(1920 * 1080);
for (int y = 0; y < 1080; ++y) {
    for (int x = 0; x < 1920; ++x) {
        process(pixels[y * 1920 + x]);
    }
}

// ✅ Растущий массив, добавляем в конец
std::vector<Record> records;
for (auto& line : file_lines) {
    records.push_back(parse(line));
}

// ✅ Нужна сортировка
std::vector<int> data = read_data();
std::sort(data.begin(), data.end());

Используй list

// ✅ Часто удаляем элементы из середины
std::list<Task> queue;
// ...
for (auto it = queue.begin(); it != queue.end(); ) {
    if (it->is_completed()) {
        it = queue.erase(it);  // O(1)
    } else {
        ++it;
    }
}

// ✅ Нужны стабильные итераторы при модификации
std::list<Observer> observers;
for (auto& obs : observers) {
    obs.notify();  // Безопасно добавлять/удалять других observer'ов
}

// ✅ Реализация LRU cache
std::list<Page> lru_list;
std::unordered_map<int, std::list<Page>::iterator> page_map;
// O(1) удаление из начала/конца, O(1) перемещение в конец

Правило выбора

*амортизированная †требует iterator на позицию

Резюме

vector: «Используй меня по умолчанию» — быстрый, компактный, ленивый.

list: «Используй когда нужны частые вставки/удаления в середине» — специальный инструмент.

Золотое правило:

• 90% программ → vector
• Специальные случаи (очереди, LRU, графы) → list
• Сомневаешься → vector

Эйч Бьёрн Страуструп (создатель C++) говорит: "Я не видел программы, где list был бы выбором номер 1 по производительности."