Правильно — дек!
Как и обещал — раскрываю магию std::deque из C++ или как в деке поддержать доступ по индексу за O(1)
Если коротко — нам нужен chunked array
Идея гениальна:
Вместо одного большого массива используется массив указателей на маленькие массивы (чанки)
👉 Структура
[ chunk1 ] [ chunk2 ] [ chunk3 ] [ chunk4 ]
↓ ↓ ↓ ↓
[..............] [..............] [..............] [..............]
Каждый chunk — небольшой массив фиксированного размера B
(обычно 8, 64 или 128 элементов — зависит от типа данных)
И дополнительно хранится таблица указателей на чанки:
chunks = [&chunk1, &chunk2, &chunk3, &chunk4]
👉 Начальное состояние
При создании deque выделяется первый chunk.
Кроме этого создаётся таблица указателей на чанки (chunks).
Она выделяется с запасом и стартует примерно с середины массива.
Это сделано специально, чтобы таблица могла расти и влево, и вправо.
Например:
chunks = [ _ _ _ &chunk1 _ _ _ ]
Теперь внутри chunk выбирается позиция:
head = tail
[ _ _ _ _ _ _ _ _ ]
↑
head, tail
Это означает, что дек пустой.
head — позиция первого элемента
tail — позиция сразу после последнего элемента
То есть элементы всегда лежат в диапазоне:
[ head ........ tail )
🚨 КАПЕЦ ВАЖНО!!!
head и tail — это глобальные позиции в структуре,
а не индексы внутри конкретного чанка.
Поэтому head может указывать НЕ на начало чанка, а на любую позицию внутри него.
Крайние чанки часто заполнены лишь частично — и это нормально.
Например дек может выглядеть так:
[ _ _ _ A B C D _ ]
↑ ↑
head tail
Здесь:
head -> указывает на первый элемент A
tail -> указывает на позицию сразу после последнего элемента D
То есть элементы лежат в диапазоне:
[ head ..... tail )
👉 Как работает push_front (вставка в начало)
Вставка в начало — это просто сдвиг head влево.
1) Уменьшаем head
head -= 1
2) Теперь нужно понять в какой chunk писать
chunk = head / m
offset = head % m
m — это размер чанка
3) Если нужного chunk ещё нет — создаём
и кладём ссылку на него в таблицу chunks
4) Записываем элемент
chunks[chunk][offset] = value
Если раньше head стоял в начале чанка — после head -= 1
мы автоматически перейдём в предыдущий chunk.
Никакие элементы не двигаются.
❗ Что если chunk получился отрицательным?
Это значит, что мы ушли левее начала массива chunks.
В этом случае:
1) создаётся новый массив указателей большего размера
2) старые указатели копируются примерно в середину нового массива
(копируются только указатели, не сами данные)
3) таблица снова получает свободное место слева и справа
После этого продолжаем вставку.
Такая операция происходит редко, поэтому вставка остаётся амортизированно O(1).
👉 Как работает pop_front (удаление из начала)
Удаление — это просто сдвиг head вправо.
1) Находим текущую позицию
chunk = head / m
offset = head % m
m — это размер чанка
2) Читаем элемент
value = chunks[chunk][offset]
3) Сдвигаем начало
head += 1
Если чанк слева полностью опустел — его можно удалить.
👉 Как получить i-й элемент (доступ по индексу)
Индекс i считается от текущего начала (head).
Сначала переводим его в абсолютную позицию:
pos = head + i
Теперь находим чанк и позицию внутри него:
chunk = pos / m
offset = pos % m
m — это размер чанка
И получаем элемент:
chunks[chunk][offset]
Вся магия в том, что deque никогда не двигает элементы
Он двигает только head/tail и добавляет новые чанки при необходимости
ФУУХХХХ
Если просто долистал до конца, то красавчик! Ставлю тебе 🌭