文章目录

• 前言
• vector的大致框架
• 模拟实现
• • 构造函数
  • 获取头尾数据的位置
  • 获取有效数据个数和容量
  • 重载[]
  • reserve函数
  • resize函数
  • • ⭐匿名对象的玩法
  • push_back尾插
  • 利用迭代器区间构造
  • operator=
  • insert任意位置插入
  • erase任意位置删除
  • 析构
  • ⚡检测vector
• ⭐迭代器失效
• ⭐源码

接前一篇文章
C++中string类的模拟实现

前言

vector是一个可变大小的序列容器，可以理解为动态增长的顺序表，但vector可以存储任意类型的数据，不管是自定义类型还是内置类型。所以vector是一个类模板，vector在实际中也非常重要，用的也很频繁。下面我们来深入了解vector的常用接口以及模拟实现

vector的大致框架

vector是通过内存池申请空间的，我们模拟实现就直接在堆区申请空间。
首先迭代器是一个随机迭代器，支持++、 --、 +、 -

//避免命名冲突在自己的命名空间实现namespace king{template<class T>class vector{typedef T* iterator;typedef const T* const_iterator;public:private:iterator _start;//指向vector的起始位置iterator _finish;//指向vector的有效元素的下一个位置iterator _endofstorage;//指向vector容量的下一个位置};}

模拟实现

构造函数

我们直接实现一个无参的

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

还有另一种构造函数以及拷贝构造和赋值需要复用其他函数所以我们后面再实现

获取头尾数据的位置

//返回第一个数据的位置iterator begin(){return _start;}//返回最后一个数据的下一个位置iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}

获取有效数据个数和容量

//不可修改所以都定义为const成员const size_t size() const{return _finish - _start;}const size_t capacity() const{return _endofstorage - _start;}

重载[]

• 功能： 像数组一样访问vector的数据

//对非const对象可以通过[]访问数据后进行修改T& operator[](size_t pos){//pos只能小于有效数据个数assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}

reserve函数

• 功能：只会改变capacity的大小

void reserve(size_t n){//当n大于capacity才会处理if (n > capacity()){size_t sz = size();T* tmp = new T[n];//开新的空间if (_start)//_satrt为空就不用拷贝了{ //memcpy(tmp, _start, sizeof(T) * sz); //不能使用memcpy，因为memcpy是浅拷贝，当T是其他自定义类型 //例如T为string时就会出事 //所以需要赋值+循环完成深拷贝for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}

resize函数

• 功能：在reserve函数的基础上开空间+初始化

//让匿名对象调用它的构造函数初始化void resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{if (n > capacity())reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}

⭐匿名对象的玩法

当匿名对象被const引用修饰后，它的生命周期就不是只在那一行了，而是在当前的作用域

类似于这种

push_back尾插

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

利用迭代器区间构造

这里采用的是InputIterator只写迭代器，没有对应的类型，是一种抽象的迭代器，采用迭代器区间构造vector

template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){//将迭代器区级的所以数据尾插到*this中完成拷贝构造push_back(*first);++first;}}

拷贝构造

void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}//v1(v2)vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){//直接让tmp帮我们构造出一样的v2，然后交换tmp与v1即可//这里tmp是局部变量出了作用域会自动调用析构函数//所以需要将v1在初始化列表中置为nullptrvector<T> tmp(v.begin(), v.end());swap(tmp);}

operator=

//v1=v2vector<T>& operator=(const vector<T>& v){//tmp拷贝构造一个一样的v，然后交换tmp与v1vector<T> tmp(v);swap(tmp);return *this;}

insert任意位置插入

• 这里就已经涉及迭代器失效问题了，我们在最后面具体讲解

