В чём разница между vector и deque? Какова сложность операций?

В чём разница между vector и deque? Какова сложность операций?

std::vector и std::deque — это оба динамические контейнеры в C++ STL, но они отличаются структурой памяти и производительностью операций. Vector использует один линейный буфер, а deque использует структуру из нескольких блоков памяти.

Структура памяти

std::vector

Линейный непрерывный буфер в памяти:

Внутреннее представление:
[ptr] -> |1|2|3|4|5|_|_|_| (capacity = 8, size = 5)
         ↑ начало буфера

При удалении старого буфера и создании нового вся память перераспределяется.

std::deque (Double-Ended Queue)

Структура из нескольких массивов (блоков):

Внутреннее представление:
Control Map:
[block0] [block1] [block2] [block3]
  |        |         |        |
  v        v         v        v
 |1|2|3| |4|5|6| |7|8|_| |_|_|_|

Каждый блок имеет фиксированный размер (обычно 512 байт). Добавление элементов может не требовать реаллокации старых блоков.

Сложность операций (Big O)

Операция        vector      deque
─────────────────────────────────
push_back       O(1)*       O(1)*
pop_back        O(1)        O(1)
push_front      O(n)        O(1)*
pop_front       O(n)        O(1)
access[i]       O(1)        O(1)
insert(iter)    O(n)        O(n)**
erase(iter)     O(n)        O(n)**
iterator        Random      Random
RAAII           Good        Good

• = амортизированная сложность (иногда O(n) при реаллокации) ** = O(n) в худшем случае, O(1) если вставляем/удаляем в конце

Детальное объяснение операций

push_back()

vector<int> v;
v.push_back(1);  // O(1) амортизированно
v.push_back(2);  // O(1)
v.push_back(3);  // O(1)

// Но иногда (при расширении):
// [1] -> [_][_] (реаллокация, O(n))
// Амортизированно: O(1), потому что реаллокация редкая

deque<int> d;
d.push_back(1);  // O(1) - добавляем в текущий блок
d.push_back(2);  // O(1)
// Если текущий блок полон, создаём новый: O(1) - не трогаем старые блоки

push_front() / pop_front()

vector<int> v = {1, 2, 3, 4, 5};
v.insert(v.begin(), 0);  // O(n) - сдвигаем все элементы!
// |1|2|3|4|5| -> |0|1|2|3|4|5|

deque<int> d = {1, 2, 3, 4, 5};
d.push_front(0);  // O(1) - добавляем в начало
// Один новый блок слева: |0| |1|2|3| |4|5|...

d.pop_front();  // O(1) - удаляем из начала

Доступ по индексу

vector<int> v = {1, 2, 3, 4, 5};
int x = v[2];  // O(1) - прямой доступ к памяти

deque<int> d = {1, 2, 3, 4, 5};
int y = d[2];  // O(1) - вычисляем индекс блока и позицию в блоке
// Индекс = 2 -> блок 0, позиция 2 -> O(1)

insert() и erase()

vector<int> v = {1, 2, 3, 4, 5};
v.insert(v.begin() + 2, 99);  // O(n) - сдвигаем элементы справа
// |1|2|99|3|4|5|

deque<int> d = {1, 2, 3, 4, 5};
d.insert(d.begin() + 2, 99);   // O(n) - тоже сдвигаем, но быстрее ближе к концам
// Если insert рядом с началом/концом -> O(k) где k = расстояние до концы

Когда использовать что?

Используй std::vector если:

• Много операций доступа по индексу
• Добавляешь элементы только в конец (push_back)
• Нужна кешевая локальность (линейная память)
• Передаёшь данные в C функции (нужен непрерывный буфер)

std::vector<int> scores;
for (int i = 0; i < 1000000; i++) {
    scores.push_back(rand() % 100);
    // ...
}
std::sort(scores.begin(), scores.end());  // Fast due to cache locality

Используй std::deque если:

• Добавляешь/удаляешь элементы в начало и конец
• Не критична кешевая локальность
• Память может быть фрагментирована
• Используется как очередь (FIFO)

std::deque<Task> queue;
while (true) {
    Task t = queue.front();     // O(1)
    queue.pop_front();           // O(1)
    process_task(t);
    
    queue.push_back(new_task);   // O(1)
}

Пример сравнения

#include <vector>
#include <deque>
#include <chrono>

int main() {
    // Test 1: push_front() - deque победит
    std::vector<int> v1;
    std::deque<int> d1;
    
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 100000; i++) {
        v1.insert(v1.begin(), i);  // O(n) каждый раз - медленно!
    }
    auto end = std::chrono::high_resolution_clock::now();
    // ~1 сек на современном ПК
    
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 100000; i++) {
        d1.push_front(i);  // O(1) - быстро!
    }
    end = std::chrono::high_resolution_clock::now();
    // ~0.01 сек
    
    // Test 2: random access - vector может быть быстрее
    std::cout << "v1[50000] = " << v1[50000] << std::endl;  // Очень быстро
    std::cout << "d1[50000] = " << d1[50000] << std::endl;  // Немного медленнее
}

Итоги и практика

Совет: По умолчанию используй vector. Переходи на deque только если:

1. Профилировщик показал bottleneck на push_front/pop_front
2. Элементы добавляются в обе стороны контейнера
3. Уверен, что это улучшит производительность

Использование RAII и правильный выбор контейнера — признак опытного C++ разработчика.