「数组」实现动态数组的功能（C++）

概述

动态数组，顾名思议即可变长度的数组。数组这种数据结构的实现是在栈空间或堆空间申请一段连续的可操作区域。

实现可变长度的动态数组结构，应该有以下操作：申请一段足够长的空间，如果数据的存入导致空间已满，则申请一段更长的空间，将原有数据复制过去后加入新数据，同时释放原空间。

//栈空间（在栈上原地生成长度为len的数组空间）
int arr[len];//堆空间（在堆上申请长度为len的空间，获得首地址交给指针arr）
int *arr=new int[len];//在堆上实现动态数组
int *temp=new int[len*2];//申请更长的空间
strcpy(temp,arr,sizeof(int)*len)//strcpy以字节为单位将arr指向的数据复制到temp中
delete[]arr;//释放原空间
arr=temp;//temp赋值给arr

接下来我们通过封装array类,实现动态数组的一些基本功能。

成员变量

定义class类array，封装三个成员变量：T*val;int val_size;int val_capacity;

template <typename T>是泛型，作为数组这种数据结构，他的数据单位应该是任意一种类型（int，double，class等），template <typename T>的作用区域是它随后的一个{}内，意为T将代表某种类型，至于某种类型到底是那种类型，将在class实例化时告知（如arrar<double> arr,这句话的意思是创建一个储存double类型的动态数组类）

T* val表示指向array维护的存放数据的空间的指针val。

int val_size表示数组的当前存入内容的长度（数据长度）。

int val_capacity是数组的空间大小（真实长度）。

为什么维护了size和capacity两种长度？试想：每次申请长度都只是当前长度+1，则会在内存空间中反复向后利用函数申请新空间来维护数据，这同时耗费了时间和空间。

那么如果每次都申请真实长度size的两倍空间capacity，则每次申请后都有一段空闲区域容纳新元素，此时不需要申请新空间，只有当再次填满时才申请新空间，则减少了时间成本，提高了空间利用率。

template <typename T>
class array {
private:T* val;int val_size;int val_capacity;
public:...
}

创建销毁

我们提供五种构造函数（创建动态数组）和一个析构函数（销毁动态数组）。

无参构造：arary（），初始化val_size=0,val_capaciy=1(如果等于0的话，后续申请两倍capacity会失效),val=nullptr（空指针）。

（初始化列表array（）：成员变量（x），...{}在构造函数后加上：即为初始化列表，表示为成员变量赋为括号内的值x，而无须写入{}中）

提供初始空间的构造：array(int num)，表示申请初始空间为num的动态数组。

（断言assert(num>0)，定义在assert.h头文件中，在运行时会判断括号内的条件为真，否则抛错，保护程序运行的安全）

提供初始长度和初值的构造：array（int size,T target_val），为val指针申请两倍size的空间，利用for循环填充长度为size的初始值。

提供源数据地址的构造：array(T* begin, T* end)，从定长度数组中获取数据进行初始化，定义int size=end-begin（指针减法获得两指针的间隔长度（以指向的数据类型为单位））

（内存拷贝函数memcpy（指针1，指针2，以字节为单位的内存长度len），将指针2指向的长度为len的内容以字节为单位复制到指针1指向的空间）

拷贝构造：array(const array& another)，将another整体赋值给新array。

（const array&表示这个函数保证接受一个array类型的常量引用（即该array自身而非他的拷贝），常量const保证本函数不修改another）

析构函数：~array（）销毁数组释放空间，在主函数结束时自动调用，但在堆上申请的空间需要写入函数体否则无法释放。

array() : val_size(0), val_capacity(1), val(nullptr) {};//无参构造
array(int num) : val_size(0), val_capacity(num) {//提供初始空间的构造assert(num > 0);val = new T[num];
}
array(int size, T target_val) : val_size(size), val_capacity(size * 2) {//提供初始长度和初值的构造assert(size > 0);val = new T[size * 2];for (int i = 0; i < size; i++)val[i] = target_val;
}
array(T* begin, T* end) {//从固定长度数组中获取数据进行构造assert(begin != nullptr && end != nullptr);int size = end - begin;val = new T[size * 2];val_size = size;val_capacity = size * 2;memcpy(val, begin, sizeof(T)*size);
}
array(const array& another) {//拷贝构造val = new T[another.val_capacity];memcpy(val, another.val, sizeof(T) * another.val_size);val_size = another.val_size;val_capacity = another.val_capacity;
}
~array() {delete[]val;
}

整体赋值

作为class类，array应该同时拥有类的性质的数组的性质，那么他就应该可以被视为整体来进行操控。
我们提供三种整体赋值的函数。