iterator insert(iterator pos, const T& val){//迭代器不能超过有效数据范围assert(pos >= _start && pos <= _finish);//扩容if (_finish == _endofstorage){//需要先记录pos相对_start的偏移量//因为扩容之后pos原来指向的空间已经被释放了size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish;while (end > pos){*end = *(end - 1);--end;}*pos = val;++_finish;//返回插入新元素的第一个元素位置的迭代器，防止迭代器失效return pos;}

erase任意位置删除

• 这里同样涉及迭代器失效问题

iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator begin = pos;//挪动和数据覆盖原来的迭代器位置while (begin + 1 < _finish){*begin = *(begin + 1);++begin;}--_finish;//返回原pos指向的下一个元素位置的迭代器，实际上就是posreturn pos;}

析构

~vector(){//这里先判断_start是否为nullptr，为nullptr就可以不用delete了if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}

⚡检测vector

到这里vector常用的借口都实现的差不多了，之前给大家分享了一篇动态开辟的杨辉三角
C++版就是用嵌套的vector实现的，我们用模拟实现的vector测试一下

void Test3(){int numrows = 10;vector<vector<int>> vv;vv.resize(numrows);for (int i = 0; i < numrows; i++){//开intvv[i].resize(i + 1);}for (int i = 0; i < numrows; i++){for (int j = 0; j <= i; j++){if (j == 0 || i == j){vv[i][j] = 1;}else{vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];}}}print(vv, numrows);}

打印结果，没啥问题

⭐迭代器失效

• vector的迭代器失效主要发生在insert/erase中
• insert时，如果需要扩容，迭代器指向的空间被释放，迭代器就变成了野指针，发生迭代器失效
• 使用迭代器insert或erase之后，如果再次使用这个迭代器时就会发生迭代器失效，所以需要先更新迭代器

这里我们用STL中的vector测试一下，当同一个迭代器使用两次时就会断言报错

只要使用迭代器访问容器，都有可能迭代器失效，所以不管是insert还是erase都会返回新的迭代器位置，当然如果我们没有连续使用也可以不接收返回值

更新迭代器后就不会失效了

⭐源码

vector.h

#include #include #include #include using namespace std;namespace king{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;vector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr){}template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}//v1(v2)vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){vector<T> tmp(v.begin(), v.end());swap(tmp);}//v1=v2vector<T>& operator=(const vector<T>& v){vector<T> tmp(v);swap(tmp);return *this;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}const size_t size() const{return _finish - _start;}const size_t capacity() const{return _endofstorage - _start;}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start)//_satrt为空就不用拷贝了{//memmove(tmp, _start, sizeof(T) * sz);for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}void resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{if (n > capacity())reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}void push_back(const T& val){//扩容if (_finish == _endofstorage)reserve(capacity() == 0 ? 4 : capacity() * 2);*_finish = val;++_finish;}iterator insert(iterator pos, const T& val){assert(pos >= _start && pos <= _finish);//扩容if (_finish == _endofstorage){//需要先记录pos相对_start的偏移量，因为再扩容之后pos指向的空间已经被释放了size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish;while (end > pos){*end = *(end - 1);--end;}*pos = val;++_finish;//返回插入新元素的第一个元素位置的迭代器，防止迭代器失效return pos;}iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator begin = pos;while (begin + 1 < _finish){*begin = *(begin + 1);++begin;}--_finish;//返回原pos指向的下一个元素位置的迭代器，实际上就是posreturn pos;}~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}private:iterator _start;iterator _finish;iterator _endofstorage;};void Test1(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.resize(10, 7);vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;}void Test2(){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);vector<int> v2(v.begin(), v.end());vector<int> v3(v2);for (auto e : v3){cout << e << " ";}cout << endl;}void print(vector<vector<int>> vv, int numrows){for (int i = 0; i < numrows; i++){for (int j = 0; j <= i; j++){cout << vv[i][j] << "   ";}cout << endl;}}void Test3(){int numrows = 10;vector<vector<int>> vv;vv.resize(numrows);for (int i = 0; i < numrows; i++){//开intvv[i].resize(i + 1);}for (int i = 0; i < numrows; i++){for (int j = 0; j <= i; j++){if (j == 0 || i == j){vv[i][j] = 1;}else{vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];}}}print(vv, numrows);}void Test4(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);vector<int> v3(v);vector<int> v2(v.begin() + 1, v.end() - 1);v2 = v3;for (auto e : v2){cout << e << " ";}cout << endl;}void Test5(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//vector v2(v.begin(), v.end());vector<int>::iterator it = find(v.begin(), v.end(), 2);if (it != v.end()){//如果insert时发生扩容，就会导致it指向的空间被释放//it就变成了野指针，也就是迭代器失效v.insert(it, 1000);}for (auto e : v){cout << e << " ";}cout << endl;it = find(v.begin(), v.end(), 4);v.erase(it);for (auto e : v){cout << e << " ";}cout << endl;}}

test.cpp

#include "vector.h"int main(){king::Test3();return 0;}

以上就是vector的模拟实现了，我们模拟了一些常用的函数，模拟实现有利于我们了解vector类模板，同时在学习其他容器时会方便很多，希望我的文章对你有所帮助，欢迎👍点赞 ，📝评论，🌟关注，⭐️收藏

读书笔记网