当前位置:首页 » 《休闲阅读》 » 正文

C++ —— vector 的模拟实现

23 人参与  2024年10月01日 12:00  分类 : 《休闲阅读》  评论

点击全文阅读


目录

前言

1. vector深度剖析

 2. 基础框架

3. 核心接口

3.1 reserve

3.2 push_back 和 pop_back

3.3 print

 3.4 insert

3.5 erase

3.6 resize

4. 拷贝构造

4.1 构造与析构

4.2 拷贝构造 

4.3 赋值重载

4.4 迭代器区间

5. 使用memcpy拷贝问题


前言

接:C++ —— 关于vector-CSDN博客icon-default.png?t=O83Ahttps://blog.csdn.net/hedhjd/article/details/142334349?spm=1001.2014.3001.5501


1. vector深度剖析

 

 _start :相当于begin,指向开始的位置
_finish :相当于size,指向最后一个数据的位置
_end_of_storage :相当于_capacity


 2. 基础框架

//因为vector是用模板写的,所以不能进行声明和定义分离,否则会出现链接错误#pragma once#include<assert.h> // _start :相当于begin,指向开始的位置//_finish :相当于size,指向最后一个数据的下一个位置//_end_of_storage :相当于_capacitynamespace bit{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//迭代器iterator begin(){return _start;}iterator end(){return _finish;}//const迭代器const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}//可读可写T& operator[](size_t i){assert(i < size());return _start[i];}//只读const T& operator[](size_t i) const{assert(i < size());return _start[i];}//判断是否为空bool empty(){return _start == _finish;}private:iterator _start = nullptr;//给个缺省值iterator _finish = nullptr;iterator _end_of_storage = nullptr;};


3. 核心接口

3.1 reserve

//修改之后//扩容void reserve(size_t n){if (n > capacity()){//提前将旧size赋给新sizesize_t old_size = size(); //开辟新空间,创建临时变量//new出来的空间是初始化好的,所以可以直接用T* tmp = new T[n];//memcpy(tmp, _start, old_size * sizeof(T));/*如果T是string或者vector类型,就需要进行深拷贝 需要赋值进行拷贝数据,否则使用浅拷贝会导致内存泄漏*/for (size_t i = 0; i < old_size; i++){//赋值就是string/vector的赋值,也就是深拷贝tmp[i] = _start[i];}//释放旧空间delete[] _start;//再把三个私有变量指向新空间_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}}


3.2 push_back 和 pop_back

/*T有可能是一个int,也有可能是一个string,还可能是一个vector,所以需要传&,传&不改变需要加上一个const*///尾插void push_back(const T& x){//先判断需不需要扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}//如果不需要就直接插入到_finish的位置*_finish = x;++_finish;}//尾删void pop_back(){assert(!empty());--_finish;}


3.3 print

如果给出的代码编译器不知道该代码是类型还是变量,所以导致识别不出来,那么可以在前面加上 typename 或者改为 auto 自动推导

//给print_vector套一层模板,让它被谁都可以使用template<class T>void print_vector(const vector<T>& v){//如果typename在没有实例化的类模板里面取东西,// 那么编译器不能区分这里const_iterator是类型还是静态成员变量//typename vector<T>::const_iterator it = v.begin();//那么使用auto可以自动推导,由v.begin()推导auto it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;}

将print彻底转换成模板,使所有类型都可以使用,不管是string,vector等等 

//将print彻底转换成模板,使所有类型都可以使用,不管是string,vector等等template<class Container>void print_container(const Container& v){/*auto it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;*/for (auto e : v){cout << e << " ";}cout << endl;}

 3.4 insert

insert在扩容后原来的pos位置就会失效,也就是迭代器失效,就相当于成为了野指针,解决方法是将扩容之前的位置记录下来在扩容后更新pos的位置

