当前位置： 首页 > news >正文

模拟实现c++中的vector模版

news 2025/8/15 15:09:47

 

目录

一·vector简述：

二·vector的一些接口函数：

1·初始化：

2.vector增长：

3·vector增删查改：

三·vector模拟实现部分主要函数：

1.size,capacity,empty,clear接口： 

2.reverse的实现： 

3.resize的实现：

 4.访问运算符重载operator[]的实现：

5.push_back与pop_back的实现：

 6.erase的实现：

7.insert的实现：

8·swap的实现：

9.拷贝构造的实现：

10.赋值重载的实现：

11.构造和析构函数的实现：

12.vector以及容器通用打印的实现：

四·vector模拟实现过程中遇到的问题总结：

1.迭代器失效问题简述：

2.vector类内类型省略问题：

3.迭代器运算符问题：

五·模拟vector代码汇总：

一·vector简述：

它可以认为是一个动态容器，即一种顺序表。通过给这个模版实例化可以得到一种任意类型的顺序表，故可以放进去数据，则使用前应该先实例化类型。

二·vector的一些接口函数：

1·初始化：

无参构造：
vector<int> v1;有参：
vector<int> v2(10,1);
v2拷贝构造给v3
vector<int>v3(v2);
迭代器初始化：
vector<int> v4(++v2.begin(),v2.end()--);//把v2部分范围给v4初始化

2.vector增长：

如：size；capacity（vs是1.5倍扩，g++为2倍）；empty；resize；reserve（不缩容）；等函数接口用法类似于上篇string用法。

3·vector增删查改：

如：push_back;pop_back;find(这时algorithm算法库内的函数，也是使用迭代器区间：找到了返回指向那个位置的迭代器，否则返回右区间)；insert;erase;swap;operator[],v.front;v.back等用法和string相差不大，可以说是string的下标换成vector的迭代器了。

注：这里对于vector的重载函数没有cin和cout。

三·vector模拟实现部分主要函数：

首先要知道这个模拟过程如图一样：

由于是类模版，一般定义和声明不能分文件，故可以都写在.h文件：

首先先不写构造，但是编译器默认生成的构造来，可能会给成员变量野指针，故给它一个缺省值为nullptr； 提前也要写好析构。

 

这里的iterator是迭代器类型可以粗略认为是指针，假设模版参数是T，故typedef一下：

typedef T* iterator;typedef const T* const_iterator;iterator begin() {return _start;
}iterator end() {return _finish;
}const_iterator cbegin()const {return _start;
}const_iterator cend() const {return _finish;
}

分别对可以修改和不允许修改的对象都有了对应的迭代器。

1.size,capacity,empty,clear接口： 

 

size_t size() const
{return _finish - _start;
}size_t capacity() const
{return _end_of_storage - _start;
}bool empty()
{return _start == _finish;
}void clear()
{_finish = _start;
}

2.reverse的实现： 

注：①这里用了一个oldsize记录为扩容之前的size；因为假设进行第一次扩容 ，_start更新后;_finish+的size（）（_finish-_start）就会不是原来的size了；故需要保存一下这个相对位置。

②这里一开始用的是string.h里的memcpy ，利用的是浅拷贝，如果让里面的类型是自定义（有资源申请已经释放的）发现浅拷贝这样会出问题，故后面改正。

3.resize的实现：

 void resize(size_t n, const T& value = T()) {if (n < size()) {size_t tmp = size();while (tmp > n) {_finish--;tmp--;}}else {reserve(n);for (size_t i = size(); i < n; i++){push_back(value);}}}

如果size小于给的n，就扩大size（capacity()也要跟上）；后面用value填充，如果大于就相当于截断。对于缺省参数：如果未给值就会掉此类型默认构造（T（）为匿名对象）,对于内置类型如：char，int等这就是'\0',0。如果是自定义类型：就是它的默认构造函数构造出的对象。

 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];}

分别对应的是const类型对象和普通对象的调用。

5.push_back与pop_back的实现：

 void push_back(const T& x) {if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;}void pop_back() {assert(!empty());_finish--;}

 

 6.erase的实现：

iterator erase(iterator pos) {assert(pos < _finish&&pos>=_start);iterator end = pos + 1;while (end < _finish) {*(end - 1) = *end;end++;}_finish--;return pos;}

7.insert的实现：

这里以insert的实现为例子，把它进行类内声明，类外定义；

//类内：iterator insert(iterator pos, const T& x);//类外：
template<class T>
typename vec::vector<T>::iterator vec::vector<T>::insert(typename vec::vector<T>::iterator pos, const T& x) 
//类模版未初始化不能进类内确定它是静态成员变量还是类型，故若是类型要typename一下{size_t len = 0;if (_finish == _end_of_storage){len = pos - _start;//迭代器失效：由于空间变了，pos无法找到指向原来空间，而数据早已被移到了新空间，原来的也被释放reserve(capacity() == 0 ? 4 : capacity() * 2);}if (len != 0) {pos = _start + len;}iterator end = _finish;while (end >= pos) {*end = *(end - 1);end--;}*pos = x;_finish++;return pos;
}

这里和erase一样涉及迭代器失效问题于后面总结进行讲解。

8·swap的实现：

swap也为后面对于拷贝构造和赋值重载的现代版本使用奠定基础。

void swap(vector<T>& v) {std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}

9.拷贝构造的实现：

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

可能前面写的函数程序都运行正常，当写完这个拷贝构造发现编译器会报错：

 

原因：其实拷贝构造函数也是一种构造函数，而当我们写了拷贝构造，编译器自己就不会生成它的默认构造了（普通构造也没写）；因此他会走这个拷贝构造，但发现参数不匹配，就会报错，因此这时要再把默认构造或者传参的构造写上就可以了。 

10.赋值重载的实现：

  //s1=s3vector<T>& operator= (vector<T> v) {swap(v);//如果不引用参数，则会进行拷贝再swap，这时候s3给s1赋值后它自身不会变。return *this;}

11.构造和析构函数的实现：

     //默认构造1：
/*vector() {}*//如果这个默认构造{}内可以没有，只用它的初始化列表，但也有缺省值了就可以这么写。//  默认构造2：（c++11）vector() = default;vector(int n, const T& value = T()) {reserve(n);for (size_t i = 0; i < n; i++){push_back(value);}}
//迭代器区间初始化：//模版函数，可以用别的类型的函数，故完成一个容器数据到另一个容器转换template<class InputIterator>vector(InputIterator first, InputIterator last) {while (first != last) {push_back(*first);//一个容器数据放另一个，数据类型要匹配，否则进不去。first++;}}//析构：~vector() {if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}

这里用了类模版内套着模版函数：方便了不同类型 的迭代器区间去放入这个容器，如list：

12.vector以及容器通用打印的实现：

//vector专属的打印：
template<class x>
void  Print(const vec::vector<x>& t) {//未实例化的模版无法去访问内部，区分不了是静态成员变量还是类型//typename vec::vector <x>::const_iterator it = t.cbegin();auto it = t.cbegin();while (it != t.cend()){std::cout << *it << " ";++it;}std::cout << std::endl;
}
template<typename C>
void Print_container(const C &cr ) {auto it = cr.cbegin();while (it != cr.cend()){std::cout << *it << " ";++it;}std::cout << std::endl;}

 

四·vector模拟实现过程中遇到的问题总结：

1.迭代器失效问题简述：

失效分为两种，第一种是迭代器指向无效内存了即空间变化了，第二种是所引用的对象发生变化了，都是迭代器失效。这时候建议不要在对它这个位置迭代器进行访问了；否则程序崩溃。

这里举erase和insert的例子：

这里如果对insert插入如果没有空间开辟也可以认为迭代器失效，但是有的时候可以继续访问，但是一般建议用返回值重新赋值再使用，而开辟空间了则一定失效，必然要重新赋值。

erase的迭代器如果此位置对象被删除，也要重新赋值再用此迭代器。

例子：

这里就涉及到了erase造成的迭代器失效：前面正常打印当到0；之后由于继续访问就崩掉了。

 

这时候要想正常需要利用它的返回值来重新赋值进行后面的访问：

 

2.vector类内类型省略问题：

如果在类内那么对于类型vector<T>可以在类内变成vector等价代替，但是如果在类外就不可能了。

3.迭代器运算符问题：

这里如果first和last如果是迭代器的话那么为什么不用大于小于呢，理论上针对vector是可以的，但是比如它空间不是连续的list链表就是反例，这时候大于小于就没概念了。前提还得是空间要连续。 

五·模拟vector代码汇总：

#pragma once
#pragma once
#include<iostream>
#include<assert.h>
#include<algorithm>
#include<string.h>namespace vec{template<class T>class vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin() {return _start;}iterator end() {return _finish;}const_iterator cbegin()const {return _start;}const_iterator cend() const {return _finish;}//默认构造1：/*vector() {}*///  默认构造2：（c++11）vector() = default;vector(int n, const T& value = T()) {reserve(n);for (size_t i = 0; i < n; i++){push_back(value);}}//模版函数，可以用别的类型的函数，故完成一个容器数据到另一个容器转换template<class InputIterator>vector(InputIterator first, InputIterator last) {while (first != last) {push_back(*first);//一个容器数据放另一个，数据类型要匹配，否则进不去。first++;}}//拷贝构造：：vector(const vector<T>& v) {reserve(v.capacity);for(auto a:v ){push_back(a);}}//s1=s3vector<T>& operator= (vector<T> v) {swap(v);//如果不引用参数，则会进行拷贝再swap，这时候s3给s1赋值后它自身不会变。return *this;}~vector() {if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}//    // capacitysize_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}bool empty(){return _start == _finish;}void clear(){_finish = _start;}void reserve(size_t n) {if (n > capacity()) {size_t oldsize = size();//开辟空间前后导致指针指向空间不同T * tmp = new T [n];// memcpy(tmp, _start, sizeof(T) * size());一个个字节的浅拷贝for (int i = 0; i < size(); i++) {tmp[i] = _start[i];//利用string库里的赋值运算符重载}//自定义类型使用深拷贝delete[]_start;_start = tmp;_finish = tmp + oldsize;//防止_start已经更新，而这里要的是以前的相对位置，故保存一下_end_of_storage = _start + n;}}void resize(size_t n, const T& value = T()) {if (n < size()) {size_t tmp = size();while (tmp > n) {_finish--;tmp--;}}else {reserve(n);for (size_t i = size(); i < n; i++){push_back(value);}}}//    ///access///T& operator[](size_t pos) {assert(pos < size());return _start[pos];}const T& operator[](size_t pos)const {assert(pos < size());return _start[pos];}//    ///modify/void push_back(const T& x) {if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;}void pop_back() {assert(!empty());_finish--;}void swap(vector<T>& v) {std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}iterator insert(iterator pos, const T& x);iterator erase(iterator pos) {assert(pos < _finish&&pos>=_start);iterator end = pos + 1;while (end < _finish) {*(end - 1) = *end;end++;}_finish--;return pos;}private:iterator _start = nullptr; // 指向数据块的开始iterator _finish = nullptr; // 指向有效数据的尾iterator _end_of_storage = nullptr; // 指向存储容量的尾};}template<class T>
typename vec::vector<T>::iterator vec::vector<T>::insert(typename vec::vector<T>::iterator pos, const T& x) 
//类模版未初始化不能进类内确定它是静态成员变量还是类型，故若是类型要typename一下{size_t len = 0;if (_finish == _end_of_storage){len = pos - _start;//迭代器失效：由于空间变了，pos无法找到reserve(capacity() == 0 ? 4 : capacity() * 2);}if (len != 0) {pos = _start + len;}iterator end = _finish;while (end >= pos) {*end = *(end - 1);end--;}*pos = x;_finish++;return pos;
}//vector专属的打印：
template<class x>
void  Print(const vec::vector<x>& t) {//未实例化的模版无法去访问内部，区分不了是静态成员变量还是类型//typename vec::vector <x>::const_iterator it = t.cbegin();auto it = t.cbegin();while (it != t.cend()){std::cout << *it << " ";++it;}std::cout << std::endl;
}
template<typename C>
void Print_container(const C &cr ) {auto it = cr.cbegin();while (it != cr.cend()){std::cout << *it << " ";++it;}std::cout << std::endl;}

 

http://www.lryc.cn/news/408249.html

相关文章：

  • uniapp安卓通过绝对路径获取文件
  • Known框架实战演练——进销存业务单据
  • 解决npm依赖树冲突的方法以及npm ERR! code ERESOLVE错误的解决方案
  • Spring Boot + Spring Batch + Quartz 整合定时批量任务
  • C++STL简介（二）
  • 嵌入式高频面试题100道及参考答案（3万字长文）
  • python爬虫-事件触发机制
  • LeetCode-day27-3106. 满足距离约束且字典序最小的字符串
  • C++中的static_cast函数
  • 从零开始学习网络安全渗透测试之基础入门篇——（二）Web架构前后端分离站Docker容器站OSS存储负载均衡CDN加速反向代理WAF防护
  • 2679. 矩阵中的和
  • Unity Playables：下一代动画与音频序列
  • matlab仿真 模拟调制（下）
  • RabbitMQ是什么？
  • 追问试面试系列：分布式id
  • 护网紧急情况应对指南：Linux 应急响应手册
  • WEB攻防-通用漏洞-SQL 读写注入-MYSQLMSSQLPostgreSQL
  • 【前端学习笔记】CSS基础一
  • Github遇到的问题解决方法总结（持续更新...）
  • 数字信封+数字签名工具类测试样例（Java实现）
  • The Schematic workflow failed. See above.
  • 操作系统面试知识点总结4
  • Lua实现面向对象以及类的继承
  • 机器学习课程学习周报五
  • vue3.0学习笔记（二）——生命周期与响应式数据（ref,reactive,toRef,toRefs函数）
  • C++——QT：保姆级教程，从下载到安装到用QT写出第一个程序
  • 掌握互联网路由选择协议：从基础入门到实战
  • [笔记]ONVIF服务端实现[进行中...]
  • 深度强化学习 ②（DRL）
  • 线性代数重要知识点和理论(下)