【C++】模拟实现vector

文章目录

前言
成员变量 & 迭代器
- 反向迭代器
空间管理函数
成员函数
- 构造函数
- - 默认构造
  - 拷贝构造
- 析构函数
- 赋值操作符重载
元素访问
元素修改
- 迭代器失效问题
- 模拟实现
总结

前言

模拟实现不是为了写得和库里面一样好。而是为了更好的了解底层，从而能够更熟练的使用这些类，同时也能学习大佬们的代码风格。

由于前面模拟实现过了string类，所以在实现vector时，有些地方就不细说了。
因为vector可以存放多种类型，所以在模拟实现时我会利用模板来实现。

vector （向量）是 C++ 标准库中的一种动态数组类型，具有以下一些特点：

动态增长：可以根据需要自动增长容量。
随机访问：可以通过索引快速访问元素。
存储在连续内存中：元素在内存中是连续存储的。
高效的插入和删除操作：在尾部进行插入和删除操作效率较高，但在其他位置插入和删除可能效率较低。

成员变量 & 迭代器

因为vector的底层物理结构是连续的，所以我们可以直接用原生指针来充当它的迭代器。并且，我们可以直接利用迭代器，来记录并修改容器内的元素。

template <class T>
class vector
{typedef T* iterator;typedef const T* const_iterator;
private:iterator _start = nullptr;      // 用来记录起始位置 iterator _finish = nullptr;     // 用来记录有效数据末尾的下一个位置iterator _end_of_storage = nullptr;  // 用来记录有效空间的末尾的下一个位置
};

那么关于迭代器的begin和end函数就可以通过以下实现


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

反向迭代器

在这里插入图片描述
在模拟string章节对反向迭代器详细的说过了，这里就不做过多赘述。但这里我有一点需要说一下，我在模拟string那个章节说过，string和vector的反向迭代器我会使用同一串代码。在string中，由于我们不会用string来存储一个自定义类型，所以不会用到->操作符重载。但是在vector中，可能会存储一些自定义类型，所以需要我们需要对反向迭代器重载->操作符，就需要用到第二个模板参数了。

template<class Iterator, class Reference, class Point>
struct __random_reverse_iterator
{typedef __random_reverse_iterator self;__random_reverse_iterator(const Iterator& it):_cur(it){}Reference operator*(){Iterator tmp = _cur;return *(--tmp);}Point operator->(){return &(this->operator*());}self& operator++(){--_cur;return *this;}self operator++(int){self tmp = *this;--_cur;return tmp;}self& operator--(){++_cur;return *this;}self operator--(int){self tmp = *this;++_cur;return tmp;}self& operator+=(int nums){_cur -= nums;return *this;}self& operator-=(int nums){_cur += nums;return *this;}bool operator!=(const self& it){return _cur != it._cur;}bool operator==(const self& it){return _cur == it._cur;}
private:Iterator _cur;
};template<class T>
class vector
{
public:typedef __random_reverse_iterator<iterator, T&, T*> reverse_iterator;typedef __random_reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}
}

我写了一个测试用例来看一下我们重载的->操作符：

int main()
{struct AA{int _a;int _b;};hyt::vector<AA> myvector(5);  // 5 default-constructed intsint i = 0;hyt::vector<AA>::reverse_iterator rit = myvector.rbegin();for (; rit != myvector.rend(); ++rit)rit->_a = rit->_b = ++i;std::cout << "myvector contains:";for (hyt::vector<AA>::iterator it = myvector.begin(); it != myvector.end(); ++it)std::cout << ' ' << it->_a << ":" << it->_b;std::cout << '\n';return 0;
}

运行结果如下：
在这里插入图片描述

空间管理函数

在这里插入图片描述
在模拟string中，我模拟实现reserve是使用了strcpy，因为string管理的每个元素都是char类型，可以直接拷贝过去。但是vector可能会管理一些涉及到资源管理的类型，所以在实现reserve函数的时候，需要注意以下几点：

如果扩容了，我们需要更改_star 和 _finish ，所以我们需要先确定他们之间的间隔距离。
需要将原空间的值复制到新扩容的空间，这里不能使用memmove等类似的函数来进行拷贝
这里涉及到一个浅拷贝的问题（如果vector中存放的是内置类型（除了指针），是可以使用memmove来进行拷贝的，但如果vector里面存放的是一些涉及到资源管理的类型时，这样做就会发生问题，假设vector里面存放一个string）

