Как изменить размер динамического массива

Реализация шаблона класса “Динамический массив”

Рассмотрим реализацию класса dynamic_array — динамический массив, то есть массив, размер которого может изменяться.

Реализация класса представляет собой шаблон, параметром шаблона является тип хранимых в массиве элементов.

Закрытые поля класса:

m_size — размер массива (количество элементов в массиве, доступных пользователю).

m_capacity — «вместимость» массива, то есть размер выделенной памяти для хранения элементов. При увеличении размера массива если новый размер не превосходит m_capacity, то новые элементы можно создать в массиве без выделения дополнительной памяти.

m_data — указатель на область памяти, где хранятся сами элементы массива.

Конструкторы и деструкторы

Конструктор по умолчанию создает пустой массив, не содержащий элементов.

public:
dynamic_array()
m_size = 0;
m_capacity = 0;
m_data = NULL;
>

Копи-конструктор создает копию существующего массива. Он нужен для того, чтобы при создании копии массива выделить новую память для хранения данных копии массива и скопировать туда все элементы. Если не сделать копи-конструктор, то при создании копии массива поле m_data у копии будет указывать на ту же область памяти, что и у исходного массива. Поэтому если в классе используется динамическое распределение памяти, то всегда необходимо создавать копи-конструктор.

Конструктор, который создает массив заданного размера.

Деструктор необходим для того, чтобы освободить выделенную память при удалении объекта.

dynamic_array()
if (m_data)
delete[] m_data;
>

Изменение размера массива

Метод resize изменяет размер массива, новый размер передается параметром size . Если значение size не превосходит значения m_capacity , то этот метод только изменяет значение поля m_size , иначе необходимо перевыделить память — выделяется новая область памяти для хранения элементов, существующие элементы массива копируются из старой области памяти в новую, выделенная ранее память освобождается.

Для того, чтобы память не выделялась слишком часто, размер выделенной памяти удваивается по сравнению со старым размером массива.

Метод push_back добавляет один новый элемент в конец массива.

void push_back(T val)
resize(m_size + 1);
m_data[m_size — 1] = val;
>

Метод size возвращает размер массива.

Доступ к элементам массива

Доступ к элементам массива перегрузим оператор [] . Это позволит обращаться к элементам класса dynamic_array так же, как к элементам обычного массива: a[i] .

Перегрузка оператора вывода

Для вывода массива перегрузим оператор << . Это необходимо сделать отдельной функцией после реализации класса dynamic_array .

Array. Resize<T>(T[], Int32) Метод

Некоторые сведения относятся к предварительной версии продукта, в которую до выпуска могут быть внесены существенные изменения. Майкрософт не предоставляет никаких гарантий, явных или подразумеваемых, относительно приведенных здесь сведений.

Изменяет количество элементов в одномерном массиве до указанной величины.

Параметры типа

Тип элементов массива.

Параметры

Подлежащий изменению размера одномерный массив, индексация которого начинается с нуля, или значение null для создания нового массива заданного размера.

Размер нового массива.

Исключения

Значение параметра newSize меньше нуля.

Примеры

В следующем примере показано, как изменение размера влияет на массив.

Комментарии

Этот метод выделяет новый массив с указанным размером, копирует элементы из старого массива в новый, а затем заменяет старый массив новым. array должен быть одномерным массивом.

Если array это так null , этот метод создает новый массив с указанным размером.

Length Если newSize больше старого массива, выделяется новый массив, а все элементы копируются из старого массива в новый. Если newSize значение меньше Length старого массива, выделяется новый массив, а элементы копируются из старого массива в новый, пока не будет заполнен новый, остальные элементы старого массива игнорируются. Если newSize значение равно Length старому массиву, этот метод ничего не делает.

Этот метод является операцией O( n ), где n находится newSize .

Метод Resize изменяет размер только одномерного массива. Класс Array не включает метод изменения размера многомерных массивов. Для этого необходимо предоставить собственный код или вызвать специальный метод в сторонней библиотеке. Следующий код иллюстрирует одну возможную реализацию метода, который изменяет размер массива n измерений.

Как правильнее изменять размер массива в С++?

Я не знаю, как работает realloc, но мне кажется, что явно быстрее сочетания «выделить новое место требуемого размера и скопировать в него старый массив, а потом его еще и удалить». Это правда или проще сделать realloc и переприсвоить указатели?

P.S. Именно для языка С++, то есть учитывать всю философию и т. д. Или насрать?

Именно для языка С++, то есть учитывать всю философию и т. д.

Ну а для массивов?

std::vector, не стоит думать, потом поймешь.

realloc, vector внутри так и делает

вектор — это такой контейнер, который выделяет непрерывные куски памяти. так что, под массив покатит. почитай матчасть.

Использовать вместо массивов std::vector, очевидно же.

У тебя что за задача? Эффективный менеджер памяти писать или что-то более высокого уровня? Нечего забивать себе голову такими вещами, если это высокоуровневая задача.

Если же менеджер памяти, то выделяй пул памяти и менеджи руками.

Это просто я решил посмотреть лыба из следующего года. Там надо велосипедить всякие стеки, очереди и т. д. на плюсах. Если бы был Си, вопрос бы не встал. Но преподы такие преподы — если просто #include <stack>, это явно не прокатит, если #include <vector> и держать вектор внутри велосипедного стека, это тоже не прокатывает — типа слишком просто. А вот С++ и средства Си — это нормально. Я думаю, можно и на Си, наверное, просто. Так будет даже как-то целостнее. Хотя велосипеды велосипедить — это какое-то зло(

Хотя я год назад писал свой вело-клон vector. Там как раз realloc с placement new и зайчатками шаблонной магии.

Я теоретически интересуюсь.