重载等于号：const array& operator=(const array& another)，等于号作为一个的成员函数被我们重新定义，接收另一个array another的常量引用并整体赋值并返回一个自身的常量引用（这是为连等=...=...=...服务的）。

（this指针：返回这个array类的对象本身）

提供新长度和填充值的内存分配：void assign(int size, T target_val)，为array分配长度为size*2的空间，保留长度为size的数据，若size大于原长则新空间内填充target_val。

数据交换：void swap(array& another)，交换两个array的值。

const array& operator=(const array& another) {//重载等于号（这并不是构造，不能在初始化时使用）delete[]val;val = new T[another.val_capacity];memcpy(val, another.val, sizeof(T) * another.val_size);val_size = another.val_size;val_capacity = another.val_capacity;return *this;
}
void assign(int size, T target_val) {assert(size > 0);T* temp = new T[size * 2];for (int i = 0; i < size; i++)temp[i] = target_val;if (size < val_size)memcpy(temp, val, sizeof(T) * size);else memcpy(temp, val, sizeof(T) * val_size);delete[]val;val = temp;val_size = size;val_capacity = size * 2;
}
void swap(array& another) {array temp(another);*this = another;another = temp;
}

内存管理

我们提供四个size相关的函数和两个capacity相关的函数维护内存。

获取有效数据长度：int size()const，返回val_size。

（函数（）与{ }之间的const表示函数体内部不进行数据的更改操作）

判断有效空间是否为空：bool empty()const，返回val_size是否不等于0，是则false，否则true。

提供新长度的长度重置：void resize(int size)，与assign类似。

提供新长度和填充值的长度重置：void resize(int size, T target_val)，与assign类似。

获取实际空间长度：int capacity()const，返回val_capacity。

延长空间：void reserve(int num)，如果申请的新空间小于val_capacity，无事发生，否则申请更大的空间。

int size()const {return val_size;
}
bool empty()const {return val_size ? false : true;
}
void resize(int size) {assert(size > 0);T* temp = new T[size * 2];if (size < val_size)memcpy(temp, val, sizeof(T) * size);else memcpy(temp, val, sizeof(T) * val_size);delete[]val;val = temp;val_size = size;val_capacity = size * 2;
}
void resize(int size, T target_val) {assert(size > 0);T* temp = new T[size * 2];for (int i = 0; i < size; i++)temp[i] = target_val;if (size < val_size)memcpy(temp, val, sizeof(T) * size);else memcpy(temp, val, sizeof(T) * val_size);delete[]val;val = temp;val_size = size;val_capacity = size * 2;
}
int capacity()const {return val_capacity;
}
void reserve(int num) {if (num > val_capacity) {T* temp = new T[num];memcpy(temp, val, sizeof(T) * val_size);delete[]val;val = temp;val_capacity = num;}
}

数据控制

与固定长度数组不同，我们需要调用成员函数来实现数据增删。

压入新元素：void push_back(const T & elem)，在末尾追加新元素elem，如果有剩余空间大于1则直接写入，否则申请两倍的新空间。

插入新元素：void insert(int pos, T element)，在给定位置插入元素elem。

删除末元素：void pop_back()，删除最后一个元素。

清空元素：void clear()，将val_size置为0。

（memet（指针p，char val，以字节为单位的内存长度len），以字节为单位将val赋给p指向的长度为len的空间）

void push_back(const T & elem) {if (val_capacity - val_size <= 1)reserve(val_capacity*2);val[val_size++] = elem;
}
void insert(int pos, T elem) {if (val_capacity - val_size <= 1)reserve(val_capacity*2);val_size++;T temp;for (int i = pos; i < val_size; i++) {temp = val[i];val[i] = elem;elem = temp;}
}
void pop_back() {assert(val_size > 0);val[val_size--] = 0;
}
void clear() {memset(val, 0, sizeof(T) * val_size);val_size = 0;
}

数据访问

我们通过编写返回值为引用类型的函数来实现数据的读写功能。

引用返回这个数据本身而非他的拷贝，它是一种比指针更安全的数据传递手段。

重载[]号：T& operator[](int pos)，为了使我们的数组类有定长数组的特征，重载[]号使arr[]具有作用。[]接收一个int pos，返回pos对应位置的引用。

获取头元素：T& front()，获取第一个元素的引用。

获取尾元素：T& back()，获取最后一个元素的引用。

T& operator[](int pos) {assert(pos >= 0);//这是一个断言 它要求pos合法 否则抛异常return val[pos];
}
T& front() {assert(val_size > 0);return val[0];
}
T& back() {assert(val_size > 0);return val[val_size - 1];
}

Code

