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

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

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

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

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

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

Вывести все слова входного потока в порядке увеличения их длины - C++
Здравствуйте . Задание: Вывести все слова входного потока в порядке увеличения их длины . Надеюсь на вашу помощь. Задание желательно...

Заданы два массива, new-delete, динамич. обл. памяти - C++
Помогите решить задачу с учетом этого : Массивы создаются в динамической области памяти с использованием операций NEW и DELETE. Ввод...

Два динамич. массива, размер увеличивается+1. MSVS ошибка - C++
полдня ломаю голову, не могу понять что не так и где что выходит, посмотрите, пожалуйста. Хуже то, что Code::Blocks работает, а VS2015...

Из элементов массива А длины 2N получить массивы В и С длины N указанным способом - C++
Из элементов массива А длины 2N получить массивы В и С длины N каждый следующим образом. Выбрать в массиве А два наиболее близких по...

Можно ли использовать memcpy для увеличения размера динамического массива? - C++
char *x = "asdsadasdasdasdasdasdasdasdasd"; char *t = new char; memcpy(t, x, 12); t = '\0'; printf("%s", t);Компилятор не...

Массив: Найти номера двух ближайших по значению элементов из этого массива и вывести их в порядке увеличения - C++
День добрый! Может ли кто-нибудь помоч решить задачу? Дан массив размера N. Найти номера двух ближайших по значению элементов из этого...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
gray_fox
What a waste!
1520 / 1223 / 70
Регистрация: 21.04.2012
Сообщений: 2,560
Завершенные тесты: 3
13.07.2013, 14:51 #2
Цитата Сообщение от TpukcTep Посмотреть сообщение
в 2 раза больше
Ну можно просто другой множитель взять)

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

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

Не по теме:

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

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

можно хранить в памяти слайсами. Когда нужно выделить дополнительную память, выделяется необходимый блок без перемещения информации. Вспомогательные переменные хранят начало каждого слайса и количество элементов в нём.
Но всё это "пальцем в небо", если нет критериев на ваш рассширяемый_массив (например, должна ли быть возможность вставлять элемент в произвольной позиции?)
0
Убежденный
Системный программист
Эксперт С++
15547 / 7055 / 1114
Регистрация: 02.05.2013
Сообщений: 11,467
Завершенные тесты: 1
13.07.2013, 21:47 #9
Цитата Сообщение от TpukcTep Посмотреть сообщение
С программой проблем нет, но в задании сказано: "Предложить различные стратегии динамического увеличения массива".
Я поступаю так: когда массив переполняется, создаю массив в 2 раза больше и копирую туда переполненный массив, удаляя его.
Но других вариантов не могу придумать. Прошу подсказать ещё какие нибудь стратегии.
Вынести стратегию перераспределения памяти в интерфейс класса.
Например, как шаблонный параметр или как параметр конструктора.
При этом предоставить значение по умолчанию, подходящее в "общем" случае.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.07.2013, 21:47
Привет! Вот еще темы с ответами:

обращение к динамич массиву - C++
Задание:Дана целочисленная квадратная матрица. Определить сумму элементов в тех строках, которые не содержат отрицательных...

Открытые функции класса: ввод массива, вывод массива, определение длины вектора - C++
Данные класса: массив N(10). Открытые функции класса: ввод массива, вывод массива, определение длины вектора. Длина массива определяется...

Добавление элемента в динамич. структуру , ошибка с 1 элементом - C++
Задание сформировать карточки для пациентов путем добавления в массив структур .Возникла ошибка , при добавление второго и последущих новых...

Не могу разобраться как сделать указатель функции с динамич. массивом - C++
int* mass(int p, int n) { cout << "Введите размер массива: "; cin>>n; int *p = new int ; for (int i(0); i < n; i ++) { cout <<...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
13.07.2013, 21:47
Ответ Создать тему
Опции темы

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