0
0

【C++】—— vector模拟实现

vector 接口预览

namespace HL
{template<classT>classvector{//迭代器iteratortypedef T* iterator;typedefconst T* const_iterator;public://默认成员函数vector();vector(size_t n,const T& val =T());vector(int n,const T& val =T());vector(const vector& v);template<classInputIterator>vector(InputIterator first, InputIterator last);~vector();
        vector<T>&operator=(vector v);//Iterator
        iterator&begin();
        iterator&end();
        const_iterator begin()const;
        const_iterator&end()const;//Capacity
        size_t size()const;
        size_t capacity()const;boolempty()const;voidreserve(size_t n);voidresize(size_t n,const T& val =T());//Modifiersvoidpush_back(const T& val);voidpop_back();voidinsert(iterator pos,const T& val);template<classInputIterator>voidinsert(iterator pos, InputIterator first, InputIterator last);
        iterator erase(iterator pos);voidswap(vector<T>& v);//Element access:
        T&operator[](size_t i);const T&operator[](size_t i)const;private:
        iterator start;
        iterator finish;
        iterator end_of_storage;};};

vector模拟实现

vector成员变量

​ vector成员变量，和顺序表的成员变量有所不同，不再是指针、size和capacity了，而是迭代器 start、finish和end_of_storage。
在这里插入图片描述

start指向起始位置、finish指向最后一个数据的下一个位置（表示数据的末尾）、end_of_storage指向这一块空间的最后。

默认成员函数

构造函数

1、无参构造

​ 无参构造，就是默认构造函数，将成员变量都初始化成nullptr。

vector():start(nullptr),finish(nullptr),end_of_storage(nullptr){}
2、构造并初始化成n个val值

​ 理论上，我们只需要写一个函数vector(size_t n, const T& val = T());即可，但是如果两个参数都是int类型，（即vector v(5,1);）编译器在编译时，认为T已经实例化成了int，对于两个int类型，编译器就会选择更为匹配的模版

template vector(InputIterator first, InputIterator last);

所以这里写一个vector(int n, const T& val = T()); 让上面这种情况匹配这个函数。

vector(size_t n,const T& val =T()){
    start =new T[n];for(size_t i =0; i < n; i++){
        start[i]= val;}
    end_of_storage = finish = start + n;}vector(int n,const T& val =T()){
    start =new T[n];for(int i =0; i < n; i++){
        start[i]= val;}
    end_of_storage = finish = start + n;}
3、使用一段迭代器区间进行初始化

​ 使用迭代器区间进行初始化，这里不一定是vector的迭代器，所以写成模板。

template<classInputIterator>vector(InputIterator first, InputIterator last){
            size_t sz = last - first;
            start =new T[sz];
            finish = start;while(first != last){*finish =*first;++finish;++first;}
            end_of_storage = start + sz;}
4、拷贝构造

​ 这里要注意，需要深拷贝，而不是浅拷贝。

vector(const vector& v){
            size_t sz = v.size();
            size_t cp = v.capacity();
            start =new T[sz];for(int i =0; i < sz; i++){
                start[i]= v[i];}
            finish = start + sz;
            end_of_storage = start + cp;}

析构函数

​ 析构函数比较简单，释放动态开辟的空间即可。

~vector(){if(start)delete[] start;
            start = finish = end_of_storage =nullptr;}

赋值运算符重载

​ 赋值运算符重载，这个编译器自动生成的是浅拷贝，我们需要写一个深拷贝的。

这里有多种写法，首先就是传统写法，我们自己释放、开辟空间再拷贝数据

        vector<T>&operator=(const vector& v){if(start)delete[] start;
            size_t sz = v.size();
            start =new T[sz];for(int i =0; i < sz; i++){
                start[i]= v[i];}
            finish = end_of_storage = start + sz;}

​ 还有现代写法，我们这里传参不使用引用，而使用传值传参；这样生成的形参对象再与我们的this(对象)进行交换；这样形参出了作用域就自动调用析构函数，不用我们去处理了。（这个需要先实现交换函数）

        vector<T>&operator=(vector v){swap(v);return*this;}

​ 注意事项： 在赋值的过程中没有使用memcpy函数，因为这个函数只是将数值拷贝过去(浅拷贝)；

