【C++】—— vector模拟实现

vector 接口预览

namespace HL{template<class T>class vector{//迭代器iteratortypedef T* iterator;typedef const T* const_iterator;public://默认成员函数vector();vector(size_t n, const T& val = T());vector(int n, const T& val = T());vector(const vector& v);template<class InputIterator>vector(InputIterator first, InputIterator last);~vector();vector<T>& operator=(vector v);//Iteratoriterator& begin();iterator& end();const_iterator begin() const;const_iterator& end() const;//Capacitysize_t size() const;size_t capacity() const;bool empty() const;void reserve(size_t n);void resize(size_t n, const T& val = T());//Modifiersvoid push_back(const T& val);void pop_back();void insert(iterator pos, const T& val);template<class InputIterator>void insert(iterator pos, InputIterator first, InputIterator last);iterator erase(iterator pos);void swap(vector<T>& v);//Element access:T& operator[](size_t i);const T& operator[](size_t i) const;private:iterator start;iterator finish;iterator end_of_storage;};};

vector模拟实现

vector成员变量

​ vector成员变量，和顺序表的成员变量有所不同，不再是指针、size和capacity了，而是迭代器 start、finish和end_of_storage。

start指向起始位置、finish指向最后一个数据的下一个位置（表示数据的末尾）、end_of_storage指向这一块空间的最后。

默认成员函数

构造函数

1、无参构造

​ 无参构造，就是默认构造函数，将成员变量都初始化成nullptr。

vector():start(nullptr),finish(nullptr),end_of_storage(nullptr){}

2、构造并初始化成n个val值

​ 理论上，我们只需要写一个函数vector(size_t n, const T& val = T());即可，但是如果两个参数都是int类型，（即vector v(5,1);）编译器在编译时，认为T已经实例化成了int，对于两个int类型，编译器就会选择更为匹配的模版

template vector(InputIterator first, InputIterator last);

所以这里写一个vector(int n, const T& val = T()); 让上面这种情况匹配这个函数。

vector(size_t n, const T& val = T()){start = new T[n];for (size_t i = 0; i < n; i++){start[i] = val;}end_of_storage = finish = start + n;}vector(int n, const T& val = T()){start = new T[n];for (int i = 0; i < n; i++){start[i] = val;}end_of_storage = finish = start + n;}

3、使用一段迭代器区间进行初始化

​ 使用迭代器区间进行初始化，这里不一定是vector的迭代器，所以写成模板。

template<class InputIterator>vector(InputIterator first, InputIterator last){size_t sz = last - first;start = new T[sz];finish = start;while (first != last){*finish = *first;++finish;++first;}end_of_storage = start + sz;}

4、拷贝构造

​ 这里要注意，需要深拷贝，而不是浅拷贝。

vector(const vector& v){size_t sz = v.size();size_t cp = v.capacity();start = new T[sz];for (int i = 0; i < sz; i++){start[i] = v[i];}finish = start + sz;end_of_storage = start + cp;}

析构函数

​ 析构函数比较简单，释放动态开辟的空间即可。

~vector(){if (start)delete[] start;start = finish = end_of_storage = nullptr;}

赋值运算符重载

​ 赋值运算符重载，这个编译器自动生成的是浅拷贝，我们需要写一个深拷贝的。

这里有多种写法，首先就是传统写法，我们自己释放、开辟空间再拷贝数据

vector<T>& operator=(const vector& v){if (start)delete[] start;size_t sz = v.size();start = new T[sz];for (int i = 0; i < sz; i++){start[i] = v[i];}finish = end_of_storage = start + sz;}

​ 还有现代写法，我们这里传参不使用引用，而使用传值传参；这样生成的形参对象再与我们的this(对象)进行交换；这样形参出了作用域就自动调用析构函数，不用我们去处理了。（这个需要先实现交换函数）

vector<T>& operator=(vector v){swap(v);return *this;}

​ 注意事项： 在赋值的过程中没有使用memcpy函数，因为这个函数只是将数值拷贝过去(浅拷贝)；

如果我们vector 示例化是vector 这样的自定义类型，使用浅拷贝就可能会出现问题；所以这里采用一个一个进行赋值操作，这样就会去调用自定义类型的赋值运算符重载；而不只是简单的浅拷贝了。

iterator 迭代器

​ vector 的迭代器这里实现的是原生指针；迭代器相关函数：begin()、end()这些都比较简单就不过多描述了。

//迭代器iteratortypedef 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;}

Capacity

​ capacity容量相关的函数，主要在于调整空间大小和设置内容。

size、capacity、empty

size_t size() const{return finish - start;}size_t capacity() const{end_of_storage - start;}bool empty() const{return start == finish;}

reserve

​ reserve，调整空间大小；即扩容。

void reserve(size_t n){if (n > capacity()){iterator tmp = T[n];size_t sz = size();for (int i = 0; i < sz; i++){tmp[i] = start[i];}if (start)delete[] start;start = tmp;finish = start + sz;end_of_storage = start + n;}}

resize()

void resize(size_t n, const T& val = T()){reserve(n);if (n < size()){finish = start + n;}else {for (int i = size(); i < n; i++){start[i] = val;}finish = start + n;}}

Modifiers

​ modifiers 增删查改、vector头插头删效率很低，就不提供头插头删接口了。

push_back、pop_back

​ 尾差、尾删，直接在vector最后插入删除数据。

void push_back(const T& val){if (capacity() == size()){size_t n = (capacity() == 0) ? 4 : 2 * capacity();reserve(n);}*finish = val;++finish;}void pop_back(){assert(start != finish);--finish;}

insert

insert函数，在某个位置插入n(可以是1)个数据。或者插入一段迭代器区间的数据。

iterator insert(iterator pos, const T& val){// 空间不够先进行增容if (finish == end_of_storage){size_t newCapacity = (capacity() == 0) ? 1 : capacity() * 2;reserve(newCapacity);// 如果发生了增容，需要重置pospos = _start + size();}//挪动数据iterator p = finish;while (p != pos){*p = *(p - 1);--p;}*pos = val;finish += 1;return pos;}template<class InputIterator>void insert(iterator pos, InputIterator first, InputIterator last){//这里如果迭代器不是原生指针或者内存空间不连续就不能进行 - 操作了size_t sz = last - first;size_t n = pos - start;reserve(sz + size());pos = start + n;//挪数据iterator p = finish - 1;while (p >= pos){*(p + sz) = *p;--p;}//插入数据for (size_t i = 0; i < sz; i++){pos[i] = first[i];}finish += sz;}

​ 这里，扩容之后还用一个迭代器失效问题，需要重新给pos赋值。

erase

​ erase就是删除某个位置的数据，直接将后面数据往前移动即可

iterator erase(iterator pos){size_t sz = finish - pos;for (int i = 0; i < sz; i++){pos[i] = pos[i + 1];}finish -= 1;return pos;}

clear、swap

void swap(vector<T>& v){std::swap(start, v.start);std::swap(finish, v.finish);std::swap(end_of_storage, v.end_of_storage);}void clear(){finish = start;}

Element access

operator[ ]

​ 下标访问，直接返回start[i]即可。

T& operator[](size_t i){return start[i];}const T& operator[](size_t i) const{return start[i];}

代码总览

#pragma once#include<iostream>#include<assert.h>namespace HL{template<class T>class vector{//迭代器iteratortypedef T* iterator;typedef const T* const_iterator;public://默认成员函数vector():start(nullptr),finish(nullptr),end_of_storage(nullptr){}vector(size_t n, const T& val = T()){start = new T[n];for (size_t i = 0; i < n; i++){start[i] = val;}end_of_storage = finish = start + n;}vector(int n, const T& val = T()){start = new T[n];for (int i = 0; i < n; i++){start[i] = val;}end_of_storage = finish = start + n;}vector(const vector& v){size_t sz = v.size();size_t cp = v.capacity();start = new T[sz];for (int i = 0; i < sz; i++){start[i] = v[i];}finish = start + sz;end_of_storage = start + cp;}template<class InputIterator>vector(InputIterator first, InputIterator last){size_t sz = last - first;start = new T[sz];finish = start;while (first != last){*finish = *first;++finish;++first;}end_of_storage = start + sz;}~vector(){if (start)delete[] start;start = finish = end_of_storage = nullptr;}/*vector<T>& operator=(vector v){swap(v);return *this;}*/vector<T>& operator=(const vector& v){if (start)delete[] start;size_t sz = v.size();start = new T[sz];for (int i = 0; i < sz; i++){start[i] = v[i];}finish = end_of_storage = start + sz;}//Iteratoriterator& begin(){return start;}iterator& end(){return finish;}const_iterator begin() const{return start;}const_iterator& end() const{return finish;}//Capacitysize_t size() const{return finish - start;}size_t capacity() const{end_of_storage - start;}bool empty() const{return start == finish;}void reserve(size_t n){if (n > capacity()){iterator tmp = T[n];size_t sz = size();for (int i = 0; i < sz; i++){tmp[i] = start[i];}if (start)delete[] start;start = tmp;finish = start + sz;end_of_storage = start + n;}}void resize(size_t n, const T& val = T()){reserve(n);if (n < size()){finish = start + n;}else {for (int i = size(); i < n; i++){start[i] = val;}finish = start + n;}}//Modifiersvoid push_back(const T& val){if (capacity() == size()){size_t n = (capacity() == 0) ? 4 : 2 * capacity();reserve(n);}*finish = val;++finish;}void pop_back(){assert(start != finish);--finish;}iterator insert(iterator pos, const T& val){// 空间不够先进行增容if (finish == end_of_storage){size_t newCapacity = (capacity() == 0) ? 1 : capacity() * 2;reserve(newCapacity);// 如果发生了增容，需要重置pospos = _start + size();}//挪动数据iterator p = finish;while (p != pos){*p = *(p - 1);--p;}*pos = val;finish += 1;return pos;}template<class InputIterator>void insert(iterator pos, InputIterator first, InputIterator last){//这里如果迭代器不是原生指针或者内存空间不连续就不能进行 - 操作了size_t sz = last - first;size_t n = pos - start;reserve(sz + size());pos = start + n;//挪数据iterator p = finish - 1;while (p >= pos){*(p + sz) = *p;--p;}//插入数据for (size_t i = 0; i < sz; i++){pos[i] = first[i];}finish += sz;}iterator erase(iterator pos){size_t sz = finish - pos;for (int i = 0; i < sz; i++){pos[i] = pos[i + 1];}finish -= 1;return pos;}void swap(vector<T>& v){std::swap(start, v.start);std::swap(finish, v.finish);std::swap(end_of_storage, v.end_of_storage);}void clear(){finish = start;}//Element access:T& operator[](size_t i){return start[i];}const T& operator[](size_t i) const{return start[i];}private:iterator start;iterator finish;iterator end_of_storage;};};

到这里，vector模拟实现就结束了，希望你能有所收获

感谢各位大佬支持并指出问题

​ 如果本篇内容对你有帮助，可以一键三连支持以下，感谢支持！！！