C++:vector的模拟实现

✨✨✨学习的道路很枯燥，希望我们能并肩走下来!

文章目录

前言

一、vector的模拟实现

1.1 迭代器的获取

1.2 构造函数和赋值重载

1.2.1 无参构造函数

1.2.2 有参构造函数（对n个对象的去调用他们的构造）

1.2.3 迭代器区间构造

1.2.4 赋值重载

1.3 析构函数

1.4 常见接口

1.4.1 获取size和capacity

1.4.2 reserve提前扩容

1.4.3 resize

1.4.4 insert

1.4.5 erase

1.4.6 push_back()

1.4.7 pop_back()

1.4.8 swap

1.4.9 重载[ ]

1.5. 迭代器失效问题

1.5.1 insert的失效

1.5.2 erase的失效

二 vector实现的全部代码

总结

前言

本篇详细介绍了vector的模拟实现，让使用者了解vector，而不是仅仅停留在表面，更好的模拟，为了更好的使用. 文章可能出现错误，如有请在评论区指正，让我们一起交流，共同进步！

一、vector的模拟实现

大致框架需要有模板（类外定义）/迭代器以及迭代器的获取（public定义，要有可读可写的也要有可读不可写的）/成员变量（private定义） 并且为了不和库的vector冲突，我们需要自己搞一个命名空间

这是我们要实现的大致框架

namespace ch{template<class T>class vector{public:// Vector的迭代器是一个原生指针typedef T* iterator；typedef const T* const_iterator；iterator begin()；iterator end()；const_iterator begin()  const；const_iterator end() const；// construct and destroyvector()；vector(size_t n, const T& value = T())；template<class InputIterator>vector(InputIterator first, InputIterator last)；vector(const vector<T>& v)；vector<T>& operator= (vector<T> v)；~vector()；// capacitysize_t size() const ；size_t capacity() const；void reserve(size_t n)；void resize(size_t n, const T& value = T())；///access///T& operator[](size_t pos)；const T& operator[](size_t pos)const；///modify/void push_back(const T& x)；void pop_back()；void swap(vector<T>& v)；iterator insert(iterator pos, const T& x)；iterator erase(Iterator pos)；private:iterator _start = nullptr; // 指向数据块的开始iterator _finish = nullptr; // 指向有效数据的尾iterator _endOfStorage = nullptr; // 指向存储容量的尾};}

1.1 迭代器的获取

这一步很简单，只需要把我们的成员变量获取出来就可以，代码如下

iterator begin()
{return _start;
}iterator end()
{return _finish;
}
//迭代器(可读不可写)
typedef const T* const_iterator;const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}

1.2 构造函数和赋值重载

1.2.1 无参构造函数

	//无参构造函数vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}

1.2.2 有参构造函数（对n个对象的去调用他们的构造）

vector(int n, const T& value = T()) 
{reserve(n); //已经知道多少空间，提前开，避免push_back多次开空间降低效率for (size_t i = 0; i < n; i++){push_back(value);}
}

缺省值T( ) ，这个地方的缺省值不能给0！！因为vector可能会存储内置类型，也可能会存储自定义类型，比如vector<string>,所以如果我们没给值，缺省值就要给他的默认无参构造函数，这个默认构造函数可以使用匿名对象。

1.2.3 迭代器区间构造

template<class InputIterator>
vector(InputIterator first, InputIterator last)
{//这里传的是别人的迭代器，不知道会传多少数据，不能提前扩容，只能让pushback的时候去判断while (first != last){push_back(*first);first++;}
}

类模板的本质上是为了让这个函数更加灵活，可以传不同类型的迭代器来帮助我们初始化，让其他的容器的迭代器来实现初始化

非法的间接寻址是为什么？

如下图我传（10，5），会出非法间接寻址

但是我传（10u，5）就可以正常使用了

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

1.2.4 赋值重载

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

1.3 析构函数

将_start指向的空间释放，成员变量全为空指针

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

1.4 常见接口

1.4.1 获取size和capacity

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

1.4.2 reserve提前扩容

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

1.4.3 resize

有三种情况，第一种是给的n比原来的size小，第二种是n比size大但是比capacity小，第三种是n比capacity大，这个时候需要扩容

void resize(size_t n, const T& value = T())
{if (n <= size()){_finish = _start + n;}else{if (n > capacity()){reserve(n);}while (_finish != _start + n){*_finish = value;++_finish;}}
}

1.4.4 insert

iterator insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _endOfStorage){size_t n = pos - _start; //记录pos与起点位置的差值，开空间后，原pos迭代器失效，要更新size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);pos = _start + n; //更新新位置}iterator end = _finish - 1;while (end >= pos){*(end+1) = *(end);end++;}*pos = x;_finish++;return pos; //返回删除位置的下个元素位置，与文档相同
}

1.4.5 erase

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

1.4.6 push_back()

我们在上面实现了insert 的实现，我们就复用insert来实现push_back()

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

1.4.7 pop_back()

同上

void pop_back()
{erase(--end());
}

1.4.8 swap

用标准库的交换来实现

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}

1.4.9 重载[ ]

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

1.5. 迭代器失效问题

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

1.5.1 insert的失效

就是因为扩容导致pos失效，我们需要去及时更新pos

但是我们传的pos是值传递，所以我们更新的后pos更新，我们在后面解引用pos就会出现经典的解引用野指针问题。

就得用返回值传回pos 这也是为什么insert的返回值用iterator的原因，我们想继续用的话就得去接收一下返回值，就可以了

虽然有了返回值，我们可以去接收更新后的pos，但是一旦我们使用了任意一个可能扩容的函数，都会到时pos的失效，从而有可能回引发野指针问题，这个问题是不太好避免的，所以我们认为迭代器只能用一次，因为结果不可预测！

1.5.2 erase的失效

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

结果是未定义的，不同编译器场景可能不同

迭代器失效解决办法：在使用前，对迭代器重新赋值即可。

二 vector实现的全部代码

#pragma once
#include<assert.h>
namespace ch
{template<class T>class vector{public:// Vector的迭代器是一个原生指针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():_start(nullptr),_finish(nullptr),_endOfStorage(nullptr){}vector(size_t n, const T& value = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(value);}}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}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;}~vector(){delete[] _start;_start = _finish = _endOfStorage = nullptr;}// capacitysize_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}void reserve(size_t n){if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];if (_start){for (size_t i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + oldsize;_endOfStorage = _start + n;}}void resize(size_t n, const T& value = T()){if (n <= size()){_finish = _start + n;}else{if (n > capacity()){reserve(n);}while (_finish != _start + n){*_finish = value;++_finish;}}}///access///T& operator[](size_t pos){return _start[pos];}///modify/void push_back(const T& x){insert(end(), x);}void pop_back(){erase(--end();}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endOfStorage){size_t n = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);pos = _start + n;}iterator end = _finish - 1;while (end >= pos){*(end+1) = *(end);end++;}*pos = x;_finish++;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);size_t end = pos + 1;while (end != _finish){*(end - 1) = *(end);end++;}_finish--;}private:iterator _start = nullptr;// 指向数据块的开始iterator _finish = nullptr; // 指向有效数据的尾iterator _endOfStorage = nullptr; // 指向存储容量的尾};
}