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

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

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

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

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

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

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

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

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

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

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

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

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

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

Добавлено через 1 минуту
Или увеличавть каждый раз при переаллокации на фиксированное количество...
Croessmah
Модератор
Эксперт CЭксперт С++
13063 / 7326 / 817
Регистрация: 27.09.2012
Сообщений: 18,085
Записей в блоге: 3
Завершенные тесты: 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
1300 / 637 / 56
Регистрация: 11.08.2011
Сообщений: 2,280
Записей в блоге: 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++
int* mass(int p, int n) { cout << "Введите размер массива: "; cin>>n; int *p = new int ; for (int i(0); i < n; i ++) { cout <<...

Ограничение длины массива - C++
В общем сейчас читаю книгу, и решил сделать небольшую свою программу, мне нужен длинный char массив, пытаюсь сделать его так: char str; ...

Вычисление длины массива - C++
Есть такой код: #include <iostream> #ifndef SORT_H #define SORT_H void isort(int a){ int length =...

Стратегии обслуживания жесткого диска - C++
Здравствуйте, пробую разобраться с темой обслуживания на примере стратегии N-SCAN; нашел для примера код, но в нем есть не совсем...

Ввод массива неизвестной длины - C++
Добрый день! Уважаемые знатоки, вопрос скорее всего тривиальный, но тем не менее решения у меня нет. Нужно задать вектор через пробелы...


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

Или воспользуйтесь поиском по форуму:
Убежденный
Системный программист
Эксперт С++
15298 / 6930 / 1096
Регистрация: 02.05.2013
Сообщений: 11,341
Завершенные тесты: 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