Как в памяти представляется двусторонняя очередь (deque)?

@rovel · Регистрация: 14.10.2011

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

@Avazart · 18.05.2012, 23:25

std::deque

@rovel · 19.05.2012, 00:35 **[ТС]**

допустим в памяти у нас хранится какое то число, мы можем добавляться и удалять сначала и конца его цифры если у нас дек?если да, то как это делается, не могли бы вы рассказать?

@Avazart · 19.05.2012, 00:54

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

@rovel · 25.05.2012, 14:54 **[ТС]**

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

@Avazart · 25.05.2012, 22:22

Нужно "хранилище" в котором будут храниться указатели на все участки памяти.
Ну а чем может быть это хранище - вопрос.
В принципе это может быть тот же vector<T*> или list<T*> в который при необходимости будет добаляться указатель на массив(новый участок памяти)
Но тут можно лишь строить догадки... например если участки памяти выделяются разной длины то кроме указателя на массив нужно еще хранить и размер массива.
Как оно в действительности реализовано в STL я не встречал.

@Damaks · 26.05.2012, 04:23

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

@Avazart · 26.05.2012, 04:35

Damaks- это будет не то что нужно так как vector делает перераспределение, а deque- не должен это делать.Из за этого возможно снижение эффективности и невалидность итераторов

Поэтому если и использовать vector то строго постоянного размера

MrGluck · 26.05.2012, 04:37

Скорее на основе 2 списков

@Avazart · 26.05.2012, 04:48

Скорее на основе 2 списков

Думаю сильно круто...
А доступ к элементам?

Добавлено через 5 минут
Я думаю достаточно что-то вроде vector<pair<T*,size_t> > v_ptr; и обычных массивов T[size];

@gray_fox · 26.05.2012, 14:43

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

Я думаю достаточно что-то вроде vector

Нельзя вектор, т.к. при добавлении может быть перераспределение памяти и все итераторы\ссылки на остальные элементы станут недействительны. Голосую за список массивов:
list<value_type [page_size]>.

@Avazart · 26.05.2012, 15:41

gray_fox вектор как хранище ссылок, а не хранилеще объектов - для объектов обычный массив
Но list тоже подходит только время доступа возможно увеличится...

@rovel · 30.05.2012, 20:39 **[ТС]**

Знающие люди, пожалуйста помогите понять, что такое двустороняя очередь, простая очередь, списки и двусвязные списки...Я перерыл инет, не могу ничего стоящего найти.В чем отличие простой очереди от списка?В чем отличие очереди от двусторонней очереди?В чем отличие двусторонней очереди от двусвязного списка?или в чем отличие двусторонней очереди от списка? или дайте ссылку на сайт , где все это есть...ато я уже запутался.........

@Avazart · 30.05.2012, 20:48

Блин что за привычка сразу интернет?
Ведь есть еще и книги...к стати я в той теме указал от куда рисунок вырезал.

@rovel · 30.05.2012, 21:46 **[ТС]**

по этой книге я не могу все разобрать...

@rovel 0 / 0 / 0 Регистрация: 14.10.2011 Сообщений: 25
	30.05.2012, 20:39 [ТС]	13
	Знающие люди, пожалуйста помогите понять, что такое двустороняя очередь, простая очередь, списки и двусвязные списки...Я перерыл инет, не могу ничего стоящего найти.В чем отличие простой очереди от списка?В чем отличие очереди от двусторонней очереди?В чем отличие двусторонней очереди от двусвязного списка?или в чем отличие двусторонней очереди от списка? или дайте ссылку на сайт , где все это есть...ато я уже запутался......... 0

@Avazart 8354 / 6092 / 610 Регистрация: 10.12.2010 Сообщений: 28,391 Записей в блоге: 29
	18.05.2012, 23:25	2
	std::deque 1

@rovel 0 / 0 / 0 Регистрация: 14.10.2011 Сообщений: 25
	19.05.2012, 00:35 [ТС]	3
	допустим в памяти у нас хранится какое то число, мы можем добавляться и удалять сначала и конца его цифры если у нас дек?если да, то как это делается, не могли бы вы рассказать? 0

