写在前边：读本文您至少得能写一点C语言。
数组
数组是一个有序的元素序列，它是最基础的数据结构，是线性表的最自然的描述方式。它通过将相同大小的数据单元一个接着一个地排放来存储数据。由它的这种存放方式，我们可以以非常快的速度找出它其中的某一个位置上的元素：我们可以直接算出第n个数据的位置，从而实现直接寻址。
一般的计算机程序使用一个连续的空间来存放数组。由于高速缓存的应用，读取连续的数据往往更加高效。
数组定义了两个基本操作：随机读取——对一个指定的下标，读取它的值和随机写入——对于一个指定的下标，修改它的值。
数组的实现
在C和C++语言中，我们通常使用数组首个元素的地址来代表一个数组。符号表中数组标识符的类型是一个指针。执行如下的代码：
int test[20];
cout << test << "----" << &test[0] << endl;
我们得到了如下的输出：0x61fdd0----0x61fdd0
可以看到：数组的标识符即为数组首元素的指针。这就说明，我们可以使用指针的操作来遍历一个数组。
方括号是什么？
对一个指针A进行[x]的操作，实际上相当于*(A + x)
运行如下的代码：
int testInt;
int* intPointer = &testInt;
cout << intPointer + 5 << "----" << &intPointer[5] << endl;
我们得到了如下的输出：0x61fe18----0x61fe18
在多数的语言中，数组的大小一经声明便无法更改。因此我们需要：
动态数组
所谓动态数组，就是封装之后的标准数组，同样没有办法跳出C/C++内存管理的限制，所谓动态只是我们在需要时重新申请一块大小不同的内存空间而已。对于动态数组，我们一般维护它目前的最大容量、目前已经占用的空间和一个指针（标准数组）。它一般支持：随机读写、随机插入、随机删除。
我们来简单写一下它的架构。
template<class elementType>
class array {
protected:
elementType* ptl; //存放数据的标准数组
int maxLength; //标准数组申请的长度
int usedLength = 0; //标准数组中已占用的长度
void increaseSize();//放大数组大小
void decreaseSize();//缩小数组大小
public:
array(int initSize = 10);//标准构造函数
array(const array<elementType> &theArray);//复制构造函数
~array() { delete[] ptl; }//析构函数
int size() const { return usedLength; }//返回大小
bool empty() const { return usedLength == 0; }//判空
bool vaildIndex(int index) const { return index >= 0 && index < usedLength; }//判断索引是否有效 此函数可以声明为protected
array<elementType>& operator=(const array<elementType> &A);//重载赋值运算符
elementType& operator[](unsigned int const index);//读写
void pop();//弹出元素
void pop(unsigned int const index);//按索引弹出元素
void push(elementType val);//压入元素
void push(elementType val, unsigned int const index);//按索引压入元素
};
接下来我们来实现它：
首先来写构造函数：一般构造函数非常直观，对最大长度变量赋值，然后申请空间。
复制构造函数使用了重载赋值运算符。
template<class elementType>
array<elementType>::array(int initSize) : maxLength(initSize) {
ptl = new elementType[initSize];
}
template<class elementType>
array<elementType>::array(const array<elementType> &theArray) {
ptl = new elementType[theArray.maxLength];
*this = theArray;
}
再实现两个private方法：
两个方法的实现非常相似且直观
template<class elementType>
void array<elementType>::increaseSize(){
elementType* tempPtl = new elementType[maxLength * 2];
for (int i = 0; i < usedLength; i++){
tempPtl[i] = ptl[i];
}
maxLength *= 2;
delete[] ptl;
ptl = tempPtl;
}
template<class elementType>
void array<elementType>::decreaseSize(){
elementType* tempPtl = new elementType[maxLength / 2];
for (int i = 0; i < usedLength; i++){
tempPtl[i] = ptl[i];
}
maxLength /= 2;
delete[] ptl;
ptl = tempPtl;
}
重载两个运算符：
此处注意：C++要求赋值运算符返回左值的引用。
template<class elementType>
array<elementType>& array<elementType>::operator=(const array<elementType> &A) {
maxLength = A.maxLength;
usedLength = A.usedLength;
for (int i = 0; i < A.usedLength; i++){
ptl[i] = A.ptl[i];
}
return *this;
}
template<class elementType>
elementType& array<elementType>::operator[](unsigned int const index) {
if (vaildIndex(index))
return ptl[index];
else
throw("invaild index");
}
最后完成两个操作的四个重载方法：
template<class elementType>
void array<elementType>::pop() {
usedLength--;
if (usedLength <= maxLength / 4)
decreaseSize();
}
template<class elementType>
void array<elementType>::pop(unsigned int const index) {
if (vaildIndex(index)) {
for (int i = index; i < usedLength - 1; i++)
ptl[i] = ptl[i + 1];
usedLength--;
if (usedLength <= maxLength / 4)
decreaseSize();
}else
throw("invaild index");
}
template<class elementType>
void array<elementType>::push(elementType val) {
usedLength++;
if (usedLength >= maxLength)
increaseSize();
ptl[usedLength - 1] = val;
}
template<class elementType>
void array<elementType>::push(elementType val, unsigned int const index) {
usedLength++;
if (vaildIndex(index)) {
if (usedLength >= maxLength)
increaseSize();
for (int i = usedLength; i > index; i--)
ptl[i] = ptl[i - 1];
ptl[index] = val;
}else {
usedLength--;
throw("invaild index");
}
}
一个简单的动态数组类就完成了。
实际上如果#include<vector>，你可以使用C++标准库中的动态数组STLstd::vector，它与上述动态数组有类似的功能并且附加了很多实用的方法。
一点练习
请你在上述例程的基础上，重载操作符==和!=，判断两个array类的引用是否完全相同。