The realloc() function changes the size of the memory block pointed to by ptr to size bytes. The contents will be unchanged in the range from the start of the region up to the minimum of the old and new sizes.

Хочешь посмотреть, как надо, посмотри как сделан std::vector.

realloc может облажаться с выделением непрерывного куска, выделить его где-то ещё и скопировать старые данные туда, убив старый указатель. Именно поэтому она возвращает указатель на расширенный кусок памяти и использовать надо именно его.

Вот скажи, это как понимать? Можно мне просто #inlude <stack>?

З використанням бібліотеки стандартних шаблонів STL (Standard Template Library) реалізувати:

1. Стек.

2. Чергу.

Забей ты на эти лабы, что как маленький.

Если речь не идёт о расчёте разлёта осколков после подрыва ЯВУ, то на современных машинах он не ошибается. И, если я не ошибаюсь, кусок не обязательно будет непрерывным. Хотя, с точки зрения приложения будет.

Вот и спросишь у преподавателя. А то мало ли, может они не в курсе, что в STL есть и стеки, и очереди, а не только один vector и list.

А какие варианты? Просто не сдать лабы? Отмазаться «доколе будем переписывать STL?!»? Если есть реальные варианты, я бы сделал)

Ну, действительно не знаю. У меня были мысли, что правильный realloc подшаманивает с таблицей виртуальной памяти и оно именно так и выходит: всегда непрерывно. Может и так; но мне это почему-то казалось неэффективным: типа что ж это такое, целая +1 косвенная адресация воще ко всему.

Vector containers are implemented as dynamic arrays; Just as regular arrays, vector containers have their elements stored in contiguous storage locations, which means that their elements can be accessed not only using iterators but also using offsets on regular pointers to elements.

посмотрел bits/vector. Это же какое-то нечитабельное что-то! Да здравствует инкапсуляция!

Хз, как они это сделали, но в мане пишут безальтернативно:

А потом идут пространные рассуждения, что будет, если память кончится.

И причём тут stl?

Ну вообще-то, в __учебной__ практике написание своей упрощённой реализации кусочка STL — это нормально.

А то можно вообще спросить, зачем изучать классичесские алгоритмы типа пузырьковой сортировки — они, внезапно в библиотеках тоже имеются.

Хотя, я тут подумал. Страницы ж размером по 4 килобайта или типа того. И расходы использование виртуальной памяти всегда есть. То есть последствия облажавшегося реаллока — это максимум копирование одной неполной страницы в другое место; а это уж подавно лучше, чем всегда копировать весь массив.

действительно..
просто выше шла дискуссия про стл 😉

Ну то unchaged — это ж про содержимое. Типа, realloc не загадит вам то, что уже хранилось в массиве.

Насколько я помню, все эти стеки/очереди требовалось реализовать на основе структуры:

struct foo datatype data;
foo* next;
>

Но это было лет 7 назад.

Там как раз пишут про новую память:

the added memory will not be initialized

А про старую ничего не пишут. Вообще. Думаю, если они предупреждают, что не инициализированная память не будет инициализирована, то уж о перемещениях написали бы.

О перемещениях чуть ниже:

If the area pointed to was moved, a free(ptr) is done.
.
If realloc() fails the original block is left untouched; it is not freed or moved.

The realloc() function returns a pointer to the newly allocated memory, which is suitably aligned for any kind of variable and may be different from ptr,

Т.е. редко, но бывает.

Ну а как мне реализовать стек стредствами STL? Где предел дозволенного? Что можно включать, а что нельзя уже?

Пойду поставлю в TODO: таки прочитать главу о менеджменте памяти из «Структур данных и алгоритмов» Ахо, Ульмана и Хопкрофта.

Это где? У нас такого не предъявляют. Наоборот — сказано реализовать как массив и как список. Это что, можно включить вектор и лист и все?

Ты всерьёз думаешь, что тут могут сделать astral <<EOF Какие тараканы у преподавателей cdshines и что ему позволят использовать из STL? EOF ?

Это риторический вопрос, который призывает всех вместе покачать головой и сказать «ндо, тупое какое-то задание».

Вот так и скажешь преподавательскому составу. И приведёшь пример хорошего задания. Уверен, скажут спасибо.

А вообще, не забивай сейчас голову. Тебе успеют накидать требований.

Я думаю, надо плотнее общаться с преподавательским составом.

Учебная программа всё-таки рассчитана бОльшей частью на тех, для кого STL — вообще ругательное слово. И я думаю, что если нормальный преподаватель видит студента, который явно знает больше среднего, он пойдёт навстречу. По крайней мере, расскажет про те самые границы.

не осилил магию шаблонов?

В c++ нет realloc, потому что бывают нетривиальные (не побайтовые) операторы присваивания/копирования. Из-за этого существуют классы, для которых результат a = b не равен результату memcpy(&a, &b, sizeof(a)). realloc делает именно memcpy без знания о том, что хранится по этому адресу, из-за чего не имеет смысла в си++. Для new[]/delete[] нет чего-то вроде realloc[], так как он был бы очень опасной операцией с точки зрения исключений (привет отсутствию прямого запрета на кидание в деструкторе), а написать один цикл с учётом текущей стратегии безопасности обычно не составляет никакого труда.

В моем ВУЗе процветал Delphi и делали мы все это на самописных списках. На самом деле не лишним будет поинтересоваться лично у преподавателя, что конкретно он от вас хочет.

Хотя я год назад писал свой вело-клон vector. Там как раз realloc с placement new и зайчатками шаблонной магии.

шаблонная магия была как раз для написания is_pod<T>, чтобы делать realloc для всяких интов, и феерию деструкторов и конструкторов для объектов; а то преподаватель жаловался, что это «не эффективно всё копировать». Таки убедил его, что с объектами realloc не прокатит.