动态数组与数组相似，但是动态数组的大小可以在运行时动态修改。动态数组的元素占用连续的内存块，一旦创建，就无法更改其大小。 一旦被填充，就可以分配更大的内存块，将内容从原始数组复制到该新空间，然后继续填充可用的插槽。在后端，动态数组在创建时会分配预定数量的内存，然后在需要时以一定的比例增长。 这些参数，初始大小和增长因子在性能方面至关重要。 如果初始大小和增长因素较小，那么您最终将不得不经常重新分配内存，这不好； 另一方面，如果它们的值较高，则可能会有大量未使用的内存，并且调整大小操作可能需要更长的时间。 这里的权衡是非常重要的。
常用语言中的动态数组的示例包括Java和C＃中的ArrayList，C ++中的Vector，.NET中的List <>，Python的列表等。
实现
C语言编写一个动态整数数组,但要兼容不同的基本数据类型,你可能要需要编写较为复杂宏函数来模拟C++泛型相同的效果。因此C++本身已经集成了模板和垃圾回收机制,以模板为基础的泛型技术可以很轻松地编写出管理任何类型和内存回收很好的动态数组-v-!!，首先我们定义了动态数组的类接口。
#define MIN_CAPACITY 10
#define INCREASE_PROG 2
template <class T>
class SequenceList
{
//实质存储元素的连续内存块
T *d_arr = nullptr;
//实时通过元素的个数
size_t d_length = 0;
//实时统计申请内存块的尺寸
size_t d_capacity = 0;
//闲置内存
size_t d_idles = 0;
public:
//顺序表的长度
size_t length;
//向堆申请内存的数量(以类型T的数据大小为单位)
size_t capacity;
//闲置内存块
size_t idles;
//默认构造函数
SequenceList();
/**
* 定义的默认构造函数
* @params T* 指向T类型的数组的指针
* @params size_t数组的尺寸大小
**/
SequenceList(T *, size_t);
SequenceList(T value);
~SequenceList();
//显示数组
void show_array();
//删除元素
void remove(T);
//在尾部插入元素
void push(T);
//弹出数据
T pop();
//判断数组是否为空
bool empty();
//在特定位置插入元素
void insert(size_t, T);
//清空表中所有元素
void clearn();
//下标操作府
T &operator[](int idx);
private:
//内存宽容
void expand();
};
构造函数的实现
我定义的顺序表这里仅提供两种构造函数初始化的实现.
- 默认的构造函数:初始化的时候即向堆申请MIN_CAPACITY的内存块。
- 定义的构造函数的实现
- 接受两个参数:指向T类型数组的指针和该数组的长度(非负数)
- 初始化的时候堆内存尺寸是传入参数n的2倍。
//默认构造函数
template <class T>
SequenceList<T>::SequenceList()
{
d_capacity = MIN_CAPACITY;
d_length = 0;
d_arr = new T[d_capacity];
capacity = d_capacity;
}
//定义的构造函数
template <class T>
SequenceList<T>::SequenceList(T *data, size_t n) : d_capacity(n * INCREASE_PROG), d_length(0)
{
capacity = d_capacity;
d_arr = new T[d_capacity];
for (size_t i = 0; i < n; i++)
{
*(d_arr + i) = *(data + i);
d_length++;
}
length = d_length;
}
析构函数的实现
显式定义构造函数是一个非常好的习惯,对于很多的内存回收的文章讲述的仅仅是delete[]操作释放堆内存,而没有将指向堆内存的T类型指针重置为nullptr，我认为这是一个很好的习惯，C风格中的回收内存的小技巧，这个是值的继承的。
//内存回收
template <class T>
SequenceList<T>::~SequenceList()
{
std::cout << "~SequenceList()调用.....!!" << std::endl;
if (d_length)
{
delete[] d_arr;
d_arr = nullptr;
}
}
核心成员函数
expand()是一个私有的内部成员函数,它内部完成了向内存池申请比现有内存更大的内存空间(是原有内存空间的2倍)，然后将原有内存空间中的元素拷贝到新的内存空间，最后将旧的内存空间释放返还给内存池。具体示意图如下：
expand成员函数的实现
//内部扩容操作
template <class T>
void SequenceList<T>::expand()
{
d_capacity = d_capacity * INCREASE_PROG;
T *tmp = new T[d_capacity];
for (size_t i = 0; i != d_length; i++)
{
*(tmp + i) = *(d_arr + i);
}
delete[] d_arr;
d_arr = tmp;
capacity = d_capacity;
}
重载operator [] (int)
我们希望顺序表是可以类似Python的list那样提供逆序访问的能力，比方说,对于一个长度为9的列表,我们通过下标 a[-1]等价于访问a[8]的元素，请参见如下图。
实现类似Python列表的访问能力非常简单,上图我们知道对应位置的顺序index(用m表示)和逆序index(用n表示)的绝对值的和等于该列表的长度(用length表示,始终是非负数)，我们得到如下简单的结论。
若 n<0且-length ≤ n < 0;
那么m=length+n,且0≤m≤length-1
即n的有效范围 可以 0≤n≤length-1 或 -length ≤n <0
实际上我们若提供一个的负整数n时,(-length ≤ n < 0)，最终会转换回顺序index的非负整数，那么operator[]的索引操作符重写如下。在重载operator[]的同时，我们需要面size_t类型的d_length转换为带符号的整数的问题，具体的问题描述可以看我之前写的随笔《C/C++ 有符号和无符号数字的迷途》
template <typename T>
inline T cvt_signed_number(size_t n)
{
if (n > static_cast<size_t>(std::numeric_limits<T>::max()))
{
throw std::overflow_error("参数n转换错误");
}
return static_cast<T>(n);
}
template <class T>
T &SequenceList<T>::operator[](int n)
{
int size = cvt_signed_number<int>(d_length);
if (n >= size || n < -size)
{
std::cout << "out of index!!" << std::endl;
exit(0);
}
if (n >= 0)
{
return *(d_arr + n);
}
else
{
return *(d_arr + d_length + n);
}
}
删除特定位值的元素
其实没什么好说的，删除中间位值的元素，实际上就是从传入索引位值算起，后续的元素依次将其元素值向各自的前一个元素拷贝并覆盖原先的元素值，拷贝过程结束后，d_length减1，原理图如下：
//删除特定的元素
template <class T>
void SequenceList<T>::remove(T value)
{
if (d_length > 0)
{
size_t k = 0;
for (size_t i = 0; i < d_length; i++)
{
if (value == d_arr[i])
{
k = i;
break;
}
}
for (size_t j = k; j < d_length; j++)
{
*(d_arr + k) = *(d_arr + k + 1);
}
*(d_arr+d_length)=0;
length = --d_length;
}
}
网友评论