@Erik945

Пытаюсь разобраться в работе std-шного дека. Веб-серфинг дал следующее:
Данные хранятся в куче небольшими блоками(массивами) в виде связанного списка.
С добавлением/удалением элементов более - менее все ясно - данные записываются в блок, когда он заканчивается, создается новый, связывается указателями с нужной стороны, и запись идет уже в него.
А вот произвольный доступ к элементу с постоянной сложностью вообще не понятен. Внутри одного блока все просто, но как быть если надо пройти дальше?
По идее, надо пройти по указателю в следующий блок, проверить есть-ли искомый элемент там, и либо вернуть его, либо рекурсивно идти дальше - а это уже линейная сложность.

В свое время реализовывал дек двумя способами - первый это что-то вроде вектора, только данные начинали писаться не сначала, а с середины, и когда с какой либо стороны упирались в конец блока, выделялся новый (больший) массив, и переписывал этот существующий дек туда, центруя данные.

Вторая реализация - это список с множественными связями. То есть каждый элемент ссылался не только на левого и правого соседа, но и (при условии их существования), на 10-й, 100-й, 1000-й и т.д до 10000000-го элемент.
При добавлении/удалении элемента приходилось переопределять эти 8 указателей, но при доступе к произвольному элементу в здоровых массивах выигрыш получался солидным (хотя сложность опять-же линейная)

0

@DrOffset

23.2.3 Sequence containers
Т.е. там не константная сложность, а амортизированная константная сложность. Это немного разные вещи.

размер блока фиксирован, количество блоков известно, определить по индексу в какой блок прыгать не сложно. Связный список не обязателен, может быть и массив.

Добавлено через 11 минут
Erik945, В любом случае о способе организации можно рассуждать только на конкретном примере. Ну вот, например, реализация gnu.

1

@Nick Alte

Дек - это, выражаясь упрощённо, массив массивов. Точнее, динамический массив, подобный вектору, элементами которого являются блоки. Если они имеют фиксированную длину L, то элемент дека N находится в блоке N / L по смещению N % L. Вычисление двух индексов и доступ по ним - вполне себе constant time.
Поскольку при добавлении элементов в начало дека мы можем просто добавить новый блок в начало и писать туда, нам не надо двигать элементы при добавлении и удалении в начале и конце. Тут надо ещё запоминать смещение первого элемента относительно первого блока и формулы чуть-чуть усложняются.

0

@Erik945

Nick Alte, понятно что дек это массив блоков, и очевидно, что если объем блока известен, то вычислить нужный - не проблема. Проблема в том, что если массив связанный, то попасть туда, не пройдя по всем предыдущим нельзя, а если массив непрерывный, то для записи нового блока в начало нужно сдвигать указатели на остальные блоки, понятно, что это быстрее чем таскать каждый отдельный элемент, особенно если там не просто числа а какие-нибудь здоровые классы, но тоже не гуд.
Во всяком случае, постоянной сложностью там и не пахнет, в лучшем случае, как сказал DrOffset - амортизированная.

По поводу конкретного примера - мне нужно было сливать данные с внешней железки в реалтайме и прогонять кое - какую статистическую обработку (аппроксимация, расчет ошибок и т.д.). Все это должно было крутиться на довольно слабом ноуте, вот и пришлось развлекаться.

0