基本数据结构（1） —— 动态数组

我们设计动态数组的目的在于，利用C++模板技术，消除C++语言中对数组的种种限制，如数组无法成为函数的参数或返回值（除非是指针），数组无法直接赋值等等。

1 一维动态数组

 

一维动态数组将一个普通数组封装成data：

 

来看具体实现：

 

template <class T>
class Array
{
protected:
    T* data;
    unsigned int base;
    unsigned int length;

public:
    Array ();
    Array (unsigned int, unsigned int = 0);
    ~Array ();

    Array (Array const&);
    Array& operator = (Array const&);

    T const& operator [] (unsigned int) const;
    T& operator [] (unsigned int);

    T const* Data () const;
    unsigned int Base () const;
    unsigned int Length () const;

    void SetBase (unsigned int);
    void SetLength (unsigned int);
};

template <class T>
Array::Array() :
data (new T [0]),
base (0),
length (0)
{}

template <class T>
Array::Array (unsigned int n, unsigned int m) :
data (new T [n]),
base (m),
length (n)
{}

template <class T>
Array::Array (Array const& array) :
data (new T [array.length]),
base (array.base),
length (array.length)
{
    for (unsigned int i = 0; i < length; ++i)
    {
        data [i] = array.data [i];
    }
}

template <class T>
Array::~Array ()
{
    delete [] data;
}

template <class T>
T const* Array::Data() const
{
    return data;
}

template <class T>
unsigned int Array::Base() const
{
    return base;
}

template <class T>
unsigned int Array::Length() const
{
    return length;
}

template <class T>
T const& Array::operator [] (unsigned int position) const
{
    unsigned int const offset = position - base;
    if (offset >= length)
    {
        throw out_of_range ("invalid position");
    }

    return data [offset];
}

template <class T>
T& Array::operator [] (unsigned int position)
{
    unsigned int const offset = position - base;
    if (offset >= length)
    {
        throw out_of_range ("invalid position");
    }

    return data [offset];
}

template <class T>
void Array::SetBase (unsigned int newBase)
{
    base = newBase;
}

template <class T>
void Array::SetLength (unsigned int newLength)
{
    T* const newData = new T [newLength];
    unsigned int const min =
        length < newLength ? length : newLength;
    for (unsigned int i = 0; i < min; ++i)
    {
        newData [i] = data [i];
    }

    delete [] data;
    data = newData;
    length = newLength;
}

2 二维动态数组

 

二维动态数组的实现比一维数组更简单：

 

[cpp] view plaincopy

template <class T>
class Array2D
{
protected:
    unsigned int numberOfRows;
    unsigned int numberOfColumns;
    Array* array;

public:
    Array2D (unsigned int, unsigned int);
    //T& Select (unsigned int, unsigned int);
    Array const& operator[](unsigned int index) const{ //const版本
        return array[index]; //返回索引处的一维数组对象
    }
    Array& operator[](unsigned int index){ //非const版本
        return array[index]; //返回索引处的一维数组对象
    }
};

template <class T>
Array2D::Array2D( unsigned int m, unsigned int n ):
numberOfRows (m),
numberOfColumns (n),
array (0)
{
    //为一维数组Array分配原始内存
    void* raw=::operator new[](numberOfColumns * sizeof(Array));
    array=static_cast*>(raw);
    //用placement new调用构造函数初始化各个元素的内存
    for(std::size_t i=0;i
        new(array+i) Array(numberOfRows);