структуры данных — правильный способ выделить память для моего собственного массива на основе указателей в переполнении стека
Я искал похожие вопросы, но не смог найти удовлетворительных для своих нужд.
Я студент информатики в настоящее время изучаю алгоритмы и структуры данных. Для моего экзамена мне пришлось реализовать набор шаблонизированных структур данных в C ++. Мне не разрешили использовать STL, так как это был экзаменационный вопрос о том, как реализовать библиотеку, похожую на STL.
Моя реализация работает, однако я хотел бы попросить вас совета о динамическом распределении памяти.
Некоторые из этих структур данных используют динамический массив (фактически необработанный указатель) для хранения элементов, который автоматически увеличивается при заполнении и сжимается при определенном пороговом значении коэффициента загрузки (удваивая и удваивая его размер соответственно). Для простоты (а также потому, что я не должен их использовать), я не использовал никаких «современных вещей», таких как умные указатели или move constructor / operator =, и в основном я полагался на C ++ 98 функции. я использовал новый [] а также удалять [ ], но я везде читал, что это плохая практика.
Мой вопрос: как правильно обрабатывать динамическое распределение памяти для структур данных на основе массива в C ++?
Вот пример того, что я сделал (массив был ранее выделен new []):
template <typename T>
void ArrayList<T>::pushBack(T item)
{
if (size < capacity) { // if there's room in the array
array[size] = item; // simply add the new item
} else { // otherwise allocate a bigger array
capacity *= 2;
T *temp = new T[capacity];
// copy elements from the old array to the new one
for (int i = 0; i < size; ++i)
temp[i] = array[i];
delete [] array;
temp[size] = item;
array = temp;
}
++size;
}
Решение
Нет, тебе все еще не нужно new а также delete, Единственная причина по-прежнему использовать new в C ++ выполнить агрегатную инициализацию, которая std::make_unique не поддерживает, и вам никогда не нужно delete совсем.
Ваш пример кода становится:
template <typename T>
void ArrayList<T>::pushBack(T item)
{
if (size < capacity) { // if there's room in the array
array[size] = item; // simply add the new item
} else { // otherwise allocate a bigger array
capacity *= 2;
auto temp = std::make_unique<T[]>(capacity);
// copy elements from the old array to the new one
for (int i = 0; i < size; ++i)
temp[i] = array[i];
temp[size] = item;
array = std::move(temp);
}
++size;
}
Который также может быть учтен путем замены двух разделов:
template <typename T>
void ArrayList<T>::pushBack(T item)
{
if (size >= capacity) { // if there's no room in the array, reallocate
capacity *= 2;
auto temp = std::make_unique<T[]>(capacity);
// copy elements from the old array to the new one
for (int i = 0; i < size; ++i)
temp[i] = array[i];
temp[size] = item;
array = std::move(temp);
}
array[size] = item; // simply add the new item
++size;
}
Дальнейшие возможные улучшения: перемещайте элементы при перераспределении вместо их копирования, используйте стандартный алгоритм вместо руководства for петля.
Другие решения
Я считаю, для этого проекта, что это действительно правильно использовать new а также delete; мой учитель Data Structures использует тот же стиль распределения памяти. По-видимому, общая причина, по которой люди не одобряют использование выделенной памяти, заключается в том, что с ней может быть трудно правильно обращаться. Это просто важно помнить delete вся память, которой вы больше не пользуетесь — не хотите иметь потерянную оперативную память на руках!