STL模拟实现—vector

STL模拟实现—vector

引言：本篇文章主要是模拟实现vector，但不同于stl中vector的成员变量都是迭代器，这个自定义的vector是一个T* 的数据变量和一个int类型的size和int类型的capacity。（有时间再写三个迭代器的版本吧！）

首先来看一下vector的结构 :

start、finish、end_of_storage都是迭代器，也就对应vector类的三个成员变量

 本篇实现的自定义vector类实现了如下功能：

• 类模板vector的定义：模板类vector拥有构造函数、析构函数、拷贝构造函数、赋值运算符重载，以及其他一些成员函数。
• 构造函数：默认构造函数创建一个空的向量。带有两个参数的构造函数创建一个具有指定大小和初始值的向量。
• 析构函数：释放内存并将大小和容量重置为0。
• 成员函数size()和capacity()：分别返回向量的大小和容量。
• 成员函数push_back()：将元素添加到向量的末尾。如果向量已满，则自动扩容。
• 成员函数reserve()：为向量分配指定的容量大小。
• 重载运算符[]：通过下标访问向量中的元素。
• 成员函数begin()和end()：返回迭代器的起始和结束位置。
• 成员函数insert()和erase()：在指定位置插入或删除元素。
• 成员函数find()：在指定范围内查找元素，并返回迭代器。

 下面是代码：

 my_vector.h

#pragma once
#include <iostream>
#include <assert.h>using std::cout;  
using std::endl;template <class T> //模板类声明
class vector{
public:vector(); //默认构造函数~vector(); //析构函数vector(const vector& v); //拷贝构造函数vector& operator=(vector v); //赋值运算符typedef T* iterator; //迭代器类型定义typedef const T* const_iterator; //常量迭代器类型定义vector(size_t n,const T& val); //构造函数,用n个val初始化size_t size()const; //返回大小size_t capacity()const; //返回容量void push_back(const T& val); //尾部插入元素void reserve(size_t n); //容量预留T& operator[](size_t n); //下标访问运算符const T& operator[](size_t n)const; //常量版本下标访问运算符iterator begin(); //返回开始迭代器iterator end(); //返回结束迭代器const_iterator begin()const; //返回常量开始迭代器const_iterator end()const; //返回常量结束迭代器iterator insert (iterator position, const T& val); //迭代器版本插入iterator insert (int position,const T& val); //整数位置版本插入  iterator erase (iterator position); //迭代器版本删除iterator erase (int position); //整数位置版本删除iterator find (iterator _begin,iterator _end,const T& val); //查找元素private:T* _data; //内部存储空间指针size_t _size; //当前大小 size_t _capacity; //当前容量
};

 my_vector.cpp