@Avazart 8354 / 6092 / 610 Регистрация: 10.12.2010 Сообщений: 28,391 Записей в блоге: 29
	19.05.2012, 00:54	4
	Нигде не видил чтоб описывался подобный процес. Но предпологаю что если в выделенном куске памяти еще есть зарезервированное место (как в векторе) если нет, то выделяется новый кусок и добавляется указатель на него (как в листе). 0

@rovel 0 / 0 / 0 Регистрация: 14.10.2011 Сообщений: 25
	25.05.2012, 14:54 [ТС]	5
	я показал преподователю эту картинку двусторонней очереди , он мне говорит, типа что нужно ,чтобы реализовать такую байду?какие переменные, указатели?Люююдиии помогите разобраться 0

@Avazart 8354 / 6092 / 610 Регистрация: 10.12.2010 Сообщений: 28,391 Записей в блоге: 29
	25.05.2012, 22:22	6
	Нужно "хранилище" в котором будут храниться указатели на все участки памяти. Ну а чем может быть это хранище - вопрос. В принципе это может быть тот же vector<T> или list<T> в который при необходимости будет добаляться указатель на массив(новый участок памяти) Но тут можно лишь строить догадки... например если участки памяти выделяются разной длины то кроме указателя на массив нужно еще хранить и размер массива. Как оно в действительности реализовано в STL я не встречал. 0

@Damaks 19 / 11 / 0 Регистрация: 02.09.2010 Сообщений: 235
	26.05.2012, 04:23	7
	Можно сделать на основе 2-х векторов и абстрактно считать что один увеличивается в одну сторону, а другой в другую. Тогда будет быстрое добавление и удаление элементов в конец и начало. Только в такой системе возникнут проблемы если в одном из векторов удалятся все элементы и удаление перекинется на другой. В таких случаях их надо балансировать, в идеале чтобы в каждом было поровну элементов. 0

@Avazart 8354 / 6092 / 610 Регистрация: 10.12.2010 Сообщений: 28,391 Записей в блоге: 29
	26.05.2012, 04:35	8
	Damaks- это будет не то что нужно так как vector делает перераспределение, а deque- не должен это делать.Из за этого возможно снижение эффективности и невалидность итераторов Поэтому если и использовать vector то строго постоянного размера 0

MrGluck Форумчанин 8164 / 5012 / 1436 Регистрация: 29.11.2010 Сообщений: 13,455
	26.05.2012, 04:37	9
	Скорее на основе 2 списков 0

@Avazart 8354 / 6092 / 610 Регистрация: 10.12.2010 Сообщений: 28,391 Записей в блоге: 29
	26.05.2012, 04:48	10
	Скорее на основе 2 списков Думаю сильно круто... А доступ к элементам? Добавлено через 5 минут Я думаю достаточно что-то вроде vector<pair<T*,size_t> > v_ptr; и обычных массивов T[size]; 0

@gray_fox What a waste! 1588 / 1287 / 173 Регистрация: 21.04.2012 Сообщений: 2,696
	26.05.2012, 14:43	11
	Сообщение от Avazart Я думаю достаточно что-то вроде vector Нельзя вектор, т.к. при добавлении может быть перераспределение памяти и все итераторы\ссылки на остальные элементы станут недействительны. Голосую за список массивов: list<value_type [page_size]>. 0

Опции темы

@Avazart 8354 / 6092 / 610 Регистрация: 10.12.2010 Сообщений: 28,391 Записей в блоге: 29
	26.05.2012, 15:41	12
	gray_fox вектор как хранище ссылок, а не хранилеще объектов - для объектов обычный массив Но list тоже подходит только время доступа возможно увеличится... 0

@Avazart 8354 / 6092 / 610 Регистрация: 10.12.2010 Сообщений: 28,391 Записей в блоге: 29
	30.05.2012, 20:48	14
	Блин что за привычка сразу интернет? Ведь есть еще и книги...к стати я в той теме указал от куда рисунок вырезал. 0

@rovel 0 / 0 / 0 Регистрация: 14.10.2011 Сообщений: 25
	30.05.2012, 21:46 [ТС]	15
	по этой книге я не могу все разобрать... 0