C、C++动态数组实现

严格来说，上一个版本不能算是纯粹的C语言版本，这是因为代码中使用了c++的引用特性，这是C语言所不包含的。然而，这是由于测试代码的限制，因而我们还是把它看做C语言的实现。（也可以编写一种不包含引用的代码来达到相同的效果，这要求使用到宏定义和一种称之为“wrapper”的小技巧）

闲话少叙，先放出新的测试代码，再具体讨论各个函数的改写方法。

//LibArray.cpp
// 实验内容：
// 1：将C语言版本LibArray用C++封装，注意，原C版本保留一个备份

// 实验目的：
// 1：C++类定义的基本方法

// 只提交CLibArray.cpp及CLibArray.h

#include "stdafx.h"
#include 
#include "CLibArray.h"

int _tmain(int argc, _TCHAR* argv[])
{
    CArray array;
    // 不再需要initial，但应该有正确的初始化
    // array_initial(array); 

    //array.recap(10); 
    //assert(array.capacity() == 10); 

    //////////////////////////////////////////////////////////////////////////
    for (int i = 0; i < 20; ++i)
    {
        array.append(i); 
    }
    assert(array.size() == 20); 

    for (int i = 0; i < array.size(); ++i)
    {
        assert(array.at(i) == i); 
    }

    //////////////////////////////////////////////////////////////////////////
    CArray array2, array3; 
    // array_initial(array2); 
    // array_initial(array3); 

    array2.copy(array); 
    assert(array.compare(array2) == true); 

    array3.copy(array); 
    assert(array.compare(array3) == true); 

    //////////////////////////////////////////////////////////////////////////
    array2.insert(2, 3); 
    assert(array.compare(array2) == false); 

    //////////////////////////////////////////////////////////////////////////
    array3.at(2) = 5; 
    assert(array.compare(array3) == false); 

    //////////////////////////////////////////////////////////////////////////
    // 不再需要destroy，但应该有正确的内存释放
    // array_destroy(array); 
    // array_destroy(array2); 
    // array_destroy(array3); 

    return 0;
}

类的定义

从测试代码和注释中可见，对变量 array，我们只需要定义一个合适的 CArray 类即可。而在类的定义部分，将原有的结构体成员放到 private 私有数据成员：

typedef int TypeName;
const int INITLENGTH = 10; //初始化长度可以为任意正整数,也可以为零，但需要把append函数里的语句做适当修改

private:
    TypeName *arrayhead;
    int arraysize;
    int arraycapacity;

自然而然地，我们需要将C语言版的各个函数，放到 CArray 类的公有部分作为接口。
另一方面，注意到注释部分：不再需要 initial 和 destroy 函数，学过c++的盆友们都知道，这是很自然的，因为在使用c++编程时，一般需要给自己定义的类写好对应的构造函数和析构函数，实际上这样的两种函数，就对应于原来的 initial 和 destroy 函数。
另外，注意到测试文件不再包含下列语句 array.recap(10);由于在C语言实现中， recap 函数用于给动态数组赋予一定的空间大小， 而测试函数中取消了此语句，那么就有两种可能的操作，一种是要考虑将空间的分配放在其他的函数中，或者保留 recap 函数，再让其他函数调用它。这样的特性很符合类的 protected 方法的定义。（当然，若不考虑继承，将其作为 private 方法也未尝不可）
于是总体思路清晰了：在 private 成员中定义了动态数组的必要参数，在 public 部分定义了可以进行的操作：

public:
    CArray();
    ~CArray();
    inline int capacity() { return arraycapacity; };
    inline int size() { return arraysize; };
    inline TypeName& at(int num) { return arrayhead[num]; };
    void append(int num);
    void copy(CArray &another);
    bool compare(CArray &another);
    void insert(int num, TypeName value);

protected:
    void recap(int length);
    void printarray();

简短的函数直接定义为内联函数（注意若直接写在类定义的头文件内，则无需 inline 关键字，然而是否最终编译为内联函数，取决于编译器的具体实现，关于 inline 关键字）

函数 printarray 用来输出动态数组的关键信息。

在改写函数时，主要工作是修改其参数，并在具体的定义中省去对调用对象本身的显式表示（也可以采用 this 指针来完成）。

构造函数和析构函数

在构造函数中，可以选择给头指针分配一定大小的内存，也可以赋值为空（nullptr，即C语言中的NULL），出于一种合情合理的原因，我给它分配了一定的大小。
在 c++中，使用 new 和 delete 来分配和释放内存，

CArray::CArray()
{
    arrayhead = new TypeName[INITLENGTH];
    arraysize = 0;
    arraycapacity = INITLENGTH;
}

而对于析构函数，只要相应地释放内存即可：

CArray::~CArray()
{
    delete[] arrayhead;
    arrayhead = nullptr;
    arraycapacity = 0;
    arraysize = 0;
}

注意：释放内存是必需步骤。且 delete[]与new []相对应。

recap函数

