【C++标准模版库】模拟实现vector+迭代器失效问题

一.vector成员变量

成员变量：

1. iterator _start：指向vector的起始位置。
2. iterator _finish：指向vector的最后一个有效数据的下一个位置。
3. iterator _end_of_storage：指向vector可容纳最大数据个数的下一个位置。

大体结构如下：

namespace xzy
{//有模版不能分离到.h与.cpp文件，否则报链接错误template<class T>class vector{public:typedef T* iterator;private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};
}

二.构造函数

1.无参（默认）构造

类内函数拷贝构造，系统就不再提供默认构造，无法vector<int> v; 需要自己提供默认构造，C++11中vector() = default; 强制生成默认构造。

//C++11 强制生成默认构造
//vector() = default;vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{}

2.有参构造

1. 迭代器区间构造：例如用list对象的迭代器区间构造vector对象。作用：例如由于list对象排序性能较低，利用vector的迭代器区间初始化list对象中相同的数据进行排序，可以提高性能。

//类模版的成员函数可以是函数模版
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);++first;}
}
int main()
{list<int> l1(10, 1); //数据类型要求匹配，例如：都是intvector<int> v1(l1.begin(), l1.end());
}

2. n个值为val初始化：

vector(size_t n, const T& val = T())
{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}

解决办法：

3.拷贝构造

1.传统写法

vector(const vector<T>& v)
{_start = new T[v.capacity()];//memmove(_start, v._start, v.size() * sizeof(T));for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();
}

更好的写法：遍历vector进行尾插。

vector(const vector<T>& v)
{reserve(v.size());for (auto& e : v){push_back(e);}
}

2.现代写法

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}vector(const vector<T>& v)
{vector<T> tmp(v.begin(), v.end());swap(tmp);
}

三.vector对象的容量操作

1.size

size_t size() const
{return _finish - _start;
}

2.capacity

size_t capacity() const
{return _end_of_storage - _start;
}

3.clear

void clear()
{_finish = _start;
}

4.empty

bool empty() const
{return _start == _finish;
}

5.reserve

扩容时：先开辟新空间，再将旧空间拷贝到空间，释放旧空间，最后修改数据。

但是这里存在一个坑，如下：

初始_start 和 _finish 为缺省值 nullptr。
_finish = _start + size() = _start + _finish - _start = _finish = nullptr——>程序崩溃。

正确代码如下：

void reserve(size_t n)
{//第一种解决方法//if (n > capacity())//{//	T* tmp = new T[n];//	memmove(tmp, _start, sizeof(T) * size());//	delete[] _start;//	_finish = tmp + size();//	_start = tmp;//	_end_of_storage = _start + n;//}//第二种解决方法//if (n > capacity())//{//	size_t old_size = size();//	T* tmp = new T[n];//	memmove(tmp, _start, sizeof(T) * size());//	delete[] _start;//	_start = tmp;//	_finish = _start + old_size;//	_end_of_storage = _start + n;//}//第三种解决方法if (n > capacity()){//先保存有效数据个数size_t old_size = size();//开空间T* tmp = new T[n];//拷贝数据for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}//释放旧空间delete[] _start;//更新数据_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;}
}

但是第一种与第二种方法在某些vector容器数据为自定义类型时存在浅拷贝问题如下图：

同理：拷贝构造使用的memmove也存在此问题。

6.resize

修改有效数据的个数时：若传入的参数小于有效数据的个数：删除数据即修改_finish即可；若传入的参数大于有效数据的个数：插入数据前考虑是否扩容。

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;}}
}

四.vector对象的访问及遍历操作

1.operator[]

T& operator[](size_t i)
{assert(i >= 0 && i < size());return _start[i];
}const T& operator[](size_t i) const
{assert(i >= 0 && i < size());return _start[i];
}

2.实现迭代器：begin+end

typedef T* iterator;
typedef const T* const_iterator;iterator begin()
{return _start;
}
iterator end()
{return _finish;
}const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}

五.vector对象的增删查改操作

1.operator

1.传统写法

vector<T>& operator=(const vector<T>& v)
{if (this != &v){delete[] _start;_start = new T[v.capacity()];//memcpy(_start, v._start, v.size() * sizeof(T)); //当vector<string>时存在问题for(size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}return *this;
}

更好的写法：遍历vector进行尾插。

vector<T>& operator=(const vector<T>& v)
{if (this != &v){clear();reserve(v.size());for (auto& e : v){push_back(e);}}return *this;
}

2.现代写法

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}//类内可以用类名替代类型：vector& operator=(vector tmp)
vector<T>& operator=(vector<T> tmp)
{swap(tmp);return *this;
}

2.push_back

尾插时：先检查容量，再进行尾插。

void push_back(const T& x)
{//容量满了——>扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());}//尾插*_finish = x;++_finish;
}

3.pop_back

尾删时：先检查是否有有效数据，再进行尾删。

void pop_back()
{assert(!empty());--_finish;
}

