0


【C++练级之路】【Lv.7】【STL】vector类的模拟实现

** 快乐的流畅:个人主页**

** 个人专栏:《C语言》《数据结构世界》《进击的C++》**** 远方有一堆篝火,在为久候之人燃烧!**

文章目录

引言

关于STL容器的学习,我们来到了运用最广泛、最常见的vector。有了之前关于string的学习,我们对容器设计有了一个大概的了解,而今天在熟悉的基础上去探求vector相比于string有哪些异同,同时迎来更多的新挑战……

一、成员变量

vector类中包含了

  • _start(指向有效空间的头)
  • _finish(指向有效空间的尾)
  • _end_of_storage(指向可用空间的尾)

细节:

  1. 三个成员变量均迭代器(此刻即指针)
  2. 使用缺省值,不必写多份初始化列表
template<classT>classvector{public:typedef T* iterator;typedefconst T* const_iterator;private:
    iterator _start =nullptr;
    iterator _finish =nullptr;
    iterator _end_of_storage =nullptr;};

二、默认成员函数

2.1 constructor

无参构造

vector(){}

带参构造

细节:

  1. 分别重载 size_t 和 int 类型,防止参数匹配时,匹配到迭代器区间构造,从而导致间接寻址错误
  2. 初始化的val的缺省值,是匿名构造的对象
vector(size_t n,const T& val =T()){reserve(n);for(size_t i =0; i < n;++i){
        _start[i]= val;}
    _finish = _start + n;}vector(int n,const T& val =T()){reserve(n);for(int i =0; i < n;++i){
        _start[i]= val;}
    _finish = _start + n;}

迭代器区间构造

细节:

  1. 使用类模板,可以传任意类型的迭代器
  2. 迭代器访问,条件最好使用不等于(!=)
template<classInputIterator>vector(InputIterator first, InputIterator last){while(first != last){push_back(*first);++first;}}

2.2 destructor

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

2.3 copy constructor

近代写法

细节:

  1. 先开辟一维空间
  2. 再用赋值重载,进行深拷贝(不能用memcpy,它是浅拷贝)
vector(const vector<T>& x){
    _start =new T[x.capacity()];for(size_t i =0; i < x.size();++i){
        _start[i]= x._start[i];}
    _finish = _start + x.size();
    _end_of_storage = _start + x.capacity();}

现代写法

细节:

  1. 用迭代器区间构造,构造出临时对象
  2. 再使用vector中的swap,交换*this和tmp的值,完成拷贝构造
vector(const vector<T>& x){
    vector<T>tmp(x.begin(), x.end());swap(tmp);}

2.4 operator=

近代写法

细节:大体与拷贝构造相同

vector<T>&operator=(const vector<T>& x){if(this!=&x){
        _start =new T[x.capacity()];for(size_t i =0; i < x.size();++i){
            _start[i]= x._start[i];}
        _finish = _start + x.size();
        _end_of_storage = _start + x.capacity();}return*this;}

现代写法

细节:

  1. 传参变成传值,这样就会拷贝构造出一个临时对象
  2. 再使用vector中的swap,交换*this和tmp的值,完成赋值重载
vector<T>&operator=(vector<T> x){swap(x);return*this;}

三、迭代器

3.1 begin

迭代器的实现和编译器有关,不同的编译器有不同的实现方式。这里用指针来实现迭代器。

同时,重载了普通迭代器和const迭代器。

iterator begin(){return _start;}

const_iterator begin()const{return _start;}

3.2 end

迭代器遵循左闭右开的原则,begin指向首元素,end指向末元素的下一位。

iterator end(){return _finish;}

const_iterator end()const{return _finish;}

悄悄告诉你:范围for的底层实现,就是运用了迭代器。

四、元素访问

4.1 operator[ ]

为了方便的访问元素,我们重载了[ ]运算符。同时,也分为普通版本和const版本,对应不同vector类的权限。

T&operator[](size_t pos){assert(pos <size());return _start[pos];}const T&operator[](size_t pos)const{assert(pos <size());return _start[pos];}

