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

@squareroot · Регистрация: 19.10.2019

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

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)

Из разных статей вычитал что примерная реализация это динамический массив из динамических массивов.
Непонятно как он может расти при добавлении за константное время в ОБЕ! стороны так что при этом оставаться массивом из массива.
Он жн не связанный список.

@hoggy · 15.03.2020, 02:11

Сообщение от squareroot

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

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

Сообщение от squareroot

расти при добавлении за константное время в ОБЕ! стороны так что при этом оставаться массивом из массива.

добавление в конец амортизированно быстрая O(1)

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

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

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

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

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

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

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

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

таким образом вставка в попу - быстро-амортизированная операция.
вставка в голову - это вставка в попу предыдущему в списке.

@squareroot · 15.03.2020, 02:43 **[ТС]**

hoggy, Если дека это список векторов, то почему доступ к элементу за константное время ?

@lemegeton · 15.03.2020, 03:46

Сообщение от squareroot

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

Можно посмотреть на GCC реализацию на сайте gnu: https://gcc.gnu.org/onlinedocs... 02018.html

@DrOffset · 15.03.2020, 03:47

Сообщение от squareroot

Если дека это список векторов, почему доступ к элементу за константное время ?

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

@lemegeton · 15.03.2020, 03:48

Сообщение от squareroot

Если дека это список векторов, то почему доступ к элементу за константное время ?

А в чём противоречие? Достаём из первого измерения по индексу за константу плюс из второго измерения сам элемент за константу. Константа плюс константа равно константа.

@DrOffset · 15.03.2020, 03:54

Сообщение от lemegeton

А в чём противоречие?

Изначально противоречие в том, что у списка нет индекса

Но его, как я уже сказал, можно построить дополнительно.
Реализация в GNU, кстати, больше похожа на вектор векторов, чем на список векторов.

@lemegeton · 15.03.2020, 03:58

Сообщение от DrOffset

Реализация в GNU, кстати, больше похожа на вектор векторов, чем на список векторов.

В вижуал студии более хитро, но тоже никакого списка векторов не наблюдается.
Откуда инфа про список векторов?

@squareroot · 15.03.2020, 03:59 **[ТС]**

Сообщение от DrOffset

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

Что такое "дополнительный индекс" ? динамически массив в дополнении к списку ? А вставка тогда как может быть за константное время тогда ?

@DrOffset · 15.03.2020, 04:02

Сообщение от lemegeton

Откуда инфа про список векторов?

Ну это каноничная, наивная реализация этой структуры.
Обычно новичкам ее объясняют именно так.

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

Добавлено через 1 минуту

Сообщение от squareroot

А вставка тогда как может быть за константное время тогда ?

Обычно тут понимается амортизированная константа, а не честная константа.

@lemegeton · 15.03.2020, 04:02

Сообщение от squareroot

Из разных статей вычитал что примерная реализация это динамический массив из динамических массивов.

Вот оттуда и константная скорость роста сложности.

@squareroot 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

@hoggy 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

@squareroot 6 / 6 / 0 Регистрация: 19.10.2019 Сообщений: 439
	15.03.2020, 02:43 [ТС]	3
	hoggy, Если дека это список векторов, то почему доступ к элементу за константное время ? 0

@lemegeton 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

@DrOffset 14016 / 7504 / 1774 Регистрация: 30.01.2014 Сообщений: 12,559
	15.03.2020, 03:47	5
	Сообщение от squareroot Если дека это список векторов, почему доступ к элементу за константное время ? Вот там же, откуда вы взяли информацию о константной сложности индексации, написано почему: строится дополнительный индекс для этого (он индексирует уже элементы списка). 0

@lemegeton 3053 / 1458 / 492 Регистрация: 29.11.2010 Сообщений: 2,888
	15.03.2020, 03:48	6
	Сообщение от squareroot Если дека это список векторов, то почему доступ к элементу за константное время ? А в чём противоречие? Достаём из первого измерения по индексу за константу плюс из второго измерения сам элемент за константу. Константа плюс константа равно константа. 0

@DrOffset 14016 / 7504 / 1774 Регистрация: 30.01.2014 Сообщений: 12,559
	15.03.2020, 03:54	7
	Сообщение от lemegeton А в чём противоречие? Изначально противоречие в том, что у списка нет индекса Но его, как я уже сказал, можно построить дополнительно. Реализация в GNU, кстати, больше похожа на вектор векторов, чем на список векторов. 0

@lemegeton 3053 / 1458 / 492 Регистрация: 29.11.2010 Сообщений: 2,888
	15.03.2020, 03:58	8
	Сообщение от DrOffset Реализация в GNU, кстати, больше похожа на вектор векторов, чем на список векторов. В вижуал студии более хитро, но тоже никакого списка векторов не наблюдается. Откуда инфа про список векторов? 0

@squareroot 6 / 6 / 0 Регистрация: 19.10.2019 Сообщений: 439
	15.03.2020, 03:59 [ТС]	9
	Сообщение от DrOffset Вот там же, откуда вы взяли информацию о константной сложности индексации, написано почему: строится дополнительный индекс для этого (он индексирует уже элементы списка). Что такое "дополнительный индекс" ? динамически массив в дополнении к списку ? А вставка тогда как может быть за константное время тогда ? 0

@DrOffset 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

Опции темы

@lemegeton 3053 / 1458 / 492 Регистрация: 29.11.2010 Сообщений: 2,888
	15.03.2020, 04:02	11
	Сообщение от squareroot Из разных статей вычитал что примерная реализация это динамический массив из динамических массивов. Вот оттуда и константная скорость роста сложности. 0