Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.86/7: Рейтинг темы: голосов - 7, средняя оценка - 4.86
6 / 6 / 0
Регистрация: 19.10.2019
Сообщений: 439
1

Как устроена std::deque внутри ?

15.03.2020, 01:28. Просмотров 1326. Ответов 10
Метки нет (Все метки)


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

The complexity (efficiency) of common operations on deques is as follows:

Random access - constant O(1)
Insertion or removal of elements at the end or beginning - constant O(1)
Insertion or removal of elements - linear O(n)

Из разных статей вычитал что примерная реализация это динамический массив из динамических массивов.
Непонятно как он может расти при добавлении за константное время в ОБЕ! стороны так что при этом оставаться массивом из массива.
Он жн не связанный список.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.03.2020, 01:28
Ответы с готовыми решениями:

Как работает std::deque?
Пытаюсь разобраться в работе std-шного дека. Веб-серфинг дал следующее: Данные хранятся в куче...

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

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

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

10
Эксперт С++
8394 / 3934 / 859
Регистрация: 15.11.2014
Сообщений: 8,881
15.03.2020, 02:11 2
Цитата Сообщение от squareroot Посмотреть сообщение
Не могу себе представить возможную внутреннюю реализацию этого контенера, чтоб она удовлетворяла всем требованиям по вычислительной сложности.
я как то особо этим вопросом не заморачивался, однако первое что приходит в голову:
дек - это не массив массивов.
это - список векторов.

Цитата Сообщение от squareroot Посмотреть сообщение
расти при добавлении за константное время в ОБЕ! стороны так что при этом оставаться массивом из массива.
добавление в конец амортизированно быстрая O(1)

например, есть вектор:
[1][2][3][][][][]

пустые клетки - это резерв.
пока он не исчерпался, всегда можно просто взять и добавить ещё один элемент:

[1][2][3][4][][][]

теперь добавляем элемент (нолик) в начало дека:

[0][][][][][][]
[1][2][3][4][][][]


что бы не нужно было сдвигать элементы вправо,
можно просто вставить ещё один вектор "перед" текущим.

а внешне очередность получается:
([0])([1][2][3][4])

круглыми скобками я выделил вектора.

таким образом вставка в попу - быстро-амортизированная операция.
вставка в голову - это вставка в попу предыдущему в списке.
0
6 / 6 / 0
Регистрация: 19.10.2019
Сообщений: 439
15.03.2020, 02:43  [ТС] 3
hoggy, Если дека это список векторов, то почему доступ к элементу за константное время ?
0
3053 / 1458 / 492
Регистрация: 29.11.2010
Сообщений: 2,888
15.03.2020, 03:46 4
Цитата Сообщение от squareroot Посмотреть сообщение
Не могу себе представить возможную внутреннюю реализацию этого контенера, чтоб она удовлетворяла всем требованиям по вычислительной сложности.
Можно посмотреть на GCC реализацию на сайте gnu: https://gcc.gnu.org/onlinedocs... 02018.html
0
14016 / 7504 / 1774
Регистрация: 30.01.2014
Сообщений: 12,559
15.03.2020, 03:47 5
Цитата Сообщение от squareroot Посмотреть сообщение
Если дека это список векторов, почему доступ к элементу за константное время ?
Вот там же, откуда вы взяли информацию о константной сложности индексации, написано почему: строится дополнительный индекс для этого (он индексирует уже элементы списка).
0
3053 / 1458 / 492
Регистрация: 29.11.2010
Сообщений: 2,888
15.03.2020, 03:48 6
Цитата Сообщение от squareroot Посмотреть сообщение
Если дека это список векторов, то почему доступ к элементу за константное время ?
А в чём противоречие? Достаём из первого измерения по индексу за константу плюс из второго измерения сам элемент за константу. Константа плюс константа равно константа.
0
14016 / 7504 / 1774
Регистрация: 30.01.2014
Сообщений: 12,559
15.03.2020, 03:54 7
Цитата Сообщение от lemegeton Посмотреть сообщение
А в чём противоречие?
Изначально противоречие в том, что у списка нет индекса
Но его, как я уже сказал, можно построить дополнительно.
Реализация в GNU, кстати, больше похожа на вектор векторов, чем на список векторов.
0
3053 / 1458 / 492
Регистрация: 29.11.2010
Сообщений: 2,888
15.03.2020, 03:58 8
Цитата Сообщение от DrOffset Посмотреть сообщение
Реализация в GNU, кстати, больше похожа на вектор векторов, чем на список векторов.
В вижуал студии более хитро, но тоже никакого списка векторов не наблюдается.
Откуда инфа про список векторов?
0
6 / 6 / 0
Регистрация: 19.10.2019
Сообщений: 439
15.03.2020, 03:59  [ТС] 9
Цитата Сообщение от DrOffset Посмотреть сообщение
Вот там же, откуда вы взяли информацию о константной сложности индексации, написано почему: строится дополнительный индекс для этого (он индексирует уже элементы списка).
Что такое "дополнительный индекс" ? динамически массив в дополнении к списку ? А вставка тогда как может быть за константное время тогда ?
0
14016 / 7504 / 1774
Регистрация: 30.01.2014
Сообщений: 12,559
15.03.2020, 04:02 10
Цитата Сообщение от lemegeton Посмотреть сообщение
Откуда инфа про список векторов?
Ну это каноничная, наивная реализация этой структуры.
Обычно новичкам ее объясняют именно так.

Для автора: https://stackoverflow.com/ques... que-in-stl
Думаю, снимет оставшиеся вопросы.

Добавлено через 1 минуту
Цитата Сообщение от squareroot Посмотреть сообщение
А вставка тогда как может быть за константное время тогда ?
Обычно тут понимается амортизированная константа, а не честная константа.
0
3053 / 1458 / 492
Регистрация: 29.11.2010
Сообщений: 2,888
15.03.2020, 04:02 11
Цитата Сообщение от squareroot Посмотреть сообщение
Из разных статей вычитал что примерная реализация это динамический массив из динамических массивов.
Вот оттуда и константная скорость роста сложности.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.03.2020, 04:02

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

Перемещение элементов внутри deque
Пытаюсь реализовать класс чекера прокси . Логика примерно такая : Объекты прокси хранятся в deque...

Как устроена рекурсия?
Давно хотел спросить каким боком она работает? К примеру void RecFunction(int level) { if...

как устроена динамическая идентификация типов
Здрасте! Меня интересует, как компилируемая программа может проводить RTTI , если во время...

Переместить элемент внутри списка std::list
Что-то я не пойму, простая вроде задача - переместить элемент внутри спиcка std::list - стандартной...

Использование std::array внутри пользовательского класса
Здравствуйте! Я создал класс, одним из полей которого является массив std::array, однако...

Std::map или string внутри класса?
Как эффективней хранить экземпляры класса, что бы потом находить нужный? В связки std::map или...


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

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

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