Максим Фатин | про IT

Вставляю за O(1) и в коней и в начало. Кто я?

Правильно — дек!

Как и обещал — раскрываю магию 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 и добавляет новые чанки при необходимости

ФУУХХХХ

Если просто долистал до конца, то красавчик! Ставлю тебе 🌭

🌭65🍓1

2.85K views06:18