企业网站美化,如何用手机创造游戏软件,婚纱店网页设计,微信平台开发公司成都目录 前言vector核心框架模拟实现1. 前期准备2. 构造和销毁补充: 隐式类型转换和多参数构造的区别 3. 迭代器相关4. 容器相关补充: memcpy拷贝问题 5. 元素访问6. vector的修改测试代码 总结 前言
本文重点模拟实现vector的核心接口, 帮助我们更好的理解底层逻辑, 以及对vecto… 目录 前言vector核心框架模拟实现1. 前期准备2. 构造和销毁补充: 隐式类型转换和多参数构造的区别 3. 迭代器相关4. 容器相关补充: memcpy拷贝问题 5. 元素访问6. vector的修改测试代码 总结 前言
本文重点模拟实现vector的核心接口, 帮助我们更好的理解底层逻辑, 以及对vector的深度剖析.
博客主页: 酷酷学!!! 期待关注~ 正文开始 vector核心框架模拟实现
1. 前期准备
首先, 可以查看到STL源码, 底层vector的实现并不是我们通常顺序表那样定义成员变量, 而是通过迭代器也就是指针进行实现, 那么我们也按照STL来进行模拟实现.
T* _a;
size_t _size;
size_t _capacity;#pragma once#includeiostream
#includeassert.h
using namespace std;namespace my
{templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;//核心接口的实现private:iterator _start; //指向数据块开始iterator _finish; //指向有效数据的尾iterator _endOfStorage; //指向存储容量的尾};
}2. 构造和销毁 默认无参构造 //默认无参构造vector():_start(nullptr), _finish(nullptr), _endOfStorage(nullptr){}默认的无参构造, 因为在声明的时候我们并没有给缺省值, 所以我们也可以直接在初始化列表进行初始化.
迭代器区间初始化 //迭代器区间初始化//若使用iterator做迭代器,会导致初始化的迭代器区间[first,last)//只能是vector的迭代器//重新声明迭代器,迭代器区间[first,last)可以是任意容器的迭代器templateclass InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}初始化n个相同的值 //n个相同的值,使用默认的构造函数进行初始化, //对于内置类型,C对这方面也进行了支持//vector(size_ n, const T value 0)//这里缺省值不能给0,如果对于自定义类型就有问题了vector(size_t n, const T value T())//匿名对象//相当于缺省值给了一个临时的匿名对象:_start(nullptr), _finish(nullptr), _endOfStorage(nullptr){reserve(n);while (n--){push_back(value);}}/** 理论上讲, 提供了vector(size_t n,const T value T())之后,* vector(int n,const T value T())就不需要提供了,但是对于:* vectorint v(10,5);* 编译器在编译时,认为T已经被实例化为int,而10和5编译器会默认其为int类型* 就不会走vector(size_t n,const T value T())这个构造方法* 最终选择的是vector(InputIterator first, InputIterator last)* 因为编译器觉得区间构造两个参数类型一致因此编译器就会将InputIterator实例化为int* 但是10和5根本不是一个区间编译时就报错了* 故需要增加该构造方法*/vector(int n, const T value T()): _start(new T[n]), _finish(_start n), _endOfStorage(_finish){for (int i 0; i n; i){_start[i] value;}}这里可能不太理解为什么 const T value T() 这个缺省值要给T(), 要给默认构造函数, C对于内置类型也进行了升级, 内置类型也可以使用构造初始化, 所以这个值, 不管自定义类型还是内置类型都可以适用 // C内置类型进行了升级也有构造int i 0;int j(1);int k int();int x int(2)有时候, 我们会发现有些代码使用vector是这样写的
vectorint v{ 1, 2, 3, 4 };查看C文档, 可以发现这是C11的新语法让vector用起来更加方便, 使用initializer_list这个类进行初始化. initializer_list中有两个成员变量. begin指针和end指针, 记录了列表的开始位置和结尾位置, 记录列表这段区间, 进行初始化.
initializer_list进行初始化 vector(initializer_listT il):_start(nullptr),_finish(nullptr),_endOfStorage(nullptr){reserve(il.size());for (auto e : il){push_back(e);}}首先扩容, 然后遍历il, 将里面的值尾插到vector. 拷贝构造 //拷贝构造vector(const vectorT v):_start(nullptr),_finish(nullptr),_endOfStorage(nullptr){reserve(v.capacity());iterator it begin();const_iterator vit v.cbegin();while (vit ! v.cend()){*it *vit;}_finish it;}//vector(const vectorT v)// :_start(nullptr)// ,_finish(nullptr)// ,_endOfStorage(nullptr)//{// reverse(v.capacity());// for (auto e : v)// {// push_back(e);// }//}赋值运算符重载 void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}//赋值运算符重载// v1 v3vectorT operator(vectorT v){swap(v);return *this;}析构函数 //析构函数~vector(){if (_start){delete[] _start;_start _finish _endOfStorage nullptr;}}补充: 隐式类型转换和多参数构造的区别
class A{public:A(int a1 0):_a1(a1), _a2(0){}A(int a1, int a2):_a1(a1),_a2(a2){}private:int _a1;int _a2;};void test()
{//单参数构造和多参数对象隐式类型转换A aa1(1); //这里是单参数构造A aa2 1; //这里是隐式类型转换A aa3(1,1); //这里是多参数构造A aa4 {1,1}; //这里是多参数隐式类型转换A aa5{1,1}; //这里是多参数隐式类型转换省略, 一般不要这种写法A aa6{1};A aa7 {1}; //这两个是C为了想让{}进行统一, 所以单参数也可以使用{}进行构造, 比较冗余,一般不要这样写/////自定义类型动态开辟调用构造函数A* p1 new A;//无参构造A* p2 new A(2); //单参数传参构造A* p3 new A(2,3); //多参数传参构造A* p1 newA[10]; //连续申请10个空间,无参构造A aa1(1);A aa2(2);A aa3(3);A *p2 new A[10]{aa1,aa2,aa3};//拷贝构造,其余为0A* p3 new A[10]{1,2,3,4,{6,7}};//也可以直接写,进行隐式类型转换///这里的隐式类型转换跟上面不一样这里参数个数不固定vectorint v1({ 1,2,3,4,5,6 });vectorint v2 { 10, 20, 30};//()可以省略for (auto e : v1){cout e ;}cout endl;for (auto e : v2){cout e ;}cout endl;vectorA v3 { 1, A(1), A(2,2), A{1}, A{2,2}, {1}, {2,2} };//这个是首先创建一个存储A的列表然后进行构造}3. 迭代器相关
这里分别对应静态和非静态vector iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin() const{return _start;}const_iterator cend() const{return _finish;}4. 容器相关
size和capacity size_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();//1.开辟新的空间T* tmp new T[n];//2.拷贝元素/*if (_start){memcpy(tmp, _start, sizeof(T) * size);}*///不可以用memcpy拷贝if (_start){for (size_t i 0; i oldSize; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start oldSize;_endOfStorage _start n;}}补充: memcpy拷贝问题
memcpy是内存的二进制格式拷贝将一段内存空间中内容原封不动的拷贝到另外一段内存空间中.如果拷贝的是内置类型的元素memcpy既高效又不会出错但如果拷贝的是自定义类型元素并且自定义类型元素中涉及到资源管理时就会出错因为memcpy的拷贝实际是浅拷贝。(比如拷贝int类型既高效又不会出错, 那如果vector里面存储的都是一个个的指针类型呢? 比如string类)
比如下面这段代码 vectorstring v1;v1.push_back(111111111111111111);v1.push_back(111111111111111111);v1.push_back(111111111111111111);v1.push_back(111111111111111111);v1.push_back(111111111111111111);for (auto e : v1){cout e ;}cout endl;当插入第五个值的时候, vector需要进行扩容, memcpy会继续拷贝, 但这是浅拷贝, 将_start里面的值拷贝到tmp中, 此时tmp中成员_str也指向了原来的那段空间, 当_start释放后, 区间就会被销毁, 此时tmp里面的内容就指向了野指针. 而这里使用赋值拷贝, 会调用我们的赋值拷贝函数, 就不会出现浅拷贝的问题了. 结论: 如果对象中涉及到资源管理时, 千万不能使用memcpy进行对象之间的拷贝, 因为memcpy是浅拷贝, 否则可能会引起内存泄漏甚至程序崩溃
rsize()函数 void resize(size_t n, const T value T()){//1.如果n小于当前的size,则数据缩小到nif (n size()){_finish _start n;return;}//2.空间不够则增容if (n capacity())reserve(n);//3.将size扩大到n,并使用value填充后面的值iterator it _finish;_finish _start n;while (it ! _finish){*it value;it;}}5. 元素访问 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);}6. vector的修改 void push_back(const T x){insert(end(), x);}void pop_back(){erase(end() - 1);}iterator insert(iterator pos, const T x){assert(pos _finish);assert(pos _start);//空间不够先进性增容if (_finish _endOfStorage){size_t newcapacity (capacity() 0) ? 4 : capacity() * 2;reserve(newcapacity);pos _start size();}iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}*pos x;_finish;return pos;}//返回删除数据的下一个数据,//方便解决迭代器失效的问题iterator erase(iterator pos){iterator begin pos 1;while (begin ! _finish){*(begin - 1) *begin;begin;}--_finish;return pos;}测试代码
void TestVector1()
{my::vectorint v1;my::vectorint v2(10, 5);int array[] { 1,2,3,4,5 };my::vectorint v3(array, array sizeof(array) / sizeof(array[0]));my::vectorint v4(v3);for (size_t i 0; i v2.size(); i){cout v2[i] ;}cout endl;
}void TestVector2()
{my::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);cout v.size() endl;cout v.capacity() endl;cout v.front() endl;cout v.back() endl;cout v[0] endl;for (auto e : v){cout e ;}cout endl;v.pop_back();v.pop_back();for (auto e : v){cout e ;}cout endl;v.insert(v.begin(), 0);for (auto e : v){cout e ;}cout endl;v.erase(v.begin() 1);for (auto e : v){cout e ;}cout endl;
}总结
本篇对vector的核心接口进行了模拟实现和探究, C这门语言本身就比较偏向底层, 希望能够帮助大家进一步理解底层逻辑以及实现思路, 感谢三连!!! 完