4.insert

插入时：先检查容量，再整体右移一位，最后插入。

迭代器失效：类似野指针

实现插入操作有一个坑造成迭代器失效问题，如下图：

修改后的代码能解决上面的问题，但是又存在另一个迭代器失效的问题，如下图：

迭代器失效：位置意义改变

由于不知道insert函数内是否存在扩容，不能确保pos是否为野指针，解决方法：可以在insert函数中返回pos用于接受。代码如下：

iterator insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);//容量满了——>扩容if (_finish == _end_of_storage){//记录pos的相对位置防止迭代器失效size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}//整体后移一位iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}//插入数据*pos = x;++_finish;return pos;
}

5.erase

同理erase也会遇到的迭代器失效：位置意义改变，在vs2022中的vector（SLT）不接收erase的返回值强行访问，程序崩溃。接收erase的返回值访问，程序正常运行。

iterator erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;return pos;
}

实现删除vector中的偶数：

int main()
{std::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){it = v1.erase(it);}else{it++;}}return 0;
}

六.源代码

1.vector.h

//#pragma once#ifndef __VECTOR_H__
#define __VECTOR_H__#include<iostream>
#include<assert.h>
using namespace std;namespace xzy
{//有模版不能分离到.h与.cpp文件，否则报链接错误template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//C++11 强制生成默认构造//vector() = default;vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}vector(const vector<T>& v){_start = new T[v.capacity()];//memmove(_start, v._start, v.size() * sizeof(T)); //当vector<string>时存在问题for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}/*vector(const vector<T>& v){reserve(v.size());for (auto& e : v){push_back(e);}}*///类模版的成员函数可以是函数模版template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}void clear(){_finish = _start;}//vector<T>& operator=(const vector<T>& v)//{//	if (this != &v)//	{//		delete[] _start;//		_start = new T[v.capacity()];//		//memcpy(_start, v._start, v.size() * sizeof(T));//当vector<string>时存在问题//      for(size_t i = 0; i < v.size(); i++)//        {//			  _start[i] = v._start[i];//        }//		_finish = _start + v.size();//		_end_of_storage = _start + v.capacity();//	}//	return *this;//}//vector<T>& operator=(const vector<T>& v)//{//	if (this != &v)//	{//		clear();//		reserve(v.size());//		for (auto& e : v)//		{//			push_back(e);//		}//	}//	return *this;//}void swap(vector<int>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}类内可以用类名替代类型：vector& operator=(vector tmp)vector<T>& operator=(vector<T> tmp){swap(tmp);return *this;}~vector(){if (_start != nullptr){delete[] _start;}_start = _finish = _end_of_storage;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//以下有一个坑//void reserve(size_t n)//{//	if (n > capacity())//	{//		//开空间//		T* tmp = new T[n];//		//拷贝数据//		memmove(tmp, _start, sizeof(T) * size());//		//释放旧空间//		delete[] _start;//		//更新数据//		_start = tmp;//		_finish = _start + size(); 注意：size()已经不再是有效数据个数了，可以通过调试观察//		_end_of_storage = _start + n;//	}//}void reserve(size_t n){//第一种解决方法：依旧存在错误//if (n > capacity())//{//	T* tmp = new T[n];//	memmove(tmp, _start, sizeof(T) * size());//	delete[] _start;//	_finish = tmp + size();//	_start = tmp;//	_end_of_storage = _start + n;//}//第二种解决方法：依旧存在错误/*if (n > capacity()){size_t old_size = size();T* tmp = new T[n];memmove(tmp, _start, sizeof(T) * size());delete[] _start;_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;}*///第三种解决方法if (n > capacity()){//先保存有效数据个数size_t old_size = size();//开空间T* tmp = new T[n];//拷贝数据for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}//释放旧空间delete[] _start;//更新数据_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;}}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;}}}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}void push_back(const T& x){//容量满了——>扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());}//尾插*_finish = x;++_finish;}bool empty(){return _start == _finish;}void pop_back(){assert(!empty());--_finish;}//void insert(iterator pos, const T& x)//{//	//容量满了——>扩容//	if (_finish == _end_of_storage)//	{//		reserve(capacity() == 0 ? 4 : 2 * capacity());//	}//	//整体后移一位//	iterator end = _finish;//	while (end > pos)//	{//		*end = *(end - 1);//		--end;//	}//	//插入数据//	*pos = x; //pos为野指针，迭代器失效//	++_finish;//}iterator insert(iterator pos, const T& x){//容量满了——>扩容if (_finish == _end_of_storage){//记录pos的相对位置防止迭代器失效size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}//整体后移一位iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}//插入数据*pos = x;++_finish;return pos;}iterator erase(iterator pos){iterator it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;return pos;}T& operator[](size_t i){assert(i >= 0 && i < size());return _start[i];}const T& operator[](size_t i) const{assert(i >= 0 && i < size());return _start[i];}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};
}#endif