在 C++ 中为我自己的基于指针的数组分配内存的正确方法

Question

我搜索过类似的问题，但找不到满足我需求的问题。

我是一名计算机科学专业的学生，目前正在学习算法和数据结构。为了考试，我必须用 C++ 实现一组模板化数据结构。我不被允许使用 STL，因为这是一道关于如何实现类似于 STL 的库的考试问题。

我的实现有效，但是我想请您提供有关动态内存分配的建议。

其中一些数据结构使用动态数组（实际上是原始指针）来存储元素，元素在满时自动增长并在特定负载因子阈值下收缩（分别将其大小加倍和减半）。为了简单起见（也因为我不应该使用它们），我没有使用任何"modern stuff"，比如智能指针或移动constructor/operator=，基本上我依赖于C ++98 个功能。我使用了 new [ ] 和 delete [ ]，但我到处都读到这是一种不好的做法。

我的问题是：在 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;
}

Answer 1

我认为，对于这个项目，使用new和delete确实是合适的；我的数据结构老师使用完全相同的内存分配方式。看起来，人们不赞成使用分配内存的普遍原因是难以正确管理。重要的是要记住 delete 您不再使用的所有内存 -- 不要让任何孤立的 RAM 留在您的手上！

Answer 2

不，您仍然不需要 new 和 delete。在 C++ 中仍然使用 new 的唯一原因是执行聚合初始化，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 循环。

在 C++ 中为我自己的基于指针的数组分配内存的正确方法

Proper way to allocate memory for my own pointer-based array in c++

c++

new-operator

dynamic-memory-allocation

data-structures

raw-pointer