? ? ? ? 这次我们来分析STL Vector的实现原理。上次对List的分析并不成功,因为直接阅读源码要理解大量繁琐的STL规定的协议或模式,很影响对代码本身的阅读。所以这次我打算直接抛弃那些内容,直接用更简洁更直观的方式编写一个vector。这样虽然没有STL源码那样规范与标准,其结构的精髓也可以得到很好的理解。
目录
基本结构
内置方法
重载运算符
基本结构
? ? ? ? 相比于List,vector是一个简单的顺序表结构。如图可以生动地展示一个vector所占用的存储空间。其中蓝色的部分代表已经赋值的部分。在values指针所控制的一组空间中,size代表当前已经存取的数据量,capacity代表当前vector可以存取的最大数据量。
#ifndef MYVECTOR_H
#define MYVECTOR_H
//防止头文件的重复包含和编译
using namespace std;
template<typename T>
class Myvector{
private:
T *_values; //存储数组内容
int _capacity; //存储数组的最大容量
int _size; //存储数组当前已经占用的容量
? ? ? ? 其中的#ifndef MYVECTOR_H是用来避免头文件的重复包含和编译的。例如在一个大型的项目中,同一个头文件可能会被多次声明,此时可能会出现错误。#ifndef xxx_H相当于一个判断语句,判断xxx_H头文件是否已经被声明,如果尚未被声明就返回false,进而执行后续的#define语句。否则就放弃声明。在头文件的结尾我们可以看到#endif语句,与本处的#ifndef相对应。
内置方法
? ? ? ? 这里实现了几个常用的vector方法。
public:
void resize(int newsize){//用来重置vector的大小
int *newvalues=new T[newsize];//开辟一个新的空间
for(int i=0;i<_size;i++){
newvalues[i]=_values[i];//将旧空间中的数值赋到新的空间
}
delete[] _values;
_values=newvalues;
_capacity=newsize;
}
Myvector(){ //没有参数的构造函数
_values=new T[10]; //初始化大小为10
_capacity=10;
_size=0;
}
Myvector(int needsize){ //指定大小的构造函数
_values=new T[needsize]; //初始化大小为10
_capacity=needsize;
_size=0;
}
~Myvector(){ //析构函数
delete[] _values;
}
void push_back(T x){ //插入一个元素
if(_size==_capacity){//vector已满,为vector扩容
resize(_capacity*2);
}
_values[_size]=x;
_size++;
}
T pop_back(){ //弹出尾部元素
if(_size==0) throw "Vector is empty!\n";//如果vector已经为空,抛出错误
T popedValue=_values[_size-1];
_size--;
return popedValue;//返回被弹出的值
}
T front(){ //查看最后一个元素
return _values[_size-1];
}
int size(){ //查看vector当前大小
return _size;
}
? ? ? ? Vector中最为重要的就是其resize()方法的实现。可以看出,在每次调用resize()方法时,vector都需要额外申请一片额外的内存空间,然后对其重新赋值。这也就意味着vector在遇到需要扩容的情形时会格外的消耗时间与空间,所以在使用vector时应当尽量减少扩容的次数。在push_back()方法中,采用的策略是一旦遇到容量已满的情况,就将vector扩容为原来的两倍。
? ? ? ? ‘~’在构造函数之前表示析构函数。析构函数是一种与构造函数相反的函数。构造函数在对象生命周期的开始调用,而析构函数在对象生命周期的结束调用。所以析构函数通常用来对消亡的对象进行善后工作,比如释放其空间。这里的~Myvector()方法就是此功能。
重载运算符
? ? ? ? 与List不同的是,由于Vector占用的是一块连续的空间,所以大部分的运算符,比如++,--等完全可以正常使用。这里只重载了[]运算符,使得vector可以如同一个普通数组一样被随机存取,这也是list不能满足的要求。
T &operator[](int position){
return _values[position];
}
};
#endif //结束编译
? ? ? ? 至此,代码编写完毕,上面的代码可以组合成一个完整的简化版Vector容器。
|