此函数是内存分配的关键，首先需保证其参数（capacity）合法，接下来，先新定义一个同类型的指针来指向需要的内存大小（capacity）的地址，并把原有的 arrayhead 所指向的内存里的数据复制到新的内存中，再删去原有的数据， 并让 arrayhead 指向新的内存地址。
这样的做的原因是，由于参数 capacity 与原有数组的 arraycapacity 和 arraysize 的大小关系不确定，因此只能新分配一块内存，再将所需内存大小的数据进行转存。
最后需要修改相关的 private 成员的值。

void  CArray::recap(int capacity)
{
    if (capacity < 0)
    {
        cout << "array's length should be larger than zero, check out array_recap()" << endl;
        exit(EXIT_FAILURE);
    }

    arraycapacity = capacity;
    arraysize = arraysize > capacity ? capacity : arraysize;

    TypeName* buffer = nullptr;
    buffer = new TypeName[capacity];
    memcpy(buffer, arrayhead, sizeof(TypeName) * arraycapacity);

    delete[] arrayhead;
    arrayhead = buffer;

    //分配失败
    if (arrayhead == nullptr)
    {
        cout << "malloc failed in array_recap()." << endl;
        exit(0);
    }
}

append 函数

该函数所需要做的工作是给第 num 位的成员赋值为 num。 为了达到此目的，需要检查 num 和 capacity 之间的关系，若 num > arraycapacity，则需要使用 recap 函数扩大数组的容量，扩大的方式和大小可自行定义， 在此采取每次扩大一倍的方式，这样，算法的复杂度将由O(n) 减小为 O(c)，此原理不详述。
注意到每次扩大一倍容量的前提是， capacity不为零，因此，在构造函数中， 我选择给数组一个不为零的内存大小，当然，如果坚持在构造函数中要使用 arrayhead = nullptr;那么在 append 函数中， 可以使用 (*this).recap((arraysize +1)*2); 这样的代码。

//给 arrayhead 数组的第 num 位赋值为 num， 若 num 大于实际长度，则扩充长度至 num
void  CArray::append(int num)
{
    if (num + 1 > arraycapacity)
    {
        // 一次扩大为原来的两倍， 时间复杂度更小（O(n) - > O(c)）
        (*this).recap(arraysize *2);
    }
    arrayhead[arraysize++] = num;
}

copy函数

和C语言版本基本一致，我们需要做的工作是使调用对象的容量与被复制的对象大小一致，然后将所有数据复制到调用对象的内存中，这样可以实现动态数组的复制。

//将 another 对象复制给调用的对象
void  CArray::copy(CArray &another)
{
    (*this).recap(another.capacity());
    memcpy(arrayhead, another.arrayhead, another.size() * sizeof(TypeName));
    arraysize = another.size();
}

注意：使用 memcpy 函数，比用 for 循环逐一赋值的效率要高，因为 mencpy 可以充分利用数据总线的位数进行传输。

compare函数

此函数几乎没有要修改的地方，唯一值得注意的是，为了输出比较的结果，我选择了用 for 循环来逐一比较数据， 若只要求其总体比较的结果，可以使用 memcmp 函数，效率更高，也更简洁。

bool  CArray::compare(CArray &another)
{
    //another.printarray();
    //输出 size 不同的信息
    if (another.size() != arraysize)
    {
        cout << "Their size are not equal, check out in CArray::compare()." << endl;
        return false;
    }

    if (another.capacity() != arraycapacity)
    {
        cout << "Their capacity are not equal, check out in CArray::compare()." << endl;
        return false;
    }
    //为了输出是第几位不同，采用循环，否则可以采用以下语句，效率更高
    //return memcmp(another.arrayhead, arrayhead, size() * sizeof(TypeName)) == 0;
    for (int i = 0; i < another.size(); i++)
        if (another.arrayhead[i] != arrayhead[i])
        {
            cout << "They are not equal in the NO." << i << " place" << endl;
            return false;
        }

    return true;
}

insert 函数

此函数需要在 第 index 的位置插入一个值为 value 的元素，为此，只需要使用 recap 函数每次多增加一个单位长度的内存空间即可，顺次移动 index 前的各位，然后将第 index 位赋值。

void  CArray::insert(int index, TypeName value)
{
    if (index > arraycapacity || index < 0)
    {
        cout << "Cannot insert with an invaild index, check out in array_insert()." << endl;
        exit(EXIT_FAILURE);
    }
    else
    {
        (*this).recap(arraycapacity + 1);

        for (int i = arraycapacity - 1; i > index; i--)
            arrayhead[i] = arrayhead[i - 1];
        arrayhead[index] = value;

        arraysize ++;
    }
}

printarray函数

此函数的实现因人而异，只需要获得调试时所需要的信息即可。

总结

本篇博客实现了动态数组的C++版本的一种简单实现。未完善的地方必然存在，望广大读者批评指正。为了符合测试程序， 我没有采用模板进行代码的编写，虽然在上一版的实验要求中提到了，对程序的要求是能够各种不同类型的数据。然而代码中没有使用模板进行对象的声明，可知无需进行模板类和模板函数的编写。
关于异常的编写，代码中某些函数使用了诸如exit(EXIT_FAILURE)这样的语句。在 C++ 中，更为规范的实现是抛出异常， 再进行针对性的处理，由于测试程序较为简单，因此没有编写针对异常的代码