#include "my_vector.h"
template<class T>
vector<T>::vector():_data(nullptr),_size(0),_capacity(0)
{}
template <class T>
vector<T>::~vector(){delete [] _data;_size = 0;_capacity = 0;
}
//构造器—开辟n个val的数组
template<class T>
vector<T>::vector(size_t n,const T& val){_data = new T[n];for(size_t i = 0; i<n;i++){_data[i] = val;}_size = n;_capacity = n;
}template<class T>
size_t vector<T>::size()const{return _size;
}template<class T>
size_t vector<T>::capacity()const{return _capacity;
}template <class T>
void vector<T>::reserve(size_t n){if(n==0)return;T* tmp = new T[n];for(size_t i =0;i<_size;i++){//深拷贝tmp[i] = _data[i];}delete []_data;_data = tmp;_capacity = n;
}template<class T>
void vector<T>::push_back(const T& val){if(_size == _capacity){//扩容_capacity = _capacity == 0?2:(_capacity*1.5);reserve(_capacity);}_data[_size] = val;_size++;}template <class T>
T& vector<T>::operator[](size_t n){assert(n<_size);//断言n要小于sizereturn _data[n];
}
template<class T>
const T& vector<T>::operator[](size_t n)const{assert(n<_size);return _data[n];
} 
template <class T>
typename vector<T>::iterator vector<T>::begin(){//定义时需要加上 typename 告诉编译器这是一个类型，因为这个类型是我们typedef出来的 return _data;
}
template <class T>
typename vector<T>::iterator vector<T>::end(){return _data+_size;
}
template <class T>
typename vector<T>::const_iterator vector<T>::end()const{return _data+_size;
}template <class T>
typename vector<T>::const_iterator vector<T>::begin()const{return _data+_size;
}
template <class T>
vector<T>::vector(const vector& v){if(this == &v)return;//如果拷贝构造自己返回_data = new T[v._size];for(int i = 0;i<v._size;i++){_data[i]=v[i];}_capacity = v._size;_size = v._size;
}
template <class T>
vector<T>& vector<T>::operator=(vector v){
//赋值现代写法，利用传过来的值，拿临时变量v拷贝构造
//再交换他们的值，这个临时变量又会出作用域销毁_data = v._data;v._data = nullptr;_size = v._size;_capacity = v._capacity;return *this;
}
template <class T>
typename vector<T>::iterator vector<T>::insert (vector<T>::iterator position, const T& val){assert(position<=end());int pos = position -begin();if(_capacity == _size){//需要扩容_capacity = _capacity==0?2:(_capacity*1.5);reserve(_capacity);}position = begin()+pos;for(vector<T>::iterator it = end()-1;it>=position;it--){*(it+1)=*it;}*position = val;_size++;return position;
}
template <class T>
typename vector <T>::iterator vector<T>::insert(int position,const T& val){return insert(begin()+position,val);
}
template <class T>
typename vector<T>::iterator vector<T>::erase(vector<T>::iterator position){assert(position >= begin() && position < end());//迭代器不能大于或等于end()for(vector<T>::iterator it = position+1;it<=end();it++){*(it-1)=*it;}_size--;return position;
}
template <class T>
typename vector<T>::iterator vector<T>::erase(int position){return erase(begin()+position);
}
template <class T>
typename vector<T>::iterator vector<T>::find(vector<T>::iterator _begin,vector<T>::iterator _end,const T& val){if(_begin>=end() || _end<begin()) return nullptr;if(_begin<begin()) _begin=begin();//条件限制一下if(_end>=end()) _end = end()-1;for(vector<T>::iterator it = _begin;it<=_end;it++){if(*it == val) return it;//找到返回迭代器}return nullptr;
}

 main.cpp

#include "my_vector.cpp"
void test01(){
vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(5);v1.push_back(3);v1.push_back(100);cout<<v1[1]<<endl;for(auto& e : v1){cout<<e<<' ';}cout<<endl;cout<<v1.capacity()<<endl;vector<int> v2;v2 = v1;v2.insert(v2.begin()+2,1230);for(auto& e:v2){cout<<e<<' ';}cout<<endl;v2.erase(v2.end()-1);for(auto& e:v2){cout<<e<<' ';}cout<<endl;cout<<*(v2.find(v2.begin(),v2.end(),5))<<endl;
}
int main(){test01();
}

注意事项：

 1. mian.cpp中，需要包含的文件是my_vector.cpp，不能像一般那样包含my_vector.h

因为如果模板的声明和定义分别单独的放在.h和.cpp文件中，当要实例化一个模板时，编译器必须看到模板确切的定义，而不仅仅是它的声明。若在main()函数中包含.h文件，则编译器无法知道模板的确切定义，所以要在main()中包含.cpp文件，.cpp文件中又会包含.h文件，这样一来通过在main函数中包含.cpp文件就会将类的定义和声明都包含进来，编译器自然能找到模板的确切定义。

2. 深浅拷贝问题

 在上面的代码中，每次进行拷贝和移动时，都是经过for循环，一个个去拷到新数组中去的，并没有使用memset等函数，因为memset是以一个字节一个字节进行拷贝的，如果此时vector里面存放的是自定义类型的数据，就会出错。

3. 迭代器失效问题 

在my_vector.cpp中，insert函数如果不注意就会发生迭代器失效

如图：传进来的迭代器，如果进行扩容了，那么这个迭代器也就失效了，因为其指向的是旧空间的，而旧空间已经释放。 

所以，需要提前记录下迭代器与begin（）的距离，再到扩容后重新更新这个迭代器。

 总之：写模板类还是有点挑战的，需要多加练习！！