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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
TpukcTep
0 / 0 / 0
Регистрация: 18.06.2013
Сообщений: 13
#1

Стратегии динамич. увеличения длины массива - C++

13.07.2013, 14:48. Просмотров 470. Ответов 8
Метки нет (Все метки)

Помогите пожалуйста.
Нужно реализовать динамическую структуру данных на основе расширяемого массива.
С программой проблем нет, но в задании сказано: "Предложить различные стратегии динамического увеличения массива".
Я поступаю так: когда массив переполняется, создаю массив в 2 раза больше и копирую туда переполненный массив, удаляя его.
Но других вариантов не могу придумать. Прошу подсказать ещё какие нибудь стратегии.
(По заданию запрещено использовать библиотеку STL, так что использование Vector не прокатит).
Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.07.2013, 14:48     Стратегии динамич. увеличения длины массива
Посмотрите здесь:

C++ обращение к динамич массиву
C++ Вывести все слова входного потока в порядке увеличения их длины
C++ Ограничение длины массива
Массив: Найти номера двух ближайших по значению элементов из этого массива и вывести их в порядке увеличения C++
Стратегии обслуживания жесткого диска C++
C++ Добавление элемента в динамич. структуру , ошибка с 1 элементом
C++ Заданы два массива, new-delete, динамич. обл. памяти
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gray_fox
What a waste!
1256 / 1139 / 55
Регистрация: 21.04.2012
Сообщений: 2,361
Завершенные тесты: 3
13.07.2013, 14:51     Стратегии динамич. увеличения длины массива #2
Цитата Сообщение от TpukcTep Посмотреть сообщение
в 2 раза больше
Ну можно просто другой множитель взять)

Добавлено через 1 минуту
Или увеличавть каждый раз при переаллокации на фиксированное количество...
Croessmah
Модератор
Эксперт CЭксперт С++
12882 / 7268 / 810
Регистрация: 27.09.2012
Сообщений: 17,959
Записей в блоге: 2
Завершенные тесты: 1
13.07.2013, 14:53     Стратегии динамич. увеличения длины массива #3
Например, можно сделать изначальный множитель 2, который будет уменьшаться, например, до 1.5, по мере увеличения массива
lowercase
212 / 201 / 34
Регистрация: 09.05.2012
Сообщений: 494
13.07.2013, 14:55     Стратегии динамич. увеличения длины массива #4
Здавать процент приащения размера. Например передали 0.15f в конструктор, а дальше кадый раз когда будет нехватка памяти - увеличить масив на 15% процентов. Такой подход реализирован в некотроых коллекциях в языке Java.
Dani
1272 / 630 / 54
Регистрация: 11.08.2011
Сообщений: 2,267
Записей в блоге: 2
Завершенные тесты: 1
13.07.2013, 15:04     Стратегии динамич. увеличения длины массива #5
TpukcTep, можно сделать списком - хранить указатель на следующий элемент и правильно организовать доступ к элементам.
TpukcTep
0 / 0 / 0
Регистрация: 18.06.2013
Сообщений: 13
13.07.2013, 15:09  [ТС]     Стратегии динамич. увеличения длины массива #6
А какой подход будет лучше?

Добавлено через 2 минуты
Dani, а это уже вторая часть задания) Реализовать ту же программу с теми же операциями на основе двусвязного списка и провести сравниельный анализ этих двух реализации)
Dani
13.07.2013, 15:11
  #7

Не по теме:

проснулись все-таки во мне экстрасенсорные способности

Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
13.07.2013, 21:19     Стратегии динамич. увеличения длины массива #8
Цитата Сообщение от TpukcTep Посмотреть сообщение
создаю массив в 2 раза больше и копирую туда переполненный массив, удаляя его.
И все указатели на элементы улетают в трубу?

можно хранить в памяти слайсами. Когда нужно выделить дополнительную память, выделяется необходимый блок без перемещения информации. Вспомогательные переменные хранят начало каждого слайса и количество элементов в нём.
Но всё это "пальцем в небо", если нет критериев на ваш рассширяемый_массив (например, должна ли быть возможность вставлять элемент в произвольной позиции?)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.07.2013, 21:47     Стратегии динамич. увеличения длины массива
Еще ссылки по теме:

C++ Определение длины одномерного массива
C++ Вычисление длины массива
C++ Не могу разобраться как сделать указатель функции с динамич. массивом
C++ Из элементов массива А длины 2N получить массивы В и С длины N указанным способом
Два динамич. массива, размер увеличивается+1. MSVS ошибка C++

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

Или воспользуйтесь поиском по форуму:
Убежденный
Системный программист
Эксперт С++
15103 / 6798 / 1073
Регистрация: 02.05.2013
Сообщений: 11,111
Завершенные тесты: 1
13.07.2013, 21:47     Стратегии динамич. увеличения длины массива #9
Цитата Сообщение от TpukcTep Посмотреть сообщение
С программой проблем нет, но в задании сказано: "Предложить различные стратегии динамического увеличения массива".
Я поступаю так: когда массив переполняется, создаю массив в 2 раза больше и копирую туда переполненный массив, удаляя его.
Но других вариантов не могу придумать. Прошу подсказать ещё какие нибудь стратегии.
Вынести стратегию перераспределения памяти в интерфейс класса.
Например, как шаблонный параметр или как параметр конструктора.
При этом предоставить значение по умолчанию, подходящее в "общем" случае.
Yandex
Объявления
13.07.2013, 21:47     Стратегии динамич. увеличения длины массива
Ответ Создать тему
Опции темы

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