Правильный способ выделить память для моего собственного массива на основе указателей в C ++

Question

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

Я студент факультета компьютерных наук, в настоящее время изучаю алгоритмы и структуры данных.Для моего экзамена мне пришлось реализовать набор шаблонизированных структур данных в C ++.Мне не разрешили использовать STL, так как это был экзаменационный вопрос о том, как реализовать библиотеку, подобную STL.

Моя реализация работает, однако я хотел бы попросить вас совета о динамическом распределении памяти.

Некоторые из этих структур данных используют динамический массив (фактически необработанный указатель) для хранения элементов, который автоматически увеличивается при заполнении и сжимается при определенном пороговом значении коэффициента загрузки (удваивая и уменьшая вдвое его размер соответственно).Для простоты (а также потому, что я не должен их использовать), я не использовал никаких «современных вещей», таких как умные указатели или move constructor / operator =, и в основном я полагался на C ++ 98функции.Я использовал new [] и delete [] , но везде читал, что это плохая практика.

Мой вопрос: как правильно обращаться?динамическое распределение памяти для структур данных на основе массива в C ++?

Вот пример того, что я сделал (массив был ранее выделен новым []):

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;
}

Answer 1

Нет, вам все еще не нужны 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 цикла.

Answer 2

Я считаю, что для этого проекта действительно целесообразно использовать new и delete;мой учитель Data Structures использует тот же стиль распределения памяти.По-видимому, общая причина, по которой люди не одобряют использование выделенной памяти, заключается в том, что с ней может быть трудно правильно обращаться.Просто важно помнить delete всю память, которой вы больше не пользуетесь - не хотите иметь потерянную оперативную память на руках!