string(上):C++初阶学习第六弹——探索STL奥秘(一)——标准库中的string类-CSDN博客
string(下):C++初阶学习第七弹——探索STL奥秘(二)——string的模拟实现-CSDN博客
vector(上):
前言:
在前面我们已经学习了string的使用及其模拟实现,并且我们也已经学习了vector的使用,今天我们就来学习一下vector的模拟实现
目录
一、 vector的基本成员变量
二、 vector的逐步实现
1、构造和销毁
2、迭代器相关
3、容量相关
4、元素访问
5、vector的修改操作
三、总结
一、 vector的基本成员变量
我们之前已经学习了vector的使用,所以也基本了解了其机制,现在我们来看一下vector工作的基本机制
从图中我们可以看出,vector的操作机制实际上是通过三个指针来实现的:
_start、_finish、_endOfStorage
所以vector的基本成员变量为:
#includeusing namespace std; //命名一个命名空间,在这个命名空间中实现我们自己的vector,这样能避免受库中vector的影响 namespace zda { template class vector { privated: T* _start; //指向有效数据的头 T* _finish; //指向有效数据的尾 T* _endOfStorage; //指向容量的尾 }; }
因为vector的本质上与顺序表很相似,只是存储的数据上变的更加多元化了,所以我们可以对基本成员做一些调整,将其改成迭代器相关的,方便我们后面写类成员函数
改进后:
#includeusing namespace std; //命名一个命名空间,在这个命名空间中实现我们自己的vector,这样能避免受库中vector的影响 namespace zda { template class vector { public: // Vector的迭代器是一个原生指针 typedef T* iterator; typedef const T* const_iterator; privated: iterator _start; //指向有效数据的头 iterator _finish; //指向有效数据的尾 iterator _endOfStorage; //指向容量的尾 }; }
接下来,我们就开始进入今天的正题,模拟vector的五大步骤:
1、构造和销毁
2、迭代器相关
3、容量相关
4、元素访问
5、vector的修改操作
二、 vector的逐步实现
1、构造和销毁
构造的方法主要有以下五种:
· 默认构造
· 构造同时将前n个初始化
· 迭代器构造法
· 拷贝构造
· operator=运算符重载
//一、vector的构造销毁 //1、默认构造 vector() :_start(nullptr) ,__finish(nullptr) ,_endOfStorage(nullptr) {} //2、构造同时将前n个初始化 vector(size_t n, const T& m = T()) :_start(nullptr) , __finish(nullptr) , _endOfStorage(nullptr) { reserve(n); //开辟n个大小的空间,这个函数在后面 while (n--) { push_back(m); //尾插,也在后面讲 } } //但是上面这个函数会有一个特殊情况出现 //例如对于vectorv(5,3) //由于v中的参数是(int,int),所以编译器容易把它与迭代器相关的函数去配对 //所以对于上面这个函数我们又写了一个vector(int n, const T& m = T())类型的来避免错误发生 //这种情况下参数一定都为int型的,所以我们可以按顺序表的方式来写这个函数 vector(int n, const T& m = T()) :_start(new T[n]) , __finish(nullptr) , _endOfStorage(nullptr) { for (int i = 0; i < n; i++) { _start[i] = m; } } //3、迭代器构造法 //为了实现不同迭代器的传参构造,我们这里再创建一个迭代器模板 template vector(InputInterator first, InputInterator last) { while (fast != last) { push_back(*first); //尾插的时候会检查扩容,所以也可以不写reserve函数 first++; } } //4、拷贝构造 vector(const vector & v) :_start(nullptr) ,_finish(nullptr) ,_endOfStorage(nullptr) { reserve(v.capacity()); iterator it = begin(); const_iterator vit = v.cbegin(); //这里涉及到const迭代器的内容,也是在后面讲 while (vit != v.cend()) { *it++ = *vit++; } _finish = it; } //5、operator=运算符重载 vector & operator=(vector v) { swap(v); //由于这里的v是对目标对象的复制,是开辟的新空间,所以我们完全可以swap直接交换而得 return *this; } //析构 ~vector() { if (_start) { delete _start; _start = _finish = _endOfStorage = nullptr; } }
2、迭代器相关
// 迭代器相关(迭代器主要就是找到头尾) iterator begin() { return _start; } iterator end() { return _finish; } const_iterator cbegin() const { return _start; } const_iterator cend() const { return _finish; }
3、容量相关
容量相关的最重要的就是扩容,就是reserve函数,同时我们也需要注意一下resize函数,这两者各自的特点需要记清,这些前面文章有讲到,我们这里只强调一下:
resize函数即可以扩容,也可以缩容,同时还可以初始化,这个函数创造性挺大
size_t size() const { return _finish - _start; } size_t capacity() const { return _endOfStorage - _start; } bool empty() const { return _start == _finish; } void reserve(size_t n) { if (n > capacity()) { size_t oldSize = size(); // 1. 开辟新空间 T* tmp = new T[n]; // 2. 拷贝元素 // 这里不能直接使用memcpy,原因我们将放到下面专门讲 //if (_start) // memcpy(tmp, _start, sizeof(T)*size); if (_start) { for (size_t i = 0; i < oldSize; ++i) tmp[i] = _start[i]; // 3. 释放旧空间 delete[] _start; } _start = tmp; _finish = _start + oldSize; _endOfStorage = _start + n; } } void resize(size_t n, const T& value = T()) { // 1.如果n小于当前的size,则数据个数缩小到n if (n <= size()) { _finish = _start + n; return; } // 2.空间不够则增容 if (n > capacity()) reserve(n); // 3.将size扩大到n iterator it = _finish; _finish = _start + n; while (it != _finish) { *it = value; ++it; } }
4、元素访问
元素访问关键就是运算符重载(operator[ ]),由于我们定义的类成员变量是以指针形式的,所以我们其实很容易实现这个重载
// 元素访问 T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos)const { assert(pos < size()); return _start[pos]; } T& front() { return *_start; } const T& front()const { return *_start; } T& back() { return *(_finish - 1); } const T& back()const { return *(_finish - 1); }
5、vector的修改操作
vector的修改操作最关键的就是insert函数和erase函数,就是在任意位置插入和删除,尾插尾删可以直接调用这两个函数来实现,但这两个函数细节也挺多,具体实现细节看下面实现过程
// vector的修改操作 void push_back(const T& x) //尾插,可以直接调用insert函数 { insert(end(), x); } void pop_back() //尾删,跟尾插一样,可以调用erase函数 { erase(end() - 1); } void swap(vector& 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 <= _finish); // 空间不够先进行增容 if (_finish == _endOfStorage) { //size_t size = size(); size_t newCapacity = (0 == capacity()) ? 1 : capacity() * 2; reserve(newCapacity); // 如果发生了增容,需要重置pos pos = _start + size(); } iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; --end; } *pos = x; ++_finish; return pos; } // 返回删除数据的下一个数据 // 方便解决:一边遍历一边删除的迭代器失效问题 // (迭代器失效问题在vector中会发生,不知道的可以看我之前文章) iterator erase(iterator pos) { // 挪动数据进行删除 iterator begin = pos + 1; while (begin != _finish) { *(begin - 1) = *begin; ++begin; } --_finish; return pos; }
三、总结
上面的就是vector的模拟实现的全部代码段,这些还不是vector的全部内容,还有vector复制等几个细节我们还没讲,这个感兴趣的可以关注一下,将在下一篇讲解这些细小知识点
感谢各位大佬观看,创作不易,还请各位大佬点赞支持!!!
还没有评论,来说两句吧...