当前位置：首页 > news >正文

vector的模拟实现

news 来源：原创 2025/9/17 9:05:05

一、构造和析构函数

二、插入删除访问迭代器

三、迭代器失效

四、拷贝构造和赋值

五、tip

一、构造和析构函数

namespace stn
{template<class T>class vector{typedef T* iterator;public:vector():_start(nullptr);, _end(nullptr), _endofstorage(nullptr){	}~vector(){delete[]_start;_start = _finish = _endofstorage = nullptr;}private:iterator _start;iterator _finish;iterator _endofstorage;};
}

start相当于迭代器的begin，finish相当于size的位置，endofstorage相当于end

二、插入删除访问迭代器

		void push_back(const T& x){if (_finish == _endofstorage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;T* tmp = new T[capacity];if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;_finish = _start + size();_endofstorage = _start + newcapacity;}*_finish = x;++_finish;}size_t capacity(){return _endofstorage - _start;}size_t size(){return _finish - _start;}

当空间不够的时候我们就需要开辟新空间，然后把旧空间的数据拷贝过去然后释放旧空间

我们运行以后就会发现这个代码是有错误的，原因就出在_finish上，start我们已经指向了新空间，但是你finish还是旧空间的finish，通俗的来讲，你start+size()，最后得到的是旧空间的finish那你新空间使用旧空间的finish肯定是不行的，所以这里我们要改成使用新空间的start也就是tmp，而且size我们需要的是旧空间的size，所以_start得放在下面

	_finish =tmp+ size();_start = tmp;_endofstorage = _start + newcapacity;

改进成这样子就可以了

这个是访问

	T& operator[](size_t pos){assert(pos < size());return  _start[pos];}

我们再搞一下迭代器

	iterator begin(){return _start;}iterator end(){return _finish;}

vector<int>::iterator it = v.begin();
while (it != v.end())
{cout << *it << " ";++it;
}cout << endl;
for (auto e : v)
{cout << e << " ";
}

注意这里的iterator要把它放到公有的要不然不能够进行访问

既然有了普通迭代器可读可写自然也要有不能被修改的迭代器const迭代器

	typedef T* const_iterator;

const_iterator begin()const
{return _start;
}
const_iterator end()const
{return _finish;
}

指向的内容不能被修改

	const T& operator[](size_t pos)const{assert(pos < size());return  _start[pos];}

三、扩容删除逻辑

		void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t sz = size();if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_finish = tmp + sz;_start = tmp;_endofstorage = _start+n;}}

写了reserve我们的pushback就可以去根据reserve的逻辑去搞了

void push_back(const T& x)
{if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}

resize我们参照一下库里面的写法

value_type就是T，

/*void resize(size_t n, T val = T())*/
void resize(size_t n,const T& val = T())

可以写这两种写法，有人说为什么不同0来充当缺省值，因为T是模板，在不同的环境下就需要不同的缺省值，比如你是指针我们就给空指针，匿名对象的本质就是去走初始化列表进行构造，我去构造出一个空指针或者int或者什么的就可以适用于各种类型，有人说int是内置类型怎么能走构造，因为c++官方为了让这种东西进行通用进行了升级，这两种写法本质上都是一样的，const&会延长匿名对象的生命周期

int j(1);
cout << j << endl;

我这样子初始化都是可以的

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

小了就删除，大了话我们直接reserve反正没有大于capacity的话reserve也不会起到作用，超过的话就执行扩容加插入

	vector<string> v;v.resize(10, "x");for (auto e : v){cout << e << " ";}

这里是单参数的构造支持隐式类型的转换

三、迭代器失效

void insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;
}

这里等于的原因是走到pos位置你还要把pos这个位置向后挪动才算结束

我们插入的时候发现会有随机值

这是怎么回事呢

我们pos在移动的过程中倘若空间不够发生了扩容，其他的变量都移到新空间去了，但是pos随着旧空间一起释放掉了，所以我们的pos也要随着新空间的改变而改变，还要记录下原本空间pos相对于start的相对位置

void insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;
}

那我们用pushback复用一下这个吧

void push_back(const T& x)
{insert(end(), x);}

	auto it = v.begin() + 1;v.insert(it, 30);

这里的it也会失效，因为it是传值pos的改变不会影响it ，所以我们认为insert插入后it就失效了，不能访问，有人说引用可不可以，库里面是没有的

我们也会发现是编译不过的，因为引用要的是变量，如果说我们这里传的是V.begin()，这个东西返回的是临时对象，而临时对象具有常性，所以说我们不要用这种东西，用传值拷贝就好了

那我们再来看一下erase

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

这个跟上面差不多我就不多过阐述了

我们来看一下erase的迭代器失不失效

迭代器失效：

如果失效就不能在使用这个迭代器，如果使用了结果是未定义的

大家可能都认为这个是不失效的，但是这个其实是失效的，一般场景下不会，但是有一个场景会

void testvector4()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);auto it = v.begin();while (it != v.end()){if (*it % 2 == 0){v.erase(it);}it++;}
}

当我们要删除偶数的时候迭代器就会失效

第一种情况下加到2了以后3往前挪，，指针到4了，3这个我们就没有进行一个很好的判断

第二种情况当最后一个是偶数的时候就想图中所写一样

所以vs2019进行强制检查，erase以后认为it失效了，不能访问，访问就报错

那我们看一下库里面的做法

这段话的意思是erase返回的是被删除位置的下一个位置

auto it = v.begin();
while (it != v.end())
{if (*it % 2 == 0){it= v.erase(it);}elseit++;
}

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

所以我们把返回值改变一下就可以了

结论：insert和erase以后迭代器都失效了，不能再访问

我们再来看下一段测试

	void testvector5(){vector<string> v;v.push_back("1111111111111111111");v.push_back("1111111111111111111");v.push_back("1111111111111111111");v.push_back("1111111111111111111");v.push_back("1111111111111111111");for (auto e : v){cout << e << " ";}}
}

会出现这个问题，为什么呢

这里就涉及到一个深层次的浅拷贝的问题，memcpy把里面的东西_start指向的东西全都拷贝下来，但是string里面指向的东西没有改变也拷贝了下来，到时候你释放旧空间的时候就会先把指向的东西里面给清除掉，我们拷贝下来的就变成了野指针了，所以就不能使用memcpy这个东西，我们用一个循环慢慢拷贝就好了

	void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t sz = size();if (_start){for (int i = 0; i < size(); i++){tmp[i] = _start[i];}delete[] _start;}_finish = tmp + sz;_start = tmp;_endofstorage = _start + n;}}

[]拷贝值的时候传回来的是引用，你tmp就是复制

我来阐述一下用memcpy的时候它就相当是被动的被它拷贝下去，而用循环赋值就是复制下去，string会主动分配一块新的内存给指向的内容两个已经存在的对象只能用赋值，调用的是自定义类型的赋值重载

四、拷贝构造和赋值

vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(capacity());for (auto& e : v){push_back(e);}
}

这里const对象不能调用非const成员函数

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

所以这里也要稍作修改

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}
vector<T>& operator=(vector<T> tmp)
{swap(tmp);return *this;
}

这里看不懂的可以去看一下我之前写的string的模拟实现

比如说你v1=v3，this就是v1，tmp就是v3的拷贝，你把自己的丢给tmp，把v3里面要的东西拿过来，顺便让tmp帮自己释放一下

五、tip

看最后一行跟我们写的不太一样这也是设计不太合理的地方

void swap(vector<T>& v)
void swap(vector& v)

你写成这样也是可以的，是类名也是类型

template <class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);
++first;}
}

我们不是有各种各样的迭代器区间吗，写成类模板就可以使用各种各样的迭代器

那我们内置类型编译器不确定一定会处理所以我们改一下

vector()
{
}

iterator _start=nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;

上面那个一定要写，我们不写编译器会生成默认的拷贝构造，但是我们还写了其他的很多构造，原始构造也要有

这种情况下就会出问题，因为它会去找最匹配的，而左边的明显比右边匹配所以我们还要写一个模板出来应对这种情况

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

vector就到这里结束了，接下来进入链表的部分，写的不好的地方欢迎大家指出

一、构造和析构函数

二、插入删除访问迭代器

三、迭代器失效

四、拷贝构造和赋值

五、tip

相关文章：