C++——vector类及其模拟实现

其他
2025-07-22 07:30:01

前言：前边我们进行的string类的方法及其模拟实现的讲解。这篇文章将继续进行C++的另一个常用类——vector。

一.什么是vector

vector和string一样，隶属于C++中STL标准模板库中的一个自定义数据类型，实际上就是线性表。两者之间有着很多相似，甚至相同的方法。

但是它们也有着很大的不同：因为vector是线性表，所以他可以存储任意类型的数据，甚至是自定义类型的数据，包括vector本身。

二.vector基本框架 #include<assert.h> namespace Myvector { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; //构造函数 voctor() {} //析构函数 ~voctor() { delete[] _start; _strat = _finish = _endofstorage = nullptr; } //迭代器 iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } //数据个数 size_t size() const { return _finish - _start; } //空间大小 size_t capacity() const { return _endofstorage - _start; } //[]运算符重载 T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; } private: iterator _start = nullptr; iterator _finish = nullptr; iterator _endofstorage = nullptr; }; }

因为vector允许定义不同类型的数据，所以我们要使用模版来定义类。

值得注意的是，在voctor中我们不用传统的size和capacity来定义数据个数和总空间大小，而是都将它们定义为指针类型，通过指针间的相减来得到size和capacity。初始情况下三者均为空指针。

同时我们将T*指针类型重定义为iterator，这是因为vector的本质就是数组，其迭代器就是指针。

三.vector常用操作 1.扩容

扩容分为两种方式，只扩容不初始化的reserve，以及扩容并且初始化的resize调整：

//扩容 void reserve(size_t n) { if (n > capacity()) { size_t old_size = size(); T* tmp = new T[n]; //memcpy(tmp, _start, sizeof(T) * size()); for (size_t i = 0; i < old_size; i++) { tmp[i] = _start[i]; } delete[] _start; _start = tmp; _finish = old_size + tmp; _endofstorage = tmp + n; } }

扩容较为简单，值得注意的是这里不在使用strcpy，而是通过for循环的方式进行赋值。

//调整 void resize(size_t n,const T& val = T()) { if (n > size()) { reserve(n); while (_finish < _start + n) { *_finish = val; _finish++; } } else { _finish = _start + n; } }

对于resize，因为我们需要使用缺省参数，但是由于vector的对象类型不定，甚至是自定义类型，所以我们不能使用0作为缺省参数，而应使用匿名对象作为参数，让匿名对象去自动识别类型并调用自己的构造函数形成初始值。

2.插入

先来看尾插，与string类似，需要考虑扩容：

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

测试如下：

在来看指定位置的插入，先判断pos是否合法，同样需要判断扩容：

//指定位置插入 void insert(iterator pos, const T& val) { assert(pos >= _start); assert(pos < _finish); if (_finish == _endofstorage) { size_t len = pos - _start; reserve(capacity() == 0 ? 4 : capacity() * 2); //扩容要更新pos pos = _start + len; } iterator it = _finish - 1; while (it >= pos) { *(it + 1) = *it; --it; } *pos = val; _finish++; }

这个指定的位置pos用迭代器比用数字更加方便进行比较，所以建议直接使用迭代器进行插入。

有一点值得注意的是，传入的pos是指向原数组的，如果进行了扩容，那么原数组被销毁，所有的指针都指向新的数组，所以也需要对pos指针进行更新，否则pos就会成为野指针。

测试如下：

3.遍历

除了上边的for循环遍历外，我们还可以通过迭代器和范围for进行遍历：

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

测试如下：

4.删除

首先来看尾删，和顺序表一样，尾删就直接让_finish减1即可，还要注意判断是否为空：

//判空 bool empty() { return _start == _finish; } //尾删 void pop_back() { assert(!empty()); --_finish; }

测试如下：

再来看指定位置的删除：

//指定位置删除 void erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); iterator it = pos + 1; while (it < _finish) { *(it - 1) = *it; it++; } _finish--; }

测试如下：

5.交换

想要实现两个对象之间的交换，其底层实现还是要借助std库中的swap函数：

//交换 void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); }

测试如下：

6.赋值

使用容器的一种必不可少的方法就是相同类型的对象之间的赋值，这就关系到类中的拷贝构造函数了。

我们知道拷贝构造分为浅拷贝和深拷贝，后者要关系到指针，显然，voctor类型对象的成员变量都是指针，所以我们必须写出深拷贝构造函数：

//拷贝构造函数 vector(const vector<T>& v) { reserve(v.capacity()); for (auto& e : v) { push_back(e); } }

这里我们采用了先开空间，在依次尾插的方式来实现拷贝构造函数，测试如下：

还可以使用“=”运算符重载的方式进行赋值：

//=运算符重载 vector<T>& operator=(vector<T> v) { swap(v); return *this; }