C++动态数组模版类Vector实例详解
1.实现机制
内部主要通过m_capacity数组容量成员和m_length数组有效长度成员来维护一个T* data数组空间.
内部默认分配一定数量大小的数组指针,每次append尾部追加的时候,无需再次分配空间,直接赋值标志length长度,假如超过当前空间容量,则再次扩大分配新的内存数组,并将旧数组拷贝至新数组及释放旧数组.
Vector需要实现的public函数如下所示:
- inline int capacity() ：获取容量
- inline int length() :获取有效长度
- void resize(int asize) :改变数组的有效长度
- void append(const T &t) :尾部追加一个元素
- T& operator[] (int i) :通过[]获取元素
- T operator[] (int i) const ：通过[]获取常量元素
- void clear() ：清空数组中的数据
- inline boolisEmpty():数组是否有数据
resize()函数实现细节:
- 如果resize长度大于当前容量时 :则扩大分配新的内存数组,并将旧数组拷贝至新数组及释放旧数组.
- 如果resize长度小于当前length时 :则需要将多余的成员进行释放,调用析构函数实现.
- 如果resize长度大于当前length时 :则需要调用默认构造函数来填充内部数组.
2.代码实现
#ifndef VECTOR_H
#define VECTOR_H
#include "throw.h"
// throw.h里面定义了一个ThrowException抛异常的宏,如下所示:
//#include <iostream>
//using namespace std;
//#define ThrowException(errMsg) {cout<<__FILE__<<" LINE"<<__LINE__<<": "<<errMsg<<endl; (throw errMsg);}
template <typename T>
class Vector
{
T* m_data;
int m_length; // 有效数据的长度
int m_capacity; // 分配容量的长度
// 分配
T* allocate(int size)
{
T* arr = new T[size];
if(arr == NULL) {
ThrowException( "No memory to create DynamicArray object ...");
}
return arr;
}
// 重新分配
void realloc(int capacity)
{
T* newData = allocate(capacity);
for(int i=0; i<m_length; i++) {
newData[i] = m_data[i];
}
delete[] m_data;
m_data = newData;
m_capacity = capacity;
}
// 调用析构函数
void destruct(int from, int end)
{
while(from++<end) {
m_data[from].~T();
}
}
// 调用默认构造函数
void defaultConstruct(int from, int end)
{
while(from++<end) {
m_data[from] = T();
}
}
public:
Vector(int lenght = 50) { m_length = 0; m_data = allocate(lenght); m_capacity = lenght; }
inline int capacity() const { return m_capacity; } // 获取容量
inline int size() { return m_length; } // 获取有效长度
inline int length() { return size(); }
inline T *data() { return m_data; }
inline const T *data() const { return m_data; }
inline bool isEmpty() const { return m_length == 0; }
void clear()
{
if(!m_length) return;
destruct(0, m_length);
m_length = 0;
}
void resize(int asize)
{
if(asize == m_length) return;
// 重新分配的大小>当前容量时
if(asize > m_capacity) {
realloc(asize);
}
if (asize < m_length) // 分配的大小<当前大小时,则调用析构
destruct(asize, m_length);
else // 分配的大小>当前大小时,则调用默认构造
defaultConstruct(m_length, asize);
m_length = asize;
}
// 尾部追加一个元素
void append(const T &t)
{
if(m_length == m_capacity) {
realloc(m_capacity+20); // 如果容量满了,则默认增加20个容量.方便后面append无需再次分配内存
}
m_data[m_length] = t;
m_length++;
}
T& operator[] (int i)
{
if((0 <= i) && (i < length()))
{
return m_data[i];
}
else
{
ThrowException("Parameter i is invalid ...");
}
}
T operator[] (int i) const
{
return m_data[i];
}
};
#endif // VECTOR_H
3.测试运行
测试如下所示:
class Test {
public:
int number;
Test(int n = 0) {
number = n;
}
};
int main(int argc, char *argv[])
{
Vector<Test> arr;
for(int i = 0; i < 10; i++)
arr.append(Test(i));
cout<<"********* Arr Len:"<<arr.length()<<" capacity:"<<arr.capacity()<<endl;
for(int i = 0; i < arr.length(); i++)
cout<<"arr []:"<<arr[i].number<<endl;
cout<<"*********"<<endl;
arr.resize(13);
cout<<"********* Arr Len:"<<arr.length()<<" capacity:"<<arr.capacity()<<endl;
for(int i = 0; i < arr.length(); i++)
cout<<"arr []:"<<arr[i].number<<endl;
cout<<"*********"<<endl;
arr.resize(5);
cout<<"********* Arr Len:"<<arr.length()<<" capacity:"<<arr.capacity()<<endl;
for(int i = 0; i < arr.length(); i++)
cout<<"arr []:"<<arr[i].number<<endl;
cout<<"*********"<<endl;
return 0;
}
运行如下所示:
可以看到我们resize(13)后,由于 resize长度大于当前arr的length,所以则调用默认构造函数来填充内部数组.所以arr[10]至arr[12]的number为0。
总结
本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注编程宝库的更多内容!
1.栈的介绍栈的实现方式分为3种基于静态数组实现,内部预设一个很大的数组对象, 实现简单，缺点是空间受限。基于动态数组实现,内部预设一个容量值,然后分配一段内存空间数组,如果入栈大于默认容量值时 ...