Форум программистов, компьютерный форум CyberForum.ru

Дек в виде массива - C++

Восстановить пароль Регистрация
 
Soup_990
0 / 0 / 0
Регистрация: 16.11.2011
Сообщений: 34
24.12.2012, 00:14     Дек в виде массива #1
Подскажите как реализовать дек в виде массива.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.12.2012, 00:14     Дек в виде массива
Посмотрите здесь:

дек C++
C++ Простой список в виде массива.Как работать с элементами списка-массива через единую функцию
C++ Простой дек
C++ Дан массив А. Образовать реверс массива А в массиве В. Вывести оба массива и индексы элементов на экран в виде трех столбцов.
C++ Найти столбец массива с наибольшей суммой элементов и записатьегох в виде одномерного массива
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,919
Записей в блоге: 2
Завершенные тесты: 1
24.12.2012, 00:17     Дек в виде массива #2
В смысле так?
Дек в виде массива
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
24.12.2012, 08:11     Дек в виде массива #3
Это всё же развёрнутый список.

А массив это обычно циклический буфер. Представляете себе, как реализуется тот же вектор на массиве? Есть массив, слева в нём элементы вектора, справа незанятое пространство. Элементы добавляются слева направо, начиная с нулевого.

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

Также буфер циклический. К примеру, если мы будем добавлять постоянно элементы в начало, то они будут добавляться в левую незанятую половину. Но как только она заполнится, то мы не изменяем размер буфера, а продолжаем добавлять элементы уже с правого конца правой половины свободного пространства. Размер изменяется только тогда, когда весь буфер заполнен.
Avazart
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,629
Записей в блоге: 17
24.12.2012, 14:35     Дек в виде массива #4
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Вот для дека надо эту точку добавления сдвинуть к центру массива. Тогда незанятое пространство в массиве будет с обеих сторон от блока с содержимым дека. Соответственно, можно быстро добавлять-удалять элементы из начала-конца, так как место есть и сдвигать элементы не придётся.
Как я помню в деке нет перераспределения памяти, поэтому такой вариант не канает думаю.

Думаю нужно нечто вроде std::vector<T*> где T* указатели на массивы, естественно нужен будет хитрый итератор
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
24.12.2012, 15:43     Дек в виде массива #5
Цитата Сообщение от Avazart Посмотреть сообщение
Как я помню в деке нет перераспределения памяти, поэтому такой вариант не канает думаю.

Думаю нужно нечто вроде std::vector<T*> где T* указатели на массивы, естественно нужен будет хитрый итератор
Дек — это вообще АТД; вопрос, где взять память, не относится к деку как таковому. Если брать реализацию, то да, вообще циклический буфер не особо подходит из-за этих перемещений, поэтому обычно реализуют (в STL по крайней мере так) именно как развёрнутый список: делается двусвязный список блоков, в каждом из которых хранятся два указателя, массив данных и число занятых элементов в массиве (количество элементов в массиве в идеале такое, чтобы весь блок влез в кеш-линию). Для дека можно число элементов выкинуть из блока и хранить просто два числа: заполненности двух крайних блоков; это потому, что в деке нельзя вставлять в середину, а только по краям, так что неполными могут быть только крайние блоки.

Но, просто, я так понял, что надо именно в одном массиве.
Yandex
Объявления
24.12.2012, 15:43     Дек в виде массива
Ответ Создать тему
Опции темы

Текущее время: 01:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru