当前位置: 首页> 教育> 大学 > 【C++】STL——vecot的模拟实现

【C++】STL——vecot的模拟实现

时间:2025/7/11 0:52:23来源:https://blog.csdn.net/2301_77112794/article/details/142214988 浏览次数:0次

目录

  • 前言
  • 总体结构
  • 默认成员函数
    • 构造函数
    • 拷贝构造
    • 赋值重载
    • 析构函数
  • vector的相关容量空间以及访问的实现
    • capacity()和size()
    • 迭代器实现
    • operator[]
    • reserve
  • vector类对象的修改操作
    • 尾插尾删
    • 任意位置插入
    • 任意位置删除
    • 交换和清理

请添加图片描述

前言

  前面我们已经学习了解了vector重要接口的使用:【C++】vector的使用。
  下面我们继续来模拟实现vector,这对学习STL有重大帮助。

总体结构

  同样,vetor在标准库中已经实现好了,因此在模拟实现时我们可以使用命名空间进行隔离,防止命名冲突
  在vector的使用中我们就已经介绍过源码中的vector是如何写的:

namespace bit
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};
}

  和在c语言中的动态顺序表不太一样,vector是由三个指针变量来实现的
在这里插入图片描述

默认成员函数

构造函数

在这里插入图片描述
对照着库里面的构造函数可以模拟实现如下:

//强制生成默认构造
vector() = default;//构造
//函数模板——支持任意迭代器的迭代区间进行初始化
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);first++;}
}
vector(size_t n, const T& val = T())
{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}
vector(int n, const T& val = T())
{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}

注意:
1.当所写函数中没有默认构造时,我们就可以写上一句:

vector() = default;

即可强制编译器生成默认构造,当然直接自己写vector(){}也可以。


2.vector(size_t n, const T& val = T())它的缺省值给的是T(),即匿名对象
我们知道,对匿名对象如果是自定义类型,就调用它的默认构造。如果是内置类型C++对内置类型进行了升级,让其也有默认构造
如:

int k = int();//也是正确的

3.我们还要再写一个vector(int n, const T& val = T())是因为如果不写时,我们写vector< int > v(3,5)时会优先匹配上迭代器构造,此时InputIterator会被替代成为int,而解引用就会报错:

error C2100: 非法的间接寻址

拷贝构造

  在进行拷贝构造前先扩容,可以避免后期频繁扩容会存在过多的内存碎片。

//拷贝构造v3(v2)
vector(const vector<T>& v)
{reserve(v.capacity());for (auto e : v){push_back(e);}//两种写法都可以/*for (size_t i = 0; i < v.size(); i++){push_back(v[i]);}*/
}

  逐个数据赋值拷贝,属于深拷贝,可以避免浅拷贝的问题。

赋值重载

//传统写法
/*vector<T>& operator=(const vector<T>& v)
{if (this != &v){reserve(v.capacity());for (size_t i = 0; i < v.size(); i++){_start[i] = v[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}return *this;
}*///现代写法,都交给编译器去完成
//v1=v3
vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}

  对于现代写法,我们使用传值传参对于自定义类型,编译器会调用它的拷贝构造,即v是v3的一个拷贝构造,直接交换,可使得v1的值换给v,v是一个形参,出了作用域会调用析构函数销毁

析构函数

~vector()
{if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}
}

  我们前面在构造开空间时用的是new[],因此在析构时也要使用delete[]

vector的相关容量空间以及访问的实现

capacity()和size()

  对于vector的一系列增删查改都离不开对空间的判断,看容量是否充足,若不充足则需要扩容,即reserve。
  对于vector而言,获取数据个数size()和容量大小capacity()都还是比较简单的:

size_t capacity() const
{return _end_of_storage - _start;
}
size_t size()const
{return _finish - _start;
}

  vector的三个成员变量都是指针,因此我们直接采用指针-指针的方式即可得到相应的数据。

迭代器实现

  同样,迭代器也是比较简单的,我们可以将其认定为T*的一个原生指针即可,同样还有const迭代器,即const对象对应的只能访问不能修改。

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

operator[]

迭代器主要实现访问的功能,那operator[]也不能少,也比较简单:

T& operator[](size_t n)
{return _start[n];
}

reserve

  当我们想要增加数据时,我们就要判断我们的容量空间是否足够,如果不足就需要先扩容再插入数据,当然这涉及到深浅拷贝的问题:

void reserve(size_t n)
{if (n > capacity()){T* tmp = new T[n];//开辟新空间size_t oldsize = size();//不能省略if (_start){//memcpy(tmp, _start, sizeof(T) * oldsize);//浅拷贝不能使用for(size_t i = 0; i < oldsize; i++){tmp[i] = _start[i];//深拷贝}delete[] _start;//释放旧空间}_start = tmp;_finish = _start + oldsize;_end_of_storage = _start + n;}
}

注意:为什么说对oldsize的定义不能省略
是因为在size()的函数定义中,它是由_start和_finish两个指针相减而来。而后面_start已经到了新空间,而_finish还是属于旧空间上的指针,二者相减就会报错。

在这里插入图片描述
  通过调试可以发现,对于memcpy是浅拷贝会使得tmp和_start的指针同时指向同一块空间,析构则会析构两次而崩溃,因此还是要逐个数据赋值拷贝。

vector类对象的修改操作

尾插尾删

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

  在尾插时要注意判断空间是否足够,不够还要记得扩容。
  尾删时也要判断size是否大于0,避免删除过多导致崩溃。

任意位置插入

iterator insert(iterator pos, const T& x)
{if (_finish == _end_of_storage){size_t len = pos - _start;//不能省略iterator newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;//更新pos,避免变成野指针}iterator end = _finish - 1;while (pos <= end){*(end + 1) = *end;--end;}*pos = x;_finish++;return pos;
}

对于insert可以认为是以下几个步骤:

  1. 判断数据是否需要扩容
  2. 往后挪动数据
  3. 插入数据

  而对于size_t len = pos - _start;pos = _start + len;这两行代码是不能省略的,因为牵扯到扩容,不更新pos就会导致迭代器失效的问题。

任意位置删除

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

  任意位置的删除只需要将该位置后面的数据挪动覆盖即可,同样存在着迭代器pos失效的问题,这在上一节就已经说了,因此我们要有返回值返回被删除元素的下一个元素即可

交换和清理

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

  库里面其实已经提供了std::swap函数,但vector还是有自己的swap函数,是因为库里面的交换函数涉及到拷贝较多,效率较低,而vector自己的交换函数只需要交换指针即可,没有拷贝,效率高


感谢大家观看,如果大家喜欢,希望大家一键三连支持一下,如有表述不正确,也欢迎大家批评指正。
请添加图片描述

关键字:【C++】STL——vecot的模拟实现

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: