Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.85/13: Рейтинг темы: голосов - 13, средняя оценка - 4.85
29 / 1 / 1
Регистрация: 30.08.2013
Сообщений: 37
1

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

17.09.2014, 22:28. Просмотров 2394. Ответов 3
Метки нет (Все метки)

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

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

Вторая реализация - это список с множественными связями. То есть каждый элемент ссылался не только на левого и правого соседа, но и (при условии их существования), на 10-й, 100-й, 1000-й и т.д до 10000000-го элемент.
При добавлении/удалении элемента приходилось переопределять эти 8 указателей, но при доступе к произвольному элементу в здоровых массивах выигрыш получался солидным (хотя сложность опять-же линейная)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.09.2014, 22:28
Ответы с готовыми решениями:

Как устроена std::deque внутри ?
Не могу себе представить возможную внутреннюю реализацию этого контенера, чтоб она удовлетворяла...

Как инициализировать объект типа std::deque<int>?
Доброе время суток! Я видимо совсем не разбираюсь в шаблонах, так как не понимаю почему не...

std::deque
Как известно при добавлении в конец вектора элементов(и не только в конец) может возникнуть...

Разделить std::deque на заданное количество деков
Имеется дек, нужно его разделить на отдельные деки. Это задание я сделал когда знал точное...

3
13881 / 7417 / 1759
Регистрация: 30.01.2014
Сообщений: 12,410
17.09.2014, 22:59 2
Цитата Сообщение от 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
Эксперт С++
1661 / 1033 / 174
Регистрация: 27.09.2009
Сообщений: 1,945
17.09.2014, 23:00 3
Дек - это, выражаясь упрощённо, массив массивов. Точнее, динамический массив, подобный вектору, элементами которого являются блоки. Если они имеют фиксированную длину L, то элемент дека N находится в блоке N / L по смещению N % L. Вычисление двух индексов и доступ по ним - вполне себе constant time.
Поскольку при добавлении элементов в начало дека мы можем просто добавить новый блок в начало и писать туда, нам не надо двигать элементы при добавлении и удалении в начале и конце. Тут надо ещё запоминать смещение первого элемента относительно первого блока и формулы чуть-чуть усложняются.
0
29 / 1 / 1
Регистрация: 30.08.2013
Сообщений: 37
17.09.2014, 23:25  [ТС] 4
Nick Alte, понятно что дек это массив блоков, и очевидно, что если объем блока известен, то вычислить нужный - не проблема. Проблема в том, что если массив связанный, то попасть туда, не пройдя по всем предыдущим нельзя, а если массив непрерывный, то для записи нового блока в начало нужно сдвигать указатели на остальные блоки, понятно, что это быстрее чем таскать каждый отдельный элемент, особенно если там не просто числа а какие-нибудь здоровые классы, но тоже не гуд.
Во всяком случае, постоянной сложностью там и не пахнет, в лучшем случае, как сказал DrOffset - амортизированная.

По поводу конкретного примера - мне нужно было сливать данные с внешней железки в реалтайме и прогонять кое - какую статистическую обработку (аппроксимация, расчет ошибок и т.д.). Все это должно было крутиться на довольно слабом ноуте, вот и пришлось развлекаться.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.09.2014, 23:25

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Не работает std::cout || std::cin
#include &quot;Account.h&quot; #include &lt;string&gt; #include &lt;iostream&gt; using std::cout; Account ::...

Как работает std::declval?
В общем понятно - позволяет использовать в decltype тип который возвращает метод шаблонного...

Как работает std::piecewise_construct?
Здравствуйте! Мне необходимо содержать std::map с уникальными значениями, что-то вида: S...

Как работает функция std::string::find(...)
здравствуйте есть допустим вот такой код #include &lt;iostream&gt; #include &lt;string&gt; using namespace...

Как работает функция std::string::replace, какие аргументы поддерживает?
Кто знает, как работает функция std::string::replace, какие аргументы поддерживает? А то запись...

Как искать по std::vecotr из std::pait по одному значению из пары?
? :) Пункт 4.7 Правил: Как можно более полно описывайте суть проблемы или вопроса, что было...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.