数组
数组是几乎任何程序语言中的一个基本要素。它用一段连续的地址空间来记录线性表中的各个元素。在C语言中，我们可以按照如下的方式定义一个具有6个元素的double类型数组:
double array[6];
采用同样的方式，用其它类型名称替换这里的double就可以定义各种类型的数组了。因此，我们定义一个宏'T'来替代这里的double，以后都用T来指代任意的数据类型。
#define T double
T array[6];
我们可以通过array[i]的形式访问数组中的第i个元素。我们知道，在C语言中array本质上就是一个指针，所以我们也可以动态的申请一段内存之后，然后以一种类似数组的方式来操作这段内存。
比如说我们可以像下面这样，使用C的标准库函数malloc来动态的创建一个具有6个元素的数组。使用该函数需要包含头文件<stdlib.h>。
#include <stdlib.h>
T *array = (T*)malloc(6 * sizeof(T));
free(array);
这两种方式的数组各有优势。动态申请的方式比较灵活一些，可以在程序运行过程中根据具体需要指定数组大小。但是由于是从操作系统中动态申请的，所以在使用完毕后需要调用函数free释放申请的内存，
否则将造成内存泄漏。原生数组的方式，就不太需要关心内存的释放问题了，但是其数组大小在编译的时候据需要确定下来，使用起来都有不便，以后称这种方式为静态的方式。
下面我们先介绍可以动态数组的数组实现，再在此基础上，删减一些功能得到静态数组的实现。动态数组用于有内存管理的系统中，静态数组用于没有内存管理或者数组大小可以预估的场景中。 最后，我们提供一个C++的模板类型。
1. 动态数组的实现
为了方便管理数组，我们定义如下的结构体array_double。左侧是完整的定义形式，将其中的宏展开之后就得到了右侧的结构体。这里的double只是一个示例，我们可以替换为任何其它类型。 其中宏定义TEMPLATE_TYPE需要一个参数a，在扩展的时候将用a来替代##，所以这里的TEMPLATE_TYPE(array)展开之后就是array_double。
|
|
这里定义了三个指针。因为动态指定数组空间的时候，往往不能明确的知道真正需要的空间大小，所以一般都会多申请一些内存。这里使用一段前闭后开的区间[stor_begin, stor_end)来表示数组的存储空间。 指针end指向尾元素\(a_{n-1}\)之后的地址，表示第一个空闲的地址。
1.1 初始化数组
下面我们定义一个函数来初始化array对象，其函数原型定义如下，将其宏定义展开之后就是右边的代码。这里的TEMPLATE_FUNCTION分别用a和name替代了_double_左右两侧的##。
|
|
该函数的具体定义如下，它的第一个参数就是我们将要初始化的array对象，在以后的历程中，第一个参数都将是我们要操作的对象，就好像是C++中的this指针一样。第二个参数指定了申请的元素数量。 为了保证malloc总是能够返回一个合法的地址，我们先检查一下参数size，确保申请内存大于0。正常情况下malloc将从操作系统那里申请一段指定大小的内存，当然也存在一些极端的情况，比如系统内存耗尽， 我们将返回一个非零的值表示函数运行出错。正常申请了内存之后，我们也对其他几个指针赋予了初值。
int TEMPLATE_FUNCTION(array, init)(TEMPLATE_TYPE(array) *a, int size) {
int alloc_size = size > 0 ? size : 1;
a->stor_begin = (T*)malloc(alloc_size * sizeof(T));
if (0 == a->stor_begin)
return 1;
a->stor_end = a->stor_begin + alloc_size;
a->end = a->stor_begin + size;
a->begin = a->stor_begin;
return 0;
}
在定义array结构体的时候，我们特意写下了stor_end和end两个指针，就是想区分开array的容量和大小两个概念。所谓的容量就是当前申请的内存最多可以保存多少个元素，而大小则是实际保存的元素数量。 我们定义了如下的函数array_T_capacity获取数组的容量，array_T_size计算数组的大小。
int TEMPLATE_FUNCTION(array, capacity)(TEMPLATE_TYPE(array) *a) {
return a->stor_end - a->stor_begin;
}
int TEMPLATE_FUNCTION(array, size)(TEMPLATE_TYPE(array) *a) {
return a->end - a->stor_begin;
}
1.2 访问数据元素
我们可以通过指针stor_begin来访问数组中的元素，即array.stor_begin[i]。很多时候我们在使用基本数据结构的时候，并不希望了解其内部的构造，只想要调用相应的API来完成所需的功能。 所以我们定义了一个宏对其进行简单的封装。需要注意的是其输入参数应当是一个array_T类型的变量，不是一个指针。这样我们才可以通过类似ARRAY(a)[i]的形式访问数组中的第i个元素。
#define ARRAY(a) ((a).stor_begin)
此外，还可以定义一些函数来访问数组的元素。
// 获取第i个元素
T TEMPLATE_FUNCTION(array, e)(TEMPLATE_TYPE(array) *a, int i) {
return *(a->stor_begin + i);
}
// 获取第i个元素的地址
T* TEMPLATE_FUNCTION(array, e_ptr)(TEMPLATE_TYPE(array) *a, int i) {
return (a->stor_begin + i);
}
// 设定第i个元素的值
void TEMPLATE_FUNCTION(array, set)(TEMPLATE_TYPE(array) *a, int i, T v) {
a->stor_begin[i] = v;
}
1.3 搜索、插入、删除
函数array_T_find就是一种简单的线性查找方法。对于数组a，该函数查找数组中第一个值为v的元素，并返回它的地址。最差的情况下，目标元素位于数组的尾部，需要与数组中的每个元素对比一遍， 因此其复杂度为\(O(n)\)。
T* TEMPLATE_FUNCTION(array, find)(TEMPLATE_TYPE(array) *a, T v) {
for (T *p = a->stor_begin; p < a->end; p++)
if (v == *p)
return p;
return 0;
}
向数组中插入元素就比较麻烦了，因为数组中的元素都是紧密的排列在一起的，它们的地址是连续的。所以要想在它们中间插入一个元素，需要先把后面的元素一次移动一个位置，才能够存入新插入的元素。 如函数array_T_insert中，我们先简单的检查一下输入的参数，确保插入的位置在数组内部。接着就把数组的大小扩张一个单元，并通过标准库函数memmove将第i个及其之后的元素向后移动了一个位置。 最后将数值v写到了第i个位置上。最差的情况就是，每次都在首位插入，这样就需要把全部n个元素都向后移，因此其复杂度为\(O(n)\)。
int TEMPLATE_FUNCTION(array, insert)(TEMPLATE_TYPE(array) *a, int i, T v) {
int size = TEMPLATE_FUNCTION(array, size)(a);
if (i > size)
return 1;
TEMPLATE_FUNCTION(array, resize)(a, size + 1);
if (i < size)
memmove(a->stor_begin+i+1, a->stor_begin+i, sizeof(T)*(size - i));
a->stor_begin[i] = v;
return 0;
}
有一点需要强调一下，就是在函数的第三行中，我们判定如果插入的目标索引超过数组的大小就报错返回。这有两个方面的考虑，其一超出了数组的大小，就意味着数组中的元素地址不连续了，这违背了我们对数组的定义， 应当避免这种情况发生。其二，不大于就意味着可以等于，此时相当于在数组末尾的位置上拼接了一个元素，它并没有打破定义，所以是一种合理的操作。
在插入函数中，我们调用了函数array_T_resize。在这个函数首先查询了一下数组a的容量，如果不足以容纳新的数组大小，就将扩容一倍，直到能够容下为止。
int TEMPLATE_FUNCTION(array, resize)(TEMPLATE_TYPE(array) *a, int size) {
int cap = TEMPLATE_FUNCTION(array, capacity)(a);
while (cap < size) {
TEMPLATE_FUNCTION(array, adjust_capacity)(a, 2*cap);
cap = TEMPLATE_FUNCTION(array, capacity)(a);
}
a->end = a->stor_begin + size;
return 0;
}
数组扩容函数array_T_adjust_capacity如下所示。它首先判定新的容量是否大于数组大小，这点很重要，根据我们的定义容量是一定不能小于数组大小的。如果新的容量大小没有改变， 我们也就不需要作任何调整了。只有在上述两种情况都不满足的情况下，它才会调用标准库函数realloc重新申请内存。realloc会保证原来的数据被拷贝到新的地址空间下。最后更新一下array指针。
int TEMPLATE_FUNCTION(array, adjust_capacity)(TEMPLATE_TYPE(array) *a, int c) {
int size = TEMPLATE_FUNCTION(array, size)(a);
if (c < size)
return 1;
int capacity = TEMPLATE_FUNCTION(array, capacity)(a);
if (c == capacity)
return 0;
capacity = c > 0 ? c : 1;
T *tmp = (T*)realloc(a->stor_begin, capacity * sizeof(T));
a->stor_begin = tmp;
a->stor_end = a->stor_begin + capacity;
a->end = a->stor_begin + size;
return 0;
}
从数组中删除元素可以说是插入的逆，它需要将目标元素之后的所有元素向前移动一个位置。下面的函数array_T_remove就在完成这一工作之后，更新了数组的大小。
int TEMPLATE_FUNCTION(array, remove)(TEMPLATE_TYPE(array) *a, int i) {
int size = TEMPLATE_FUNCTION(array, size)(a);
if (i > size)
return 1;
memmove(a->stor_begin+i, a->stor_begin+i+1, sizeof(T)*(size - i - 1));
a->end -= 1;
return 0;
}
2. 静态数组的实现
静态数组的大小在编译之初就已经确定了，在运行过程中不能改变，这点在使用的时候多少有些不便。但是，在一些没有内存管理的嵌入式裸机中，静态数组大有用武之地。此外， 它也适用于明确的知道所需内存上限的场景。为了与动态数组加以区分，我们加上一个前缀，成为"s_array_T"。其宏定义和展开形式如下所示，仍然使用成员变量stor_begin和stor_end指示存储空间， 并用end标识数组结尾。
|
|
2.1 初始化
由于静态数组不能动态的申请内存，所以其初始化过程就不能使用malloc函数了，我们需要在初始化的时候为静态数组指定一段已经分配好的存储空间。所以我们对初始化函数s_array_T_init作如下的修改。 除了数组对象a和大小之外，它还多了buf和capacity两个参数，分别指示分配的存储空间起始地址和容量。
int TEMPLATE_FUNCTION(s_array, init)(TEMPLATE_TYPE(s_array) *a, int size, T *buf, int capacity) {
a->stor_begin = buf;
a->stor_end = buf + capacity;
a->end = buf + size;
return 0;
}
这个初始化函数的内容很简单，就是对结构体的三个成员指针赋予初值。调用它对一个数组初始化之前，我们需要有一段空间，下面就是一种比较常用的形式。通过一个宏来指明数组的容量，这样可以提高代码的自解释性。 然后定义一个数组缓存和数组，并调用s_array_T_init进行数组初始化。
#define ARRAY_BUF_LEN 1024
double array_buf[ARRAY_BUF_LEN];
s_array_double array;
s_array_double_init(&array, 32, array_buf, ARRAY_BUF_LEN);
获取数组的大小和容量的函数实现与动态数组的一样，元素的访问方式以及搜索也没有差别，这里不再赘述。
2.2 插入、删除
由于静态数组不能动态的修改内存大小，所以对其插入操作需要先判定数组的剩余空间。如下面的代码所示，我们查询了当前的大小和容量，如果插入一个元素之后就超出了数组的容量就报错返回。 此外，我们还保留了插入位置不能超出数组大小的约束，这样就可以在数组末尾拼接元素，而且避免了违背数组定义的插入操作。
int TEMPLATE_FUNCTION(s_array, insert)(TEMPLATE_TYPE(s_array) *a, int i, T v) {
int size = TEMPLATE_FUNCTION(s_array, size)(a);
int cap = TEMPLATE_FUNCTION(s_array, capacity)(a);
if (((size + 1) > cap) || (i > size))
return 1;
for (int idx = size; idx >= i; idx--)
a->stor_begin[idx] = a->stor_begin[idx-1];
a->stor_begin[i] = v;
a->end++;
return 0;
}
在插入函数的第8,9行中，我们倒叙的将插入位置之后的元素依次向后移动了一个位置。这里特意用一个for循环来实现，而没有像动态数组那样使用标准库函数memmove。这样做主要是考虑到了， 静态数组可能工作在没有内存管理功能的系统中。
下面是静态数组的删除函数。该函数可以删除数组中从from开始到to的所有元素，包含\(a_{from}\)但不包含\(a_{to}\)，所以在函数的一开始先判定to不小于from，否则返回1， 其实可以再定义一系列的宏或者是一个枚举类型来记录各种不同的错误号，但是这里的条件很简单就省略了。接着我们还要查看一下需要删除的区间不要超出了数组的范围，否则没有意义。 在完成了对输入参数的检测之后，就将to之后的所有元素依次挪到from之后，这样做就覆盖了原有的数据，相当于删除了数据，最后更新一下数组成员指针。
int TEMPLATE_FUNCTION(s_array, remove_section)(TEMPLATE_TYPE(s_array) *a, int from, int to) {
if (to < from)
return 1;
int size = TEMPLATE_FUNCTION(s_array, size)(a);
if (to >= size)
return 2;
int len = size - to;
for (int idx = 0; idx < len; idx++)
a->stor_begin[from + idx] = a->stor_begin[to + idx];
a->end -= (to - from);
return 0;
}
同样的，这里特意没有使用库函数，这个函数同样适用于动态版本的数组中。另外如果我们只希望删除一个元素，只需要像下面调用该函数就可以实现了:
TEMPLATE_FUNCTION(s_array, remove_section)(a, i, i+1);
3. C++模板类
我们为了得到所谓的抽象数据的效果，在C语言的版本中使用了大量的宏定义，在一定程度上增加了代码的复杂程度。相比之下，C++因为有模板(template)、重载操作符、 成员权限(public和private之分)等机制，实现起来更灵活一些。
首先，我们定义一个模板类DataArray，和以前一样它用三个指针stor_begin, stor_end和end来指示数组的内存边界和数据边界。所不同的是我们可以将他们设定成private的权限， 这样除了DataArray类型的对象之外，就没谁能够直接操作这些边界了，增加了数据的安全性。此外，还定义和实现了一个默认构造函数，该函数为三个边界指针赋予了初值0。
template <class T>
class DataArray {
public:
DataArray() : mStorBegin(0), mStorEnd(0), mEnd(0) { }
private:
T *mStorBegin;
T *mStorEnd;
T *mEnd;
};
在使用的时候，我们可以按照下面的形式定义一个用于装载double类型的DataArray对象。这里的模板类型实现，与我们之前的C语言版本的各种宏定义所作的工作类似，
都是通过一个T来表示任意一种类型。我们可以理解为，编译器把通过关键字template <class T>定义的类型T都用double替换了。
DataArray<double> array;
3.1 数组的初始化
在C++中的构造函数的让我们可以在创建对象的时候，就对其进行初始化，这样就不需要像C语言版本那样，先定一个数组变量在通过init函数进行初始化操作。而且它可以重载多个函数， 来满足我们不同的初始化需求。刚刚我们就定义了一个默认的构造函数，那个构造函数没有任何的参数，也没有特别的操作，就是创造了一个对象并赋予了初值。
下面就是两个不同的构造函数。左边的函数需要一个参数size用来指定构造的数组大小，但是它并不对构造出来的数组内容负责。在函数中，先检查了一下输入的参数，然后用向系统申请一段大于指定大小的内存。 这里刻意保持申请的内存大小为2的指数幂，之所以这样做，是因为我曾听闻有些邪教声称这样申请内存会快一些，权且相信它们吧。申请完毕之后就对三个边界指针的赋值操作。
右边的构造函数，有两个参数，它构建了一个长度为len的数组对象，并用缓存buf下的内容为之赋予初值。它的套路于左边的函数没什么区别，只是在最后将缓存buf下的内容拷贝到了新申请的数组中。
|
|
此外还有一个特殊的构造函数——拷贝构造函数，值得我们特别关注。默认构造函数和拷贝构造函数都是一个类所必需的构造函数，即使我们不去实现，编译器也会为我们准备一个。 但是很多时候编译器并不能理解我们的用意，所以它们准备的函数一般不能满足我们的需求，往往需要我们专门提供一个版本。所谓的拷贝构造函数，就是通过赋值语句或者参数传递来构建对象时所需调用的构造函数。 它以一个本类型的引用作为参数，如下面代码所示，作为拷贝对象。这里的拷贝构造实现的是硬拷贝操作，先查询一下拷贝对象的容量和大小，在构建一个一样容量的数组，并依次把拷贝对象中的内容复制到新申请的内存中。
DataArray(DataArray const & array) {
int c = array.capacity();
int n = array.size();
mStorBegin = new T[c];
mStorEnd = mStorBegin + c;
mEnd = mStorBegin + n;
for (int i = 0; i < n; i++)
mStorBegin[i] = array[i];
}
因为，在构建和使用数组对象的过程中，我们向系统动态的申请过内存，所以在释放对象的时候，我们还需要显式的释放这些申请的内存，否则会造成内存泄漏。在C++中释放对象的时候，会调用一个所谓的析构函数， 这个函数就是让程序员释放不需要的内存的。例如下面的析构函数，就是通过关键字delete释放mStorBegin所指的内存空间。这里我们可以看到申请和释放内存时使用的是C++原生的new和delete操作符， 我们也可以使用C版本中的malloc和free函数来完成相同的功能，但是不建议这样做，更不建议两种方式混合使用。
~DataArray() {
if (0 != mStorBegin)
delete [] mStorBegin;
}
3.2 元素访问
我们知道C/C++原生数组的元素访问可以通过操作符[]来实现。在C语言版本中为了仍然能够使用类似的方式，我们专门定义了一个宏，但是每次访问的时候都需要多敲几个字母，显得很繁琐。 在C++中可以对操作符进行重载，这样我们就可以直接使用[]来访问元素了，例如下面的重载实现。
T & operator [] (int idx) {
assert((mStorBegin + idx) < mStorEnd);
return mStorBegin[idx];
}
这个重载实现返回的是一个引用，这样它返回的结果既可以用作左值，也可以用作右值。也就是说我们可以向下面这样为一个数组元素赋值，也可以获取一个数组元素:
DataArray<double> array(4);
array[0] = 3.14;
array[1] = array[0];
3.3 搜索、插入、删除
C++版本的搜索、插入、和删除的操作与静态版本的数组实现极为类似，只是参数都是引用的形式，这里不再赘述了。
4. 完
在本文中，我们实现了三种不同类型的数组。C语言版本的动态形式数组可以在使用过程中动态的申请内存，使用起来比较灵活，但是需要至少提供一个内存管理器。 C语言版的静态数组，虽然在编译之初就需要明确数组的大小，灵活性较小，但是可以用于没有内存管理的系统。实际上有了操作系统和编译器，这些都不是问题，C++版本的实现就很灵活， 只是它需要强大的工具来把源代码转换成机器语言。
为了满足ADT的设计思想，在C语言版本的实现中，我们定义了各种宏，C++版本则使用了它的模板特性。两者相比C语言的实现和使用相对繁琐一些，但也还是比较方便的。