|
19 / 19 / 18
Регистрация: 25.08.2014
Сообщений: 186
|
|
Написать свою реализацию deque27.10.2014, 16:07. Показов 15274. Ответов 41
Метки нет (Все метки)
Всем привет, требуется написать свою реализацию deque.
Я до этого никогда не сталкивался с распределением памяти, аллокаторами и другими вещами, которые в этом деле, по-видимому, придется заюзать. Расскажите, куда копать? Самая проблема с памятью, сам класс-то не очень сложный, почти что обычный массив.
0
|
|
| 27.10.2014, 16:07 | |
|
Ответы с готовыми решениями:
41
Написать свою реализацию функций нахождения косинуса и синуса Написать программу использующую пользовательские классы Stack, Queue, Deque
|
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||
| 28.10.2014, 12:29 | ||
|
0
|
||
|
19 / 19 / 18
Регистрация: 25.08.2014
Сообщений: 186
|
|||||||||||
| 28.10.2014, 22:59 [ТС] | |||||||||||
|
Попытался разобраться с памятью, решил для начала сделать обычный массив.
Постепенно мне казалось что начинаю вникать, но в итоге я ничего не понял. iter_begin и iter_end возвращают какой-то свой внутренний виртуальный адрес, и я не могу понять почему, а при попытке доступа к *iter_begin и *iter_end прога падает. Объясните, пожалуйста.
Да, так же не понял, почему не получается в конструкторе сделать так:
0
|
|||||||||||
|
19506 / 10109 / 2464
Регистрация: 30.01.2014
Сообщений: 17,834
|
||
| 28.10.2014, 23:22 | ||
|
Wiiiiijjj, память, на которую потенциально могли бы указывать твои iter_begin и iter_end, не была тобой выделена нигде. Вот и падает.
0
|
||
|
19 / 19 / 18
Регистрация: 25.08.2014
Сообщений: 186
|
|||||||||||
| 29.10.2014, 00:56 [ТС] | |||||||||||
|
Наверное, я чего-то фундаментального не понимаю, опять не робит
![]()
Добавлено через 19 минут Кликните здесь для просмотра всего текста
Не по теме: pastebin .com/JaTPtLf2
0
|
|||||||||||
|
19506 / 10109 / 2464
Регистрация: 30.01.2014
Сообщений: 17,834
|
|||||||
| 29.10.2014, 08:29 | |||||||
|
А у тебя сейчас создаются два независимх единичных объекта типа T, и между указателями на них нельзя производить адресную арифметику - это разная память. Добавлено через 5 минут Вот примерно это я имею в виду:
1
|
|||||||
|
19 / 19 / 18
Регистрация: 25.08.2014
Сообщений: 186
|
||||||
| 29.10.2014, 13:07 [ТС] | ||||||
|
Сейчас будет очень много глупых вопросов, как и всегда. Я запутался (как и всегда).
2. warning: 'MyPersonalArrayType<char>::iter_end' will be initialized after [-Wreorder] Что значит это предупреждение? Ведь таким же способом я инициализирую и ::iter_begin, почему он на это так не ругается? 3. Как сделать корректное освобождение памяти? Опять же, когда размер не увеличивается в будущем, то удаляется вроде корректно, без утечек — delete []iter_begin; delete iter_end; — я же правильно понимаю? Как тогда сделать правильно с resize()? 4. Как вставляются и удаляются элементы?
0
|
||||||
|
19506 / 10109 / 2464
Регистрация: 30.01.2014
Сообщений: 17,834
|
||||
| 29.10.2014, 13:29 | ||||
|
Остальное потом посмотрю - некогда. Ну или может еще кто ответит.
1
|
||||
|
19 / 19 / 18
Регистрация: 25.08.2014
Сообщений: 186
|
|||||||||||
| 30.10.2014, 12:21 [ТС] | |||||||||||
|
Падало почему-то как раз когда новый размер меньше старого. Т.е. вот при таком мейне не падает:
Вроде логика есть — создать новые два пойнтера, записать прошлый массив, потом новую часть заполнить нулями, удалить старые и присвоить им эти. Проблема в реализации? Буду сейчас дебажить.
Объясните в чем ошибка, не могу понять
0
|
|||||||||||
|
655 / 576 / 164
Регистрация: 13.12.2012
Сообщений: 2,126
|
||||||
| 30.10.2014, 12:26 | ||||||
1
|
||||||
|
19 / 19 / 18
Регистрация: 25.08.2014
Сообщений: 186
|
|
| 30.10.2014, 12:43 [ТС] | |
|
Как же в деке реализовать добавление/удаление в начало?
Не перезаписывать же все элементы каждый раз.
0
|
|
|
19506 / 10109 / 2464
Регистрация: 30.01.2014
Сообщений: 17,834
|
||
| 30.10.2014, 13:41 | ||
|
В случае массива, да, перезаписывать каждый раз. Именно поэтому в std::vector нет функции push_front.
1
|
||
|
19 / 19 / 18
Регистрация: 25.08.2014
Сообщений: 186
|
|
| 30.10.2014, 14:10 [ТС] | |
|
DrOffset, да, массив, но это просто чтобы вникнуть хоть чуть-чуть в работу с памятью, в итоге мне необходимо сделать дек.
Как же реализуется дек? Гугл не помогает, там только примеры работы с обычным из библиотеки шаблонов. В стандартной же реализации столько шаманства, что вообще не получается вникнуть. Объясните принцип, по которому это делается, я попытаюсь отдельно все по пунктам навелосипедить, хоть как-нибудь, время поджимает, а результата null.
0
|
|
|
19506 / 10109 / 2464
Регистрация: 30.01.2014
Сообщений: 17,834
|
||
| 30.10.2014, 14:31 | ||
|
Предлагаю начать с реализации связного списка. Потом эту реализацию можно модифицировать, чтобы получился дек.
1
|
||
|
19 / 19 / 18
Регистрация: 25.08.2014
Сообщений: 186
|
||||||
| 30.10.2014, 17:58 [ТС] | ||||||
|
DrOffset, нашел много полезного материала про связные списки, помогло понять.
Но опять как всегда, валится на любом из методов.
0
|
||||||
|
19506 / 10109 / 2464
Регистрация: 30.01.2014
Сообщений: 17,834
|
|||||||
| 30.10.2014, 18:28 | |||||||
1
|
|||||||
|
19 / 19 / 18
Регистрация: 25.08.2014
Сообщений: 186
|
||||||
| 30.10.2014, 18:55 [ТС] | ||||||
|
DrOffset, почему-то теперь вылетает при связи элементов, добавленных в конец, и в начало
![]()
0
|
||||||
|
19506 / 10109 / 2464
Регистрация: 30.01.2014
Сообщений: 17,834
|
|
| 30.10.2014, 19:02 | |
Сообщение было отмечено Wiiiiijjj как решение
Решение
Wiiiiijjj, потому что в методе push_back поле first надо тоже назначать. Если элементов не было, то first будет указывать на только что созданный элемент, если элементы уже есть, то first не трогаем. В push_front - наоборот, last меняется, только если до этого не было элементов, в остальных случаях меняется first.
1
|
|
|
19 / 19 / 18
Регистрация: 25.08.2014
Сообщений: 186
|
|||||||||||
| 30.10.2014, 21:59 [ТС] | |||||||||||
|
DrOffset, а если, например, элементов не было, мы пушнули в конец что-то и first на это указывает, то что хранится в значении first?
Добавлено через 43 минуты Просто не понимаю, как избежать двойственности: добавляю в пустой дек один элемент, а получается два.
UPD: Разобрался с этим.
DrOffset, большое спасибо за проявленное терпение и помощь
0
|
|||||||||||
|
|
|
| 24.09.2016, 21:40 | |
|
На самом деле std::deque представляет из себя массив указателей на мини-массивы из 1...16 хранимых элементов.
Для std::deque<int> это будет массив указателей на мини-массив из 4-х целых чисел. Для std::deque<char> это будет массив указателей на мини-массив из 16-и символов. Т.е. количество вмещаемых элементов в такие мини-массивы равно 16 / sizeof(value_type). Дальше буду опираться только на std::deque<int>, а массив указателей на мини-массив будет просто map. При вставке первого элемента, выделяется память под массив из 8 указателей (map[8][4]). Вместимость контейнера при этом будет под 32 элемента типа int. При вставке int в конец контейнера методом push_back в самой map этот int будет записан в самое её начало (map[0][0]), а при вставке в начало контейнера - в самый её конец (map[7][3]) При следующей вставке методом push_back, int будет записан в map[0][1], а при вставке методом push_front в map[7][2] и т.д. Вставка будет без проблем продолжаться, пока индексы указателей, соответствующие методам push_back и push_front не столкнутся т.е. пока не произойдёт map[idx push_front][] == map[idx push_back][]. В этом случае будет заново выделен массив ЧИСТО под указатели, но в двойном размере, т.е. map[16][4] (в следующий раз map[32][4] и т.д.). Значения указателей прошлого массива будут записаны в новый, но при этом значения тех указателей, которые использовались методом push_front будут записаны в самый конец нового массива. Далее несложно догадаться, как реализован operator[]: контейнер должен хранить значение количества элементов, вставленных методом push_front, а также общее количество элементов для того, чтобы правильно вычислить индексы при вытаскивании значения из map. Метод insert не смотрел, но думаю, что сначала определяется, между какими элементами вставляется новый элемент - между push_back-элементами или push_front-элементами, и затем происходит перестановка либо одних, либо других.
0
|
|
|
Любитель чаепитий
|
|
| 25.09.2016, 00:05 | |
|
0
|
|
| 25.09.2016, 00:05 | |
|
Написать реализацию перегрузки функции Написать реализацию перегруженных функций Написать собственную реализацию стандартной функции strstr Подскажите пожалуйста как написать реализацию алгоритма Написать собственную реализацию функции strcmp() согласно условию Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Как установить и настроить Windows 11 без подключения к Интернету и без аккаунта Microsoft
Maks 22.11.2026
Положу сюда, чтобы не искать постоянно.
• На экране «Давайте подключим вас к сети» во время установки Windows 11 нажмите комбинацию клавиш Shift+F10, чтобы открыть командную строку. Введите. . .
|
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
|
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM
Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой.
Но использовать несколько программ не удобно. Искал другие. . .
|
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской)
Options
Preferences
General
Language
|
|
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент".
В данной функции нет апострофов,. . .
|
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы.
Карта этого меню приложена ниже.
Нужный пункт выделен красным.
Сервис
Настройки
Поведение
|
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки.
Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён".
Изменено отображение буквы Й.
Добавлена. . .
|
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки.
Добавлено:
- Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
|