如果我们vector 示例化是vector 这样的自定义类型，使用浅拷贝就可能会出现问题；所以这里采用一个一个进行赋值操作，这样就会去调用自定义类型的赋值运算符重载；而不只是简单的浅拷贝了。

iterator 迭代器

​ vector 的迭代器这里实现的是原生指针；迭代器相关函数：begin()、end()这些都比较简单就不过多描述了。

//迭代器iteratortypedef T* iterator;typedefconst T* const_iterator;
        iterator&begin(){return start;}
        iterator&end(){return finish;}
        const_iterator begin()const{return start;}
        const_iterator&end()const{return finish;}

Capacity

​ capacity容量相关的函数，主要在于调整空间大小和设置内容。

size、capacity、empty

        size_t size()const{return finish - start;}
        size_t capacity()const{
            end_of_storage - start;}boolempty()const{return start == finish;}

reserve

​ reserve，调整空间大小；即扩容。

voidreserve(size_t n){if(n >capacity()){
                iterator tmp = T[n];
                size_t sz =size();for(int i =0; i < sz; i++){
                    tmp[i]= start[i];}if(start)delete[] start;
                start = tmp;
                finish = start + sz;
                end_of_storage = start + n;}}

resize()

voidresize(size_t n,const T& val =T()){reserve(n);if(n <size()){
                finish = start + n;}else{for(int i =size(); i < n; i++){
                    start[i]= val;}
                finish = start + n;}}

Modifiers

​ modifiers 增删查改、vector头插头删效率很低，就不提供头插头删接口了。

push_back、pop_back

​ 尾差、尾删，直接在vector最后插入删除数据。

voidpush_back(const T& val){if(capacity()==size()){
                size_t n =(capacity()==0)?4:2*capacity();reserve(n);}*finish = val;++finish;}voidpop_back(){assert(start != finish);--finish;}

insert

insert函数，在某个位置插入n(可以是1)个数据。或者插入一段迭代器区间的数据。

iterator insert(iterator pos,const T& val){// 空间不够先进行增容if(finish == end_of_storage){
        size_t newCapacity =(capacity()==0)?1:capacity()*2;reserve(newCapacity);// 如果发生了增容，需要重置pos
        pos = _start +size();}//挪动数据
    iterator p = finish;while(p != pos){*p =*(p -1);--p;}*pos = val;
    finish +=1;return pos;}template<classInputIterator>voidinsert(iterator pos, InputIterator first, InputIterator last){//这里如果迭代器不是原生指针或者内存空间不连续就不能进行 - 操作了
    size_t sz = last - first;
    size_t n = pos - start;reserve(sz +size());
    pos = start + n;//挪数据
    iterator p = finish -1;while(p >= pos){*(p + sz)=*p;--p;}//插入数据for(size_t i =0; i < sz; i++){
        pos[i]= first[i];}
    finish += sz;}

​ 这里，扩容之后还用一个迭代器失效问题，需要重新给pos赋值。

erase

​ erase就是删除某个位置的数据，直接将后面数据往前移动即可

        iterator erase(iterator pos){
            size_t sz = finish - pos;for(int i =0; i < sz; i++){
                pos[i]= pos[i +1];}
            finish -=1;return pos;}

clear、swap

voidswap(vector<T>& v){
            std::swap(start, v.start);
            std::swap(finish, v.finish);
            std::swap(end_of_storage, v.end_of_storage);}voidclear(){
            finish = start;}

Element access

operator[ ]

​ 下标访问，直接返回start[i]即可。

        T&operator[](size_t i){return start[i];}const T&operator[](size_t i)const{return start[i];}

代码总览