所以如果我们要拷贝原空间的内容，就可以去调用string类中的赋值操作符重载，来对string类进行深拷贝。具体操作如下：

	void reserve(size_t n){if (n > capacity()){size_t len = _finish - _start;T* tmp = new T[n];if (_start){for (size_t i = 0;i < len;++i)*(tmp + i) = *(_start + i);delete[] _start;}_start = tmp;_finish = _start + len;_end_of_storage = _start + n;}}void resize(size_t n, T val = T()){// 不考虑缩容if (n + size() > capacity())reserve(n);for (size_t i = size();i < n;++i)*(_start + i) = val;_finish = _start + n;}bool empty() const{return _finish == _start;}inline size_t capacity() const{return _end_of_storage - _start;}inline size_t size() const{return _finish - _start;}

成员函数

构造函数

默认构造

	vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}

拷贝构造

这里与上面实现reserve的情况是一样的，不能使用memmove来拷贝数据。具体原因上面已经分析过了，所以这里就不再过多赘述，关于开辟空间问题，我们可以复用上面写的reserve函数，然后再将需要拷贝的数据一个一个的尾插到新开辟空间中。

	vector(const vector<T>& x){size_t _capacity = x.capacity();reserve(_capacity);for (size_t i = 0;i < x.size();++i){push_back(x[i]);}}

析构函数

	~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}

赋值操作符重载

我们通过上面，知道了涉及拷贝的操作，都需要好好分析是否会发生意外。

	vector& operator=(const vector<T>& x){if (&x != this){delete[] _start;size_t len = x.size();T* tmp = new T[x.capacity()];_start = tmp;_finish = _start;for (size_t i = 0;i < len;++i)push_back(x[i]);_end_of_storage = _start + x.capacity();}return *this;}

这里可以写一个现代写法（这个写法的原理在模拟实现string的时候讲过，所以这里就不多说了）：

vector& operator=(const vector<T>& x)
{if (&x != this){vector<T> tmp = x;swap(tmp);}return *this;
}

元素访问

在这里插入图片描述

因为vector底层物理空间是连续的，所以可以支持随机访问（[]）

	T& operator[] (size_t n){assert(n < size());return *(_start + n);}const T& operator[] (size_t n) const{assert(n < size());return *(_start + n);}iterator& front(){return _start;}const_iterator& front() const{return _start;}iterator& back(){return _finish - 1;}const_iterator& back() const{return _finish - 1;}

元素修改

在这里插入图片描述

迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。
对于vector可能会导致其迭代器失效的操作有：

会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。

#include <iostream>
using namespace std;
#include <vector>
int main()
{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);// 给vector重新赋值，可能会引起底层容量改变v.assign(100, 8);/*出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃。解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新赋值即可。*/while (it != v.end()){cout << *it << " ";++it;}cout << endl;return 0;
}

指定位置元素的删除操作— erase

#include <iostream>
using namespace std;
#include <vector>
int main()
{int a[] = { 1, 2, 3, 4 };vector<int> v(a, a + sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvector<int>::iterator pos = find(v.begin(), v.end(), 3);// 删除pos位置的数据，导致pos迭代器失效。v.erase(pos);cout << *pos << endl; // 此处会导致非法访问return 0;
}

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。

⭐️：迭代器失效解决方法：在使用之前，对迭代器重新赋值即可

模拟实现

	void push_back(const T& val){if (size() == capacity()){size_t _capacity = capacity();size_t newcapacity = _capacity == 0 ? 4 : 2 * _capacity;reserve(newcapacity);}*(_finish++) = val;}inline void pop_back(){--_finish;}inline void clear(){_finish = _start;}void swap(vector& x){std::swap(_start, x._start);std::swap(_finish, x._finish);std::swap(_end_of_storage, x._end_of_storage);}iterator insert(iterator position, const T& val){size_t len = 0, gap = 0;iterator tmp = position;while (tmp != end())++len, ++tmp;iterator start = _start;  while (start != position)  // 记录迭代器位置,以免扩容时发生迭代器失效gap++, start++;if (size() == capacity()){size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);position = _start;for (size_t i = 0;i < gap;++i)++position;}iterator cur = end() + 1;while (cur > position){*cur = *(cur - 1);--cur;}*position = val;++_finish;return position;}iterator erase(iterator position){assert(begin() != end());assert(position < end());iterator cur = position;while (cur < end() - 1){*cur = *(cur + 1);++cur;}--_finish;return position;}void assign(int n, const T& val){delete[] _start;_start = _finish = _end_of_storage = nullptr;resize(n, val);}

总结

以下是我自己模拟实现的一个vector类：My_vector