C++vector常用接口和模拟实现

C++中的vector是一个可变容量的数组容器，它可以像数组一样使用[]进行数据的访问，但是又不像C语言数组空间是静态的，它的空间是动态可变的。

在日常中我们只需要了解常用的接口即可，不常用的接口查文档即可。

1.构造函数

//空构造
vector()//拷贝构造
vector(const vector<T>& v)//构造并初始化n个val
vector(size_t n,const T& val = T())//使用迭代器初始化，这里写成模板
template<class InputIterator>
vector(InputIterator first, InputIterator last)

2.迭代器

对于vector的迭代器也可以看作是指针

//获取第一个位置数据的普通迭代器和const迭代器
iterator begin();
const_iterator begin() const;//获取最后一个位置数据的普通迭代器和const迭代器
iterator end();
const_iterator end() const;

3.空间管理

//获取元素个数
size_t size() const;//判断是否为空
bool empty() const;//改变大小并且初始化
void resize (size_type n, value_type val = value_type());//改变容量
void reserve (size_type n);

reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问 题。 resize在开空间的同时还会进行初始化，影响size。

4.增删改查

//尾插
void push_back (const value_type& val);//尾删
void pop_back();//在任意位置插入
iterator insert (iterator position, const value_type& val);//在任意位置删除
iterator erase (iterator position);//交换两组数据空间
void swap (vector& x);//[]重载
T& operator[](size_t pos)

这里需要了解一个问题就是迭代器失效的问题，对于vector而言，它的迭代器底层就是原生指针。因此迭代器失效的原因就是指针所指向的空间被销毁了，指向了一个已经被释放的空间。

    vector<int> v{1,2,3,4,5,6};auto it = v.begin();// 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容// v.resize(100, 8);// reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变// v.reserve(100);// 插入元素期间，可能会引起扩容，而导致原空间被释放// v.insert(v.begin(), 0);// v.push_back(8);

例如上面这些例子，他们都引起了底层空间的改变，就会导致it失效，如果在后面的代码中使用失效的迭代器就会导致程序崩溃。

要解决这个问题的方法也很简单，就是在修改之后重新赋值即可。

下面进行vector的模拟实现

	template<class T>class vector{public://vector的迭代器就是原生指针，这里写成模板的形式typedef T* iterator;typedef const T* const_iterator;//begin()相当于直接返回头指针iterator begin(){return _start;}const_iterator begin() const{return _start;}//end()相当于直接返回尾指针iterator end(){return _finish;}const_iterator end() const{return _finish;}//左闭右开//迭代器构造函数，这里写成模板支持更多类型template<class InputIterator>vector(InputIterator first, InputIterator last){while(first != last){push_back(*first);++first;}}//空构造函数vector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr){}//拷贝构造//不能使用memcpy，因为这是浅拷贝，很可能会造成内存泄漏vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){_start = new T[v.capacity()];//memcpy(_start, v._start, sizeof(T) * v.size());//这里与下面reserve是相同的问题for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];//如果是自定义类型，这里事实上调用的是自定义类型的赋值操作}//这里由于是原生指针，并且是顺序存储因此可以直接相加_finish = _start + v.size();_endofstorage = _start + v.capacity();}//初始化n个val的vector，这里可以复用resize()vector(size_t n,const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){resize(n, val);}//交换void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}//现代写法//这里使用传值方式传参是因为能够生成临时拷贝不会影响原数据//这里使用传引用返回是因为this出了作用域会销毁vector<T>& operator=(vector<T> v){swap(v);//相当于this->swap(v)return *this;}//析构~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}//reserve()空间管理，同样不能使用memcpy(),会导致内存泄漏void reserve(size_t n){if (n > capacity()){size_t sz = size();T* temp = new T[n];if (_start){//memcpy(temp, _start, sizeof(T) * size());for (size_t i = 0; i < sz; i++){temp[i] = _start[i];//如果是自定义类型，这里事实上调用的是自定义类型的赋值操作}delete[] _start;}_start = temp;//_finish = _start + size()这样写是错的。//由于_start的改变会导致size（）报错，这就是迭代器失效。//因为_start指向了新空间，但是_finish还是指向旧空间_finish = _start + sz;_endofstorage = _start + n;}}//申请n个空间初始化为val，这里复用reserve()void resize(size_t n,const T& val = T())//匿名对象{if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}//尾插，这里自己实现需要注意扩容，但是也可以考虑直接复用insert()void push_back(const T& x){//if (_finish == _endofstorage) //{//	//扩容//	size_t newcapacity = capacity() == 0 ? 4 : capacity() *2;//	reserve(newcapacity);//}//*_finish = x;//++_finish;insert(end(), x);}//这里与尾插是一样的思路void pop_back(){erase(end());}//获得当前容器的容量size_t capacity() const{return _endofstorage - _start;}//获取当前容器中有效数据的个数size_t size() const{return _finish - _start;}//重载[]，这里事实上相当于(*_start + pos)T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}//任意位置插入，需要注意迭代器失效的问题void insert(iterator pos ,const T& x){assert(pos >= _start && pos <= _finish);if (_finish == _endofstorage){//扩容//这里如果直接扩容会引发迭代器失效，因为pos还是指向原来的位置//因此需要更新pos的位置,这里保存的时相对位置size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = x;++_finish;}//iterator erase(iterator pos)//{//	 //检查 pos 是否在合法范围内//	if (pos < _start || pos >= _finish)//	{//		throw std::out_of_range("Iterator out of range");//	}//	 //从删除位置开始，将后续所有元素向前移动一位//	iterator it = pos;//	while (it < _finish - 1)//	{//		*it = *(it + 1);//		++it;//	}//	 //更新 _finish，减少容器大小//	--_finish;//	 //返回删除位置的下一个有效迭代器//	return pos;  // 注意：这里返回的是删除位置的下一个迭代器//}//只要把pos位置后面的元素向前挪动覆盖即可，也不需要考虑迭代器失效的问题iterator erase(iterator pos){assert(pos >= _start && pos <= _finish);iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;++it;}--_finish;return pos;}private://定义头指针和尾指针以及一个管理空间的指针iterator _start;iterator _finish;iterator _endofstorage;};