C++ vector模拟实现
C++ vector模拟实现
- 一.我们要实现的大致框架
- 1.STL库中是如何实现的呢?
- 1.迭代器
- 2.成员变量
- 3.vector的特性
- 4.vector的成员变量大致情况
- 2.我们要实现的大致框架
- 3.前言
- 二.具体实现
- 1.迭代器,begin,end
- 2.无参构造,析构,简单函数
- 3.push_back
- 4.reserve
- 1.reserve的第一大坑点:野指针问题
- 1.reserve的第二大坑点:浅拷贝问题
- 3.正确版本
- 5.resize
- 6.insert
- 1.insert内部的迭代器失效问题
- 2.insert外部的迭代器失效问题
- 7.erase
- 1.erase的实现
- 2.erase外部的迭代器失效问题
- 8.push_back和pop_back对于insert和erase的复用
- 1.push_back
- 2.pop_back
- 9.含参构造
- 10.迭代器区间构造
- 11.拷贝构造
- 1.传统写法
- 2.现代写法
- 12.赋值运算符重载
- 1.传统写法
- 2.现代写法
- 三.完整代码
首先我们先明确一点:
对于vector而言,最难的点是
1.它如何进行设计与封装的
2.迭代器失效问题
3.memcpy,memmove导致的浅拷贝问题
而不是顺序表的基础操作
一.我们要实现的大致框架
1.STL库中是如何实现的呢?
1.迭代器
vector中的迭代器其实就是指针
因为vector的底层物理空间是连续的(vector其实就是数据结构中的顺序表)
2.成员变量
也就是说STL库中的vector容器维护的是3个指针:start finish end_of_storage
关于这三个指针大家一定要牢记它们的作用,因为下面全是对这三个指针的操作
3.vector的特性
注意:vector作为STL库中的容器,是采用泛型编程和面向对象的思想来设计的
vector的元素不仅仅可以是内置类型,也可以是自定义类型,其他容器类型
其实是因为vector采用了类模板的技术,因此vector可以存放所有类型的数据
例如
vector vector vector vector 等等等等....
4.vector的成员变量大致情况
其实vector中成员变量大致情况就是这样的
也就是说接下来我们所有的操作都是通过操作
_start _finish _endOfStorage这三个指针来完成的
#pragma once #include using namespace std; #include namespace wzs { template class vector { public: typedef T* iterator; typedef const T* const_iterator; private: iterator _start; // 指向数据块的开始 iterator _finish; // 指向有效数据的尾 iterator _endOfStorage; // 指向存储容量的尾 }; }2.我们要实现的大致框架
#pragma once #include using namespace std; #include namespace wzs { template class vector { public: /// // 构造,拷贝构造,赋值运算符重载,析构 vector(); vector(int n, const T& value = T()); template //迭代器区间构造 vector(InputIterator first, InputIterator last); //拷贝构造函数传统写法 vector(const vector& v); //拷贝构造函数现代写法 vector(const vector& v); //赋值运算符重载传统写法 vector& operator=(const vector& v); //赋值运算符重载现代写法 vector& operator=(vector v); ~vector(); / // 迭代器相关 // vector的迭代器是一个原生指针 typedef T* iterator; typedef const T* const_iterator; iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; // // 容量相关 size_t size() const; size_t capacity() const; void reserve(size_t n); void resize(size_t n, const T& value = T()); bool empty() const; /// // 元素访问 //operator[]运算符重载 T& operator[](size_t pos); const T& operator[](size_t pos)const; //返回第一个数据的引用 T& front(); const T& front()const; //返回最后一个有效数据的引用 T& back(); const T& back()const; / // vector的修改操作 void push_back(const T& x); void pop_back(); void swap(vector& v); //返回插入的元素的位置 iterator insert(iterator pos, const T& x); //返回被删除的位置的下一个位置 iterator erase(iterator pos); private: iterator _start; // 指向数据块的开始 iterator _finish; // 指向有效数据的尾 iterator _endOfStorage; // 指向存储容量的尾 }; }3.前言
为了更好地演示整个实现过程,
首先我们先实现
1.迭代器
2.无参构造函数,析构函数和其他一些很简单的函数
3.push_back
4.reserve
5.resize
6.insert
7.erase 然后是push_back和pop_back的复用
8.含参构造函数
9.迭代器区间构造函数
10.拷贝构造函数和赋值运算符重载
期间
在介绍reserve的时候我们会介绍本文的第一个重点:
memcpy/memmove导致的浅拷贝问题
在介绍insert和erase的时候我们会介绍本文的第二个重点:
迭代器失效问题
二.具体实现
1.迭代器,begin,end
刚才说明了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来说,iterator很简单,就是原生指针
2.无参构造,析构,简单函数
无参构造: vector() :_start(nullptr) ,_finish(nullptr) ,_endOfStorage(nullptr) {} 析构: ~vector() { delete[] _start; _start = _finish = _endOfStorage = nullptr; } // 容量相关的简单函数 size_t size() const { return _finish - _start; } size_t capacity() const { return _endOfStorage - _start; } bool empty() const { return _finish == _start; } // 元素访问的简单函数 T& operator[](size_t pos) { return _start[pos]; } const T& operator[](size_t pos)const { 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); }注意:
front是第一个有效数据的引用
back是最后一个有效数据的引用
operator[]是下标访问运算符重载,跟数组的下标访问是一样的用法
3.push_back
下面我们就来实现push_back
void push_back(const T& x) { //扩容 if (size() == capacity()) { int newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } //尾插 *_finish = x; ++_finish; }先扩容,后尾插
4.reserve
相信上面的那些函数对大家来说没有什么挑战
下面我们就来看一下reserve的实现过程中的坑点吧
reserve函数:扩容函数
1.reserve的第一大坑点:野指针问题
void reserve(size_t n);
如果ncapacity时才会扩容
大家看一下这份代码有问题吗?
void reserve(size_t n) { if (n > capacity()) { //1.申请新空间 T* tmp = new T[n]; //2.将原有数据拷贝到新空间当中 memmove(tmp, _start, sizeof(T) * size()); //3.释放原有空间 delete _start; //4.指向新空间 _start = tmp; _finish = _start + size(); _endOfStorage = _start + capacity(); } }其实是有问题的,_finish和_endOfStorage会成为野指针
原因如下:
给大家调试来看一下:
可以看出,扩容结束之后,_finish和_endOfStorage仍然还是指向旧空间的对应位置
那么应该怎么办呢?
其实我们可以把旧空间的size保存下来
记为oldSize,这样只需要
_finish = _start + oldSize; 即可将_finish也指向新空间的相应位置
而_endOfStorage呢?
因为新空间的容量是n
所以
_endOfStorage = _start + n; 即可将_endOfStorage也指向新空间的相应位置
因此下面的代码才是"正确"的
void reserve(size_t n) { if (n > capacity()) { //1.保存原有空间的size int oldSize = size(); //2.开辟新空间 T* tmp = new T[n]; //3.将原有空间的数据拷贝到新空间当中 memmove(tmp, _start, sizeof(T) * oldSize); //4.释放旧空间 delete _start; //5.指向新空间 _start = tmp; _finish = _start + oldSize; _endOfStorage = _start + n; } }分为5步:
1.保存原有空间的size
2.开辟新空间
3.将原有空间的数据拷贝到新空间当中
4.释放旧空间
5.指向新空间
下面我们来调试看一下:
1.reserve的第二大坑点:浅拷贝问题
刚才那个代码其实也是不正确的
不过他不正确的原因是因为memmove的底层实现其实是浅拷贝
是以字节为单位进行拷贝的
因为刚才我们这个vector里面存放的数据类型是int这种内置类型
而对于内置类型来说是不会受到浅拷贝的影响的
不过对于开辟在堆上的自定义类型来说就会受到浅拷贝的影响导致出现同一内存空间多次释放的错误
比方说此时vector里面存放的是string类型
第二次扩容之前是没有任何问题的
不过当他发生了扩容之后
崩了,断言报错
为什么呢?
而且:
delete的时候会先调string的析构函数把string都析构(string的空间在string的析构函数当中释放)了,然后才会释放_start这个旧空间
3.正确版本
因为我们实现的在堆上开辟了空间的自定义类型都是有赋值运算符重载的,而我们实现的赋值运算符重载都是深拷贝
因此我们可以这样修改
void reserve(size_t n) { if (n > capacity()) { //提前保存偏移量oldSize int oldSize = size(); //1.申请新空间 T* tmp = new T[n]; //2.将原有空间中的数据拷贝到新空间当中 for (int i = 0; i
此时就没有任何问题了
5.resize
resize:调整有效数据的个数
void resize(size_t n, const T& value = T())
作用是:
1.n //1.n //将_finish移动到_start向后偏移n个单位的位置 //我们知道:[_start,_finish)才是有效数据 //因此就是只让前n个数据作为有效数据 _finish = _start + n; } //2.size while (size() = _start && pos // //扩容 // int newcapacity = capacity() == 0 ? 4 : capacity() * 2; // reserve(newcapacity); // } // //开始insert // //把[pos,_finish)的数据往后挪 // iterator end = _finish; // while (end pos) // { // *end = *(end - 1); // --end; // } // //插入数据 // *pos = x; // //更新size // ++_finish; // return pos; //} //发生扩容之后pos迭代器会失效,因此需要在扩容之前先保存偏移量,并在扩容之后重新调整pos迭代器的位置 iterator insert(iterator pos, const T& x) { //检查pos的合法性 assert(pos >= _start && pos //先保存pos的偏移量 int gap = pos - _start; //扩容 int newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); //调整pos的位置 pos = _start + gap; } //开始insert //把[pos,_finish)的数据往后挪 iterator end = _finish; while (end pos) { *end = *(end - 1); --end; } //插入数据 *pos = x; //更新size ++_finish; return pos; } // 返回删除数据的下一个数据 // 方便解决:一边遍历一边删除的迭代器失效问题 iterator erase(iterator pos) { assert(pos >= _start && pos
以上就是C++ vector模拟实现的全部内容,希望能对大家有所帮助!
