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

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

Восстановить пароль Регистрация
 
TpukcTep
0 / 0 / 0
Регистрация: 18.06.2013
Сообщений: 13
13.07.2013, 14:48     Стратегии динамич. увеличения длины массива #1
Помогите пожалуйста.
Нужно реализовать динамическую структуру данных на основе расширяемого массива.
С программой проблем нет, но в задании сказано: "Предложить различные стратегии динамического увеличения массива".
Я поступаю так: когда массив переполняется, создаю массив в 2 раза больше и копирую туда переполненный массив, удаляя его.
Но других вариантов не могу придумать. Прошу подсказать ещё какие нибудь стратегии.
(По заданию запрещено использовать библиотеку STL, так что использование Vector не прокатит).
Заранее спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
13.07.2013, 14:51     Стратегии динамич. увеличения длины массива #2
Цитата Сообщение от TpukcTep Посмотреть сообщение
в 2 раза больше
Ну можно просто другой множитель взять)

Добавлено через 1 минуту
Или увеличавть каждый раз при переаллокации на фиксированное количество...
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,920
Записей в блоге: 2
Завершенные тесты: 1
13.07.2013, 14:53     Стратегии динамич. увеличения длины массива #3
Например, можно сделать изначальный множитель 2, который будет уменьшаться, например, до 1.5, по мере увеличения массива
lowercase
 Аватар для lowercase
211 / 200 / 34
Регистрация: 09.05.2012
Сообщений: 494
13.07.2013, 14:55     Стратегии динамич. увеличения длины массива #4
Здавать процент приащения размера. Например передали 0.15f в конструктор, а дальше кадый раз когда будет нехватка памяти - увеличить масив на 15% процентов. Такой подход реализирован в некотроых коллекциях в языке Java.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 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++ Заданы два массива, new-delete, динамич. обл. памяти
C++ Вычисление длины массива
C++ Ввод массива неизвестной длины

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

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

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