我正在尝试为我的数据结构和算法课程实现动态数组数据结构,但我认为我在内存管理方面遇到了一些麻烦。我的模板类如下。
ArrayList.h
#include <iostream>
#include <cstring>
using namespace std;
#define Length(array) (sizeof((array))/sizeof((array[0])))
template <class T>
class ArrayList
{
public:
ArrayList() {a = new T[1]; n = 0;}
~ArrayList() {delete [] a;}
int size();
int backingSize();
T get(int i);
T set(int i, T x);
void add(int i, T x);
T remove (int i);
private:
void resize();
T *a;
int n;
};
template <class T>
int ArrayList<T>::size() { return n; }
template <class T>
int ArrayList<T>::backingSize() { return Length(a); }
template <class T>
T ArrayList<T>::get(int i) { return a[i]; }
template <class T>
T ArrayList<T>::set(int i, T x)
{
T temp = a[i];
a[i] = x;
return temp;
}
template <class T>
void ArrayList<T>::add(int i, T x)
{
if (n+1 > Length(a)) resize();
for (int j = n; j > i; j--) a[j] = a[j-1];
a[i] = x;
n++;
}
template <class T>
T ArrayList<T>::remove(int i)
{
T temp = a[i];
for (int j = i; j < n-1; j++) a[j] = a[j+1];
n--;
if (Length(a) > 3*n) resize();
return temp;
}
template <class T>
void ArrayList<T>::resize()
{
if ( n+1 > Length(a))
{
cout << "Making Biggern";
T* tempArr = new T[2*n];
memcpy(tempArr, a, n * sizeof(T));
delete [] a;
a = tempArr;
}
else // (Length(a) > 3*n)
{
cout << "Making Smallern";
T* tempArr = new T[n/2];
memcpy(tempArr, a, n * sizeof(T));
delete [] a;
a = tempArr;
}
}
然后我使用以下主要函数对其进行测试
TestArrayList.cpp
#include "ArrayList.h"
#include <iostream>
using namespace std;
int main()
{
ArrayList <int> myList;
cout << myList.size() << "nn";
myList.add(0,15);
cout << myList.get(0) << ", " << myList.size() << ", " << myList.backingSize() << "n";
myList.add(1,34);
cout << myList.get(1) << ", " << myList.size() << ", " << myList.backingSize() << "n";
myList.add(2,23);
cout << myList.get(2) << ", " << myList.size() << ", " << myList.backingSize() << "n";
myList.add(3,1);
cout << myList.get(3) << ", " << myList.size() << ", " << myList.backingSize() << "nn";
myList.~ArrayList();
}
代码编译并运行,并输出到终端:
15, 1, 2
34, 2, 2
Making Bigger
23, 3, 2
Making Bigger
1, 4, 2
*** Error in `./TestArrayList': double free or corruption (fasttop): 0x000000000090c010 ***
Aborted
它似乎按预期工作,get 函数在其索引处返回正确的值,size 函数返回数组的正确长度,并且没有 seg 错误。但是,backingSize()
函数总是返回 2,并且我认为最后抛出的错误与糟糕的内存管理有关。我已经难倒了一段时间,所以任何帮助将不胜感激。
显式调用对象的析构函数。析构函数是自动调用的,因此由于您已经调用了它,因此会发生双重释放错误。
若要了解何时调用析构函数,请查看此链接
这是一个错误(不确定是否没有其他错误):
T* tempArr = new T[n / 2]; // the size is n / 2
memcpy(tempArr, a, n * sizeof(T)); // but here you try to copy n elements
tempArr
只能保存n / 2
元素,但您尝试将n
元素复制到其中。这是未定义的行为。此外,对于所有可能的类型T
逐字节复制元素是不可行的。
你永远不应该在指针上使用#define Length(array) (sizeof((array))/sizeof((array[0])))
。 无法从指针中知道数组的大小。 这可能会导致您的问题。 既然你有一个类,为什么不把大小和容量存储为变量呢? 在处理数组类型对象时,内存中占用的 8 个字节的大小和容量实际上不算什么。