#pragmaonce#include<iostream>#include<assert.h>namespace HL
{template<classT>classvector{//迭代器iteratortypedef T* iterator;typedefconst T* const_iterator;public://默认成员函数vector():start(nullptr),finish(nullptr),end_of_storage(nullptr){}vector(size_t n,const T& val =T()){
            start =new T[n];for(size_t i =0; i < n; i++){
                start[i]= val;}
            end_of_storage = finish = start + n;}vector(int n,const T& val =T()){
            start =new T[n];for(int i =0; i < n; i++){
                start[i]= val;}
            end_of_storage = finish = start + n;}vector(const vector& v){
            size_t sz = v.size();
            size_t cp = v.capacity();
            start =new T[sz];for(int i =0; i < sz; i++){
                start[i]= v[i];}
            finish = start + sz;
            end_of_storage = start + cp;}template<classInputIterator>vector(InputIterator first, InputIterator last){
            size_t sz = last - first;
            start =new T[sz];
            finish = start;while(first != last){*finish =*first;++finish;++first;}
            end_of_storage = start + sz;}~vector(){if(start)delete[] start;
            start = finish = end_of_storage =nullptr;}/*vector<T>& operator=(vector v)
        {
            swap(v);
            return *this;
        }*/
        vector<T>&operator=(const vector& v){if(start)delete[] start;
            size_t sz = v.size();
            start =new T[sz];for(int i =0; i < sz; i++){
                start[i]= v[i];}
            finish = end_of_storage = start + sz;}//Iterator
        iterator&begin(){return start;}
        iterator&end(){return finish;}
        const_iterator begin()const{return start;}
        const_iterator&end()const{return finish;}//Capacity
        size_t size()const{return finish - start;}
        size_t capacity()const{
            end_of_storage - start;}boolempty()const{return start == finish;}voidreserve(size_t n){if(n >capacity()){
                iterator tmp = T[n];
                size_t sz =size();for(int i =0; i < sz; i++){
                    tmp[i]= start[i];}if(start)delete[] start;
                start = tmp;
                finish = start + sz;
                end_of_storage = start + n;}}voidresize(size_t n,const T& val =T()){reserve(n);if(n <size()){
                finish = start + n;}else{for(int i =size(); i < n; i++){
                    start[i]= val;}
                finish = start + n;}}//Modifiersvoidpush_back(const T& val){if(capacity()==size()){
                size_t n =(capacity()==0)?4:2*capacity();reserve(n);}*finish = val;++finish;}voidpop_back(){assert(start != finish);--finish;}
        iterator insert(iterator pos,const T& val){// 空间不够先进行增容if(finish == end_of_storage){
                size_t newCapacity =(capacity()==0)?1:capacity()*2;reserve(newCapacity);// 如果发生了增容，需要重置pos
                pos = _start +size();}//挪动数据
            iterator p = finish;while(p != pos){*p =*(p -1);--p;}*pos = val;
            finish +=1;return pos;}template<classInputIterator>voidinsert(iterator pos, InputIterator first, InputIterator last){//这里如果迭代器不是原生指针或者内存空间不连续就不能进行 - 操作了
            size_t sz = last - first;
            size_t n = pos - start;reserve(sz +size());
            pos = start + n;//挪数据
            iterator p = finish -1;while(p >= pos){*(p + sz)=*p;--p;}//插入数据for(size_t i =0; i < sz; i++){
                pos[i]= first[i];}
            finish += sz;}
        iterator erase(iterator pos){
            size_t sz = finish - pos;for(int i =0; i < sz; i++){
                pos[i]= pos[i +1];}
            finish -=1;return pos;}voidswap(vector<T>& v){
            std::swap(start, v.start);
            std::swap(finish, v.finish);
            std::swap(end_of_storage, v.end_of_storage);}voidclear(){
            finish = start;}//Element access:
        T&operator[](size_t i){return start[i];}const T&operator[](size_t i)const{return start[i];}private:
        iterator start;
        iterator finish;
        iterator end_of_storage;};};

到这里，vector模拟实现就结束了，希望你能有所收获

感谢各位大佬支持并指出问题

​ 如果本篇内容对你有帮助，可以一键三连支持以下，感谢支持！！！

img

标签： c++ 开发语言
本文转载自: https://blog.csdn.net/LH__1314/article/details/142702293
版权归原作者 努力学习的小廉 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【C++】—— vector模拟实现”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

C#与C++交互开发系列（二十）：跨进程通信之共享内存（Shared Memory）

hadoop技术实验- 第4章 HBase 开发：使用Java操作HBase

智能对话微信前端小程序设计与开发

前端配置开发环境：新电脑配置前端开发环境，Vue开发环境配置的详细过程

SpringBoot集成MQTT服务器和客户端并通过WebSocket将消息实时发送到前端（本地搭建MQTT服务器）

idea | 搭建 SpringBoot 项目之配置 Maven

Python毕业设计选题：基于django+vue的全国民宿信息管理系统

文章导航