Как работает std::deque?

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

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

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

0

Сообщение от Erik945 А вот произвольный доступ к элементу с постоянной сложностью вообще не понятен.

23.2.3 Sequence containers

16 Table 101 lists operations that are provided for some types of sequence containers but not others. An implementation shall provide these operations for all container types shown in the “container” column, and shall implement them so as to take amortized constant time. Table 101 — Optional sequence container operations ... push_front, push_back, operator[]

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

Сообщение от Erik945 По идее, надо пройти по указателю в следующий блок, проверить есть-ли искомый элемент там, и либо вернуть его, либо рекурсивно идти дальше - а это уже линейная сложность.

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

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

1

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

0

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

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

0