五、容量

5.1 size

获取当前有效数据个数

细节:const修饰,保证普通和const类型vector类都能访问

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

5.2 capacity

获取当前最大有效容量

细节:同上

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

看了上面size和capacity的实现,是不是就瞬间明白_start、_finish和_end_of_storage的含义了?

悄悄告诉你:其实当你不懂成员变量的含义时,可以先看看size和capacity的实现。


5.3 reserve

改变当前最大容量

细节:

  1. 只扩容,不缩容
  2. 用赋值重载,进行深拷贝
  3. 更新成员变量时(如果按照顺序更新),先保存size的大小,防止_finish失效。因为如果为_finish = tmp + size(),等价于_finish = tmp + _finish - _start,而_start已经更新了,所以size()计算的大小失效,最终_finish并没有更新。
voidreserve(size_t n){if(n >capacity()){
        T* tmp =new T[n];if(_start){for(size_t i =0; i <size();++i){
                tmp[i]= _start[i];}delete[] _start;}

        size_t sz =size();
        _start = tmp;
        _finish = tmp + sz;
        _end_of_storage = tmp + n;}}

5.4 resize

改变当前有效数据个数

细节:

  1. 如果n<size,则减少有效个数,如果n>size,则填充指定值,直至达到n个
  2. 运用赋值重载,实现深拷贝
voidresize(size_t n, T val =T()){if(n >size()){reserve(n);for(size_t i =size(); i < n;++i){
            _start[i]= val;}}
    _finish = _start + n;}

5.5 empty

判断是否为空

细节:const修饰,保证普通和const类型vector类都能访问

boolempty()const{return _start == _finish;}

六、修改

6.1 push_back

尾插

细节:需要扩容时,判断容量是否为空

voidpush_back(const T& val){if(_finish == _end_of_storage){reserve(capacity()==0?4:2*capacity());}*_finish = val;++_finish;}

6.2 pop_back

尾删

细节:断言vector不为空,才进行删除

voidpop_back(){assert(!empty());--_finish;}

6.3 insert

指定位置插入

细节:

  1. 断言判断pos的合法性
  2. 扩容前,先保存pos的相对位置,扩容后,刷新pos,防止迭代器失效
  3. 返回指向新插入元素的迭代器,防止迭代器失效
iterator insert(iterator pos,const T& val){assert(pos >= _start && pos <= _finish);if(_finish == _end_of_storage){
        size_t len = pos - _start;reserve(capacity()==0?4:2*capacity());
        pos = _start + len;}

    iterator end = _finish -1;while(end >= pos){*(end +1)=*end;--end;}*pos = val;++_finish;return pos;}

6.4 erase

指定位置删除

细节:

  1. 断言判断pos的合法性
  2. 返回指向删除元素的后一位的迭代器,防止迭代器失效
iterator erase(iterator pos){assert(pos >= _start && pos < _finish);

    iterator start = pos +1;while(start < _finish){*(start -1)=*start;++start;}--_finish;return pos;}

上述有两种迭代器失效:

  1. 野指针
  2. 指向含义改变

关于迭代器失效,我们统一认为,进行过插入或删除操作的迭代器pos,已经失效,不能再使用。只有接收其返回值,刷新pos,才能重新使用。


6.5 swap

交换两个vector类的值

细节:使用std库中的swap函数,交换各个成员变量的值

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

总结

我们在有了学习string的基础后,学习vector的成本降低了不少,函数名和用法大体相同。但是,我们依旧遇到了新的问题与挑战,如多层深拷贝,迭代器失效等。我与C++的故事,仍在无声地诉说……


** 真诚点赞,手有余香 **

标签: c++ 开发语言 stl

本文转载自: https://blog.csdn.net/2301_79188764/article/details/135739145
版权归原作者 快乐的流畅 所有, 如有侵权,请联系我们删除。

“【C++练级之路】【Lv.7】【STL】vector类的模拟实现”的评论:

还没有评论