//在指定位置插入数据void insert(iterator pos, const T& x){    assert(pos >= _start);assert(pos <= _finish);// 扩容if (_finish == _end_of_storage){/*为了防止迭代器失效的情况,先创建一个临时变量len记录扩容之前pos - _start的位置*/size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);//然后再更新pos的位置pos = _start + len;}//将最后一个数据的位置给临时变量enditerator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}


3.5 erase

erase之后也会出现迭代器失效,所以需要先记录pos原来的位置然后再更新pos

//删除指定位置的数据void erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;}


3.6 resize

用于改变vector的有效长度,也可以用来初始化指定长度的指定数据

三种情况:

1. 当n < size()时,删除多余的元素,直接缩容

2. 当size() < n < capacity()时,直接插入数据

3. 当capacity() < n时,先扩容再插入数据

//用于改变vector的有效长度//也可以开辟n个空间,使用val去初始化void resize(size_t n, T val = T()){//n < size,删除数据if (n < size()){_finish = _start + n;}else//>=size{//扩容reserve(n);while (_finish < _start + n){//插入数据val*_finish = val;++_finish;}}}


4. 拷贝构造

4.1 构造与析构

//默认构造    vector(){}    // C++11 强制生成默认构造//vector() = default;    //析构~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}


4.2 拷贝构造 

//拷贝构造vector(const vector<T>& v){reserve(v.size());for (auto& e : v){push_back(e);}}


4.3 赋值重载

//赋值重载的传统写法//clear清除数据但是不释放空间void clear(){_finish = _start;}// v1 = v3vector<T>& operator=(const vector<T>& v){if (this != &v){clear();reserve(v.size());for (auto& e : v){push_back(e);}}return *this;}//赋值重载的现代写法void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}// v1 = v3vector<T>& operator=(vector<T> v){swap(v);return *this;}


4.4 迭代器区间

1. 类模版里的成员函数还能继续是函数模版

2. 在迭代器区间构造的函数时可以使用函数模版,这样可以使用任意容器的迭代器初始化,例如链表

//迭代器区间// 类模板的成员函数,还可以继续是函数模版//加上一个模板那么迭代器就可以是任意类型的迭代器//需要推导template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}//可以直接使用size_t类型  使用n个val初始化vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}//可以直接使用int类型  使用n个val初始化vector(int n, const T& val = T()){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}


5. 使用memcpy拷贝问题

memcpy拷贝问题的问题其实就是浅拷贝的原因

浅拷贝就是两个指针指向同一块空间,如果一个指针对该空间进行释放或者其他操作就会影响另一个指针导致内存泄漏等问题

所以最好使用深拷贝让两指针指向不同的空间然后使其数据保持一致

错误代码 

//扩容//错误代码void reserve(size_t n){if (n > capacity()){//提前将旧size赋给新sizesize_t old_size = size();//开辟新空间,创建临时变量//new出来的空间是初始化好的,所以可以直接用T* tmp = new T[n];//将旧空间里的数据拷贝给新空间//将 _start指向的size() * sizeof(T)空间里的数据拷贝到临时变量tmp里去memcpy(tmp, _start, size() * sizeof(T));//释放旧空间delete[] _start;//再把三个私有变量指向新空间_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}}

修改之后

//修改之后//扩容void reserve(size_t n){if (n > capacity()){//提前将旧size赋给新sizesize_t old_size = size();//开辟新空间,创建临时变量//new出来的空间是初始化好的,所以可以直接用T* tmp = new T[n];//memcpy(tmp, _start, old_size * sizeof(T));/*如果T是string或者vector类型,就需要进行深拷贝 否则使用浅拷贝会导致内存泄漏*/for (size_t i = 0; i < old_size; i++){//赋值就是string/vector的赋值,也就是深拷贝tmp[i] = _start[i];}//释放旧空间delete[] _start;//再把三个私有变量指向新空间_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}}

感谢观看~


点击全文阅读


本文链接:http://zhangshiyu.com/post/166911.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1