0

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

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

我的实现有效，但是我想向您询问有关动态内存分配的建议。

其中一些数据结构使用动态数组（实际上是原始指针）来存储元素，当满时自动增长并在某个负载因子阈值下收缩（分别将其大小加倍和减半）。为了简单起见（也因为我不应该使用它们），我没有使用任何“现代东西”，例如智能指针或移动构造函数/运算符 =，基本上我依赖于 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;
}
4

2 回答 2

1

不，你仍然不需要newand 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循环。

于 2018-10-26T15:49:55.850 回答
0

new我相信，对于这个项目，使用and确实是合适的delete；我的数据结构老师使用了完全相同的内存分配方式。看起来，人们不赞成使用分配的内存的一般原因是它很难正确管理。记住delete您不再使用的所有内存非常重要——不要手上有任何孤立的 RAM！

于 2018-10-26T15:20:54.603 回答