#include <cassert>
template <typename T>
class array {
private:T* val;int val_size;int val_capacity;
public:array() : val_size(0), val_capacity(1), val(nullptr) {};//无参构造array(int num) : val_size(0), val_capacity(num) {//提供初始空间的构造assert(num > 0);val = new T[num];}array(int size, T target_val) : val_size(size), val_capacity(size * 2) {//提供初始长度和初值的构造assert(size > 0);val = new T[size * 2];for (int i = 0; i < size; i++)val[i] = target_val;}array(T* begin, T* end) {//从固定长度数组中获取数据进行构造assert(begin != nullptr && end != nullptr);int size = end - begin;val = new T[size * 2];val_size = size;val_capacity = size * 2;memcpy(val, begin, sizeof(T)*size);}array(const array& another) {//拷贝构造val = new T[another.val_capacity];memcpy(val, another.val, sizeof(T) * another.val_size);val_size = another.val_size;val_capacity = another.val_capacity;}~array() {delete[]val;}const array& operator=(const array& another) {//重载等于号（这并不是构造，不能在初始化时使用）delete[]val;val = new T[another.val_capacity];memcpy(val, another.val, sizeof(T) * another.val_size);val_size = another.val_size;val_capacity = another.val_capacity;return *this;}void assign(int size, T target_val) {assert(size > 0);T* temp = new T[size * 2];for (int i = 0; i < size; i++)temp[i] = target_val;if (size < val_size)memcpy(temp, val, sizeof(T) * size);else memcpy(temp, val, sizeof(T) * val_size);delete[]val;val = temp;val_size = size;val_capacity = size * 2;}void swap(array& another) {array temp(another);*this = another;another = temp;}int size()const {return val_size;}bool empty()const {return val_size ? false : true;}void resize(int size) {assert(size > 0);T* temp = new T[size * 2];if (size < val_size)memcpy(temp, val, sizeof(T) * size);else memcpy(temp, val, sizeof(T) * val_size);delete[]val;val = temp;val_size = size;val_capacity = size * 2;}void resize(int size, T target_val) {assert(size > 0);T* temp = new T[size * 2];for (int i = 0; i < size; i++)temp[i] = target_val;if (size < val_size)memcpy(temp, val, sizeof(T) * size);else memcpy(temp, val, sizeof(T) * val_size);delete[]val;val = temp;val_size = size;val_capacity = size * 2;}int capacity()const {return val_capacity;}void reserve(int num) {if (num > val_capacity) {T* temp = new T[num];memcpy(temp, val, sizeof(T) * val_size);delete[]val;val = temp;val_capacity = num;}}void push_back(const T & elem) {if (val_capacity - val_size <= 1)reserve(val_capacity*2);val[val_size++] = elem;}void insert(int pos, T elem) {if (val_capacity - val_size <= 1)reserve(val_capacity*2);val_size++;T temp;for (int i = pos; i < val_size; i++) {temp = val[i];val[i] = elem;elem = temp;}}void pop_back() {assert(val_size > 0);val[val_size--] = 0;}void clear() {memset(val, 0, sizeof(T) * val_size);val_size = 0;}T& operator[](int pos) {assert(pos >= 0);//这是一个断言 它要求pos合法 否则抛异常return val[pos];}T& front() {assert(val_size > 0);return val[0];}T& back() {assert(val_size > 0);return val[val_size - 1];}
};

测试

#include <iostream>
#include "array.h"
using namespace std;
template <typename T>
void show(::array<T>& arr) {if (arr.empty())cout << "EMPTY";else for (int i = 0; i < arr.size(); i++)cout << arr[i] << ' ';cout << endl;
}
int main()
{//c++有自己内部的STL类型<array>，这里::表示是自己定义的array类::array<int>a;show<int>(a);::array<int>b(5); show<int>(b);::array<int>c(5, 3); show<int>(c);double x[] = {1.1,2.2,3.3};::array<double>d(x, x + 3); show<double>(d);::array<double>e(d); show(e);cout << endl;a = c; show<int>(a);b.assign(6); cout << b.size() << endl;c.assign(8, 2); show<int>(c);b.swap(c); show<int>(b);cout << endl;cout << b.size() << endl;cout << ( b.empty() ? "YES" : "NO") << endl;b.resize(10, 5); show<int>(b);cout << b.capacity()<<endl;b.reserve(50);cout << b.capacity()<<endl;cout << endl;a.push_back(10); show<int>(a);a.insert(1, 7); show<int>(a);a.pop_back(); show<int>(a);a.clear(); cout << (a.empty() ? "YES" : "NO") << endl;cout << endl;show<double>(d);d[1] = 8.8; show<double>(d);cout << endl;cout << d.front() << ' ' << d.back() << endl;return 0;
}