当前位置:   article > 正文

C++ stl容器vector的底层模拟实现

C++ stl容器vector的底层模拟实现

目录

前言:  

1.成员变量,容量与大小

2.构造函数

无参构造:

带参的使用值进行构造:

 使用迭代器区间进行构造:

3.交换

4.拷贝构造

5.赋值重载

6.迭代器

7.扩容

reserve:

resize:

8.插入与删除

insert:

erase:

insert迭代器失效问题:

erase迭代器失效问题:

9.头插头删

10.[]重载

11.完整代码与测试

总结:


前言:  

本篇来实现stl容器vector,有了前面string的基础,会实现起来更加的顺畅同样也是挑重要的接口来实现,结尾会附上完整代码。

1.成员变量,容量与大小

  1. public:
  2. typedef T* iterator;
  3. typedef const T* const_iterator;
  4. private:
  5. iterator _start;
  6. iterator _finish;
  7. iterator _end_of_storage;

这里的成员变量都是指针实现的,_start指向开始的位置也就是第一元素,_finish指向最后一个元素的下一个位置,所以是开区间,_end_of_storage是容量大小,也就是指向容器的最后一个位置。

  1. size_t size() const
  2. {
  3. return _finish - _start;
  4. }
  5. size_t capacity() const
  6. {
  7. return _end_of_storage - _start;
  8. }

大小就是最后一个元素的下一个位置减去开始的位置,也就是有效数据的个数。

容量就是可能扩容好的最后的位置减去开始的位置。

注意可以是const成员调用的,所以用const成员修饰函数,这里没有分开const修饰的函数与普通的函数是因为我们实际就算是访问容量与大小也不会修改数据;而像迭代器要分开是因为,我们会使用普通迭代器解引用修改数据,要区分开。

2.构造函数

无参构造:
  1. vector()
  2. :_start(nullptr)//不管调用哪个构造,带参的还是不带参数的,都要给初始化列表,因为不给初始化后成员变量都是随机值;或者是成员变量声明时给缺省
  3. ,_finish(nullptr)
  4. ,_end_of_storage(nullptr)
  5. {}

注意不管是带参的构造还是无参的构造,都要在初始化列表给初始化,因为不然成员变量里面都是随机值;或者是在声明成员变量的时候给上缺省值。

带参的使用值进行构造:
  1. vector(size_t n, const T& val = T())//任意类型都有默认构造,例如模版参数是int也就成0了
  2. :_start(nullptr)
  3. , _finish(nullptr)
  4. , _end_of_storage(nullptr)
  5. {
  6. reserve(n);
  7. for (size_t i = 0; i < n;++i)
  8. {
  9. push_back(val);
  10. }
  11. }
  12. vector(int n, const T& val = T())//没有这个会出现非法的间接寻址的错误,编译器识别不出来两个参数的构造是调用迭代器的那个还是这个。
  13. :_start(nullptr)
  14. , _finish(nullptr)
  15. , _end_of_storage(nullptr)
  16. {
  17. reserve(n);
  18. for (size_t i = 0; i < n; ++i)
  19. {
  20. push_back(val);
  21. }
  22. }

首先参数里面的第二个参数是使用匿名对象进行初始化的,我们要知道c++既然设计了面对对象的特性,那构造就不能只针对自定义类型来说了,或者说构造的时候让编译器取区分自定义类型与内置类型会带来麻烦,所以我们使用匿名对象进行构造初始化,也就是说这个构造的缺省值是T类的对象,例如:

  1. const int& a = int();//匿名对象具有常性
  2. const char& b = char();
  3. int c = int();//任意类型都有默认构造,这是使用匿名对象进行初始化

我们观察调试窗口可以发现:

 这些内置类型使用默认的构造也被初始化为0了。

还有注意匿名对象是具有常性的,所以使用引用接收要加上const修饰 ,而如果使用引用接收匿名对象,匿名对象的生命周期会跟着引用而延长直道引用销毁。

现在我们搞懂了第二个参数,我们再来看看第一个参数为什么要重载成两个形式,因为我们如果直接使用size_t,再结合下面的迭代器的构造,编译器就识别不出了掉用哪一个了(但会选择最合适的,就是迭代器的构造,根据模版推演类型),所以最好还是重载一个,让编译器识别的更全面。

	my_vector::vector<int> v1(10, 2);

 上面的代码会报错如果没有int n这个参数的重载,因为10默认是int,会先优先匹配迭代器构造的模版参数,而不是识别size_t(因为这个会发生类型转换,模版直接就推演了)。

还可以这样解决:

然后函数体内就是根据要初始化的数据个数,进行扩容,再尾插即可。

 使用迭代器区间进行构造:
  1. //类模版的成员函数还可以带模版,这个模版可以用主模板的模版参数,也可以用自己的
  2. template<class InputIterator>
  3. vector(InputIterator first, InputIterator last)//用迭代器区间初始化,这个迭代器区间的类型可以是任何迭代器区间的类型,所以给上模版参数
  4. :_start(nullptr)
  5. , _finish(nullptr)
  6. ,_end_of_storage(nullptr)
  7. {
  8. while (first != last)//不能用小于,假设是链表传过来的迭代器区间,空间不是连续的,不能保证前面的节点的地址就小于后面的
  9. {
  10. push_back(*first);
  11. ++first;
  12. }
  13. }

首先,类模版的成员函数还可以带模版,这个模版可以用主模板的模版参数,也可以用自己的,就是这里会跟上面的带参的构造矛盾。

其次,使用迭代器区间初始化就是保证可以让任意类型的迭代器区间都可以初始化vector,例子已在vector的使用中举过。

然后就是将传过来的迭代器区间一个一个尾插到vector这个容器中,注意判断条件不能使用小于,如果传的迭代器区间的类型是一个list也就是链表,我们知道链表的存储并不是连续的,所以不能保证前面的空间的地址一个小于后面的空间地址。 

3.交换

  1. void swap(vector<T>& v)
  2. {
  3. std::swap(_start, v._start);
  4. std::swap(_finish, v._finish);
  5. std::swap(_end_of_storage, v._end_of_storage);
  6. }

直接调用库中的交换即可,直接写还需要有三个深拷贝。

 注意这里的swap的参数不能是const,如果使用const修饰,那v就不能变了,所以里面的成员指向的空间也不能变,交换可是要交换空间的。

4.拷贝构造

  1. 不传统的拷贝构造,但是是可以的
  2. //vector(const vector<T>& v)
  3. //{
  4. // reserve(v.capacity());
  5. // for (auto e : v)
  6. // {
  7. // push_back(e);//this->push_back(e)
  8. // }
  9. //}
  10. //vector(const vector<T>& v)
  11. //{
  12. // //reserve(v.capacity());
  13. // //扩容也可不复用
  14. // _start = new T[v.capacity()];
  15. // //memcpy(_start, v._start, sizeof(T) * v.size());
  16. // for (size_t i = 0; i < v.size(); ++i)
  17. // {
  18. // _start[i] = v._start[i];//[]就是解引用
  19. // }
  20. // _finish = _start + v.size();
  21. // _end_of_storage = _start + v.capacity();
  22. //}
  23. //很现代的拷贝构造(不对???为什么???要提供两个迭代器区间的构造才能用)
  24. //vector(const vector<T>& v) //语法上支持拷贝构造和赋值不加模版参数
  25. vector(const vector<T>& v)
  26. {
  27. vector<T> tmp(v.begin(), v.end());//这个要提供两个迭代器区间的构造才能用
  28. swap(tmp);
  29. //swap(v);//不能这样直接调用,v的类型不支持swap的参数
  30. }

这里一个提供了3个拷贝构造,第一个我们让它叫做不传统的拷贝构造,因为它利用了范围for,其实就是先根据拷贝的对象扩容,然后再进行赋值尾插到要拷贝的内容中去。

第二拷贝构造是传统的拷贝构造,先扩容再开空间深拷贝,注意这里的赋值就是深拷贝,因为如果假设模版是string类型的,在赋值的时候解引用找到的就是string类型的元素,再赋值就是去调用string内部的赋值重载;而这样使用memcpy是按字节进行拷贝的,所以还会造成拷贝完了,new出来的变量是指向同一块空间的,然后析构两次会出错,并且插入删除数据会混乱。

最后要更新大小与容量。

第三个是更现代的拷贝构造,也就是复用了swap,这样不能直接调用swap,因为swap的参数没有const修饰,而这里的v是const类型的,不匹配,所以要先用要拷贝的对象构造出一个对象,再进行交换。

举一个深拷贝的情形:

其实这里有三层,第一层是直接拷贝,第二层是内置类型的memcpy实现的深拷贝,第三层就是vector嵌套其它深浅拷贝的这种:
 

这里虽然v4和v3不再指向同一块空间了,但memcpy是按字节拷贝的,

这里v4和v3里面的_str却指向同一块空间了(调试可看v3v4里面的原始试图里的string里的_Ptr指针地址是一样的),说明还没有拷贝成功,程序会崩在哪呢?v4先调用一次析构(delete[] 析构会先析构vector上即这个数组上的每一块空间,即先析构v4上的所有_str,再[]析构掉整个v4空间,因为v4是new出来的),v3同理,所以_str所指向的空间都被析构了两次,v4析构完_str空间就已经找不到了,v3再析构就找不到了。

所以我们得出结论:
只要是vector里面嵌套其它的需要深拷贝的,都会涉及到这样的问题,例如vector<vector<int>>,那不用memcpy该怎么解决?使用赋值:

赋值就是深拷贝,如果拷贝类型是string,那就调用string的赋值,string的赋值就是开空间拷贝也就是深拷贝。

内置类型就直接赋值;容器例如sting(vector没有重载赋值)就调用赋值,就会开空间再拷贝,也就是深拷贝。

 

对于vector这样没有重载赋值的,又嵌套使用例如vector<vector<int>>在,这样的,调试可发现外面的vector进行了深拷贝,但是里面的vector还是浅拷贝,原因就是vector没有赋值重载,不能用我们上面的赋值方案解决这样的嵌套,需要自己重载一个赋值:

5.赋值重载

  1. vector<T>& operator=(vector<T>& v)
  2. {
  3. swap(v);
  4. return *this;
  5. }

直接复用即可,这里就可以直接交换了, 参数是匹配的;最后要有返回值,支持连续赋值。

6.迭代器

  1. iterator begin()
  2. {
  3. return _start;
  4. }
  5. iterator end()
  6. {
  7. return _finish;
  8. }
  9. iterator begin() const
  10. {
  11. return _start;
  12. }
  13. iterator end() const//这里的const是修饰的调用者的const,所以调用者不能修改数据;而返回值是如果是const迭代器那就是迭代器不能走了,不能遍历了,不行
  14. {
  15. return _finish;
  16. }

7.扩容

reserve:
  1. void reserve(size_t n)
  2. {
  3. if (n > capacity())
  4. {
  5. size_t sz = size();
  6. T* tmp = new T[n];
  7. if (_start)//如果旧空间为空,就不进if了,直接让旧空间开好的空间;其次也因为if中要对_start解引用
  8. {
  9. //memcpy是浅拷贝,因为按字节拷贝还是两个开辟出了的指针指向同一块空间
  10. //memcpy(tmp,_start,sizeof(T)*size());//这里乘capacity可能会造成浪费,因为capacity开的空间比较多
  11. for (size_t i = 0; i < size(); ++i)
  12. {
  13. tmp[i] = _start[i];//如果模版参数是string这样的自定义类型,而且有开辟的空间,肯定是要深拷贝的,而这里的赋值就会调用string的赋值,符合深拷贝
  14. }
  15. delete[] _start;
  16. }
  17. _start = tmp;
  18. _finish = sz + _start;//虽然扩容了,但是原有的finish的位置不能变,所以上面要记录一下;而且_start也变了,原来的size()就不能用了
  19. _end_of_storage = _start + n;
  20. }
  21. }

 扩容首先要记录大小,因为虽然扩容了,但是_finish与_statr的距离不会变,如果不记录,后面的_start要么销毁要么找不到了,不能使用了。

扩容就是先开空间,然后旧空间内容深拷贝给新空间,释放旧空间,再让旧空间指向新空间,原来在string的实现中以说过。

注意后面的更新需要用原来的旧空间的大小更新(这里就体现了记录原来大小的作用),容量就用扩好的容量更新。

resize:
  1. void resize(size_t n,T val=T())//任意类型都有默认构造
  2. {
  3. if (n < capacity())
  4. {
  5. _finish = _start + n;
  6. }
  7. else
  8. {
  9. if (n > capacity())
  10. {
  11. reserve(n);
  12. }
  13. while ((_start + n) != _finish)
  14. {
  15. *_finish = val;//源码使用的是定位new,但这里的空间都是直接new出来的,定位new针对的是内存池
  16. _finish++;
  17. }
  18. }
  19. }

 如果是传的容量小于原来的容量,就是删除数据,否则就是扩容,然后将扩容后的数据给上初始化的值,默认是0。

扩容如果使用memcpy:

开辟的新空间tmp旧空间_start的_str都指向同一块空间,后面直接delete []掉旧空间即delete[]会对数组上的每个对象调用析构函数,再释放整个空间,然后v3指向新空间,但是新空间的_str都指向释放掉的旧空间了,所以就野指针了,所以扩容也要赋值。

 

8.插入与删除

insert:
  1. iterator insert(iterator pos, const T& val)
  2. {
  3. assert(pos >= _start);
  4. assert(pos <= _finish);
  5. if (_finish == _end_of_storage)
  6. {
  7. size_t len = pos - _start;//虽然扩容了,但是pos与_start的距离不会变,所以记录下来
  8. reserve(capacity() == 0 ? 4 : capacity() * 2);
  9. pos = _start + len;//reserve走完,pos指向的旧空间就找不到或者销毁了,要更新pos的位置,否则会面临迭代器失效的问题
  10. }
  11. iterator end = _finish - 1;
  12. while (pos <= end)
  13. {
  14. *(end + 1) = *end;
  15. --end;//不用担心pos为0,end--变成负的,因为这里是指针
  16. }
  17. *pos = val;
  18. _finish++;
  19. return pos;
  20. }

插入时如果为空,就扩容,然后挪到数据。

注意这里的迭代器失效的问题,这里的迭代器失效是指的野指针的问题,因为pos在走完reserve后pos指向的还是旧空间,但是reserve已经将就旧空间释放了,再使用pos就野指针了,但是pos与_start的距离是不会变的,所以用它们记录这个距离,再reserve后再更新pos就能解决问题。

注意返回插入后的迭代器的位置。

erase:
  1. iterator erase(iterator pos)
  2. {
  3. assert(pos >= _start);
  4. assert(pos < _finish);
  5. iterator start = pos + 1;
  6. while (start != _finish)
  7. {
  8. *(start - 1) = *start;
  9. ++start;
  10. }
  11. --_finish;
  12. return pos;
  13. }

 删除,挪动数据。

insert迭代器失效问题:

首先就是上面的野指针问题,迭代器失效。

其次就是迭代器虽然能用,但不是想要的位置了的问题。

此问题分为两种情况:

第一。如果之前调用过insert了,扩好容了(这个前提很重要),再插入数据就会面临不是想要的位置的问题:

开始调用了一下insert,说明已经扩好容了,要修改3位置的值,但是实际插入完数据pos的位置指向的数据就变了,指向的就是插入的数据30的位置。

这样也是, 开始调一次insert扩好容了,但是pos还是不是想要的位置。

第二种情况,没有扩好容,此时调用insert就需要扩容,但是扩容后pos的位置更新,pos就指向其它的位置了,再使用这个pos就找不到了,再改动数据也没有用。(但是这并不属于野指针,所以不会报错,因为pos并没有被销毁,只是指向了其它的位置。)

如何解决?

能不能用引用解决呢? 

 

不能,因为begin里面是一个传值返回,返回的是临时变量的拷贝,临时变量具有常性,不能权限放大。

使用返回值记录迭代器的位置即可:

但是最好还是不要用insert后的pos,就认为它失效了,因为不知道insert里面什么时候扩容,一旦扩容就要考虑是否失效的问题;库里面实现的效果是,如果不用返回值接收pos的位置,还去使用迭代器的位置,就会断言失败。

erase迭代器失效问题:

首先在vs中:

而g++下,不会报错:

那到底认为erase后pos到底失不失效呢?vs合理还是g++合理呢?

行为结果未定义就是不同环境结果不同。

而实际上,是vs(vs没有使用指针实现迭代器而是封装)更合理,认为失效,因为对于pos删的是最后一个数据的情况,_finish就挪动到删除的数据的位置了,而再去访问pos(pos指向的和_finish一样,而_finish又是开区间)就应该断言失败,而g++还是正确的,所以erase后不要访问pos位置了,认为是失效的 :

再看一个在g++下报错的情况:

vs下肯定报错,erase后就不允许访问迭代器了,而同样的代码在g++下,插入5个数据还没问题,但是4个数据就出现了段错误,连续的偶数还会出现结果不对的情况:

因为erase删除是挪到数据并覆盖数据,但当删除到最后一个数据时,pos位置会++到finish的

后面,而循环条件又是二者相等,这样二者一直不会相等,所以更要确定erase后是迭代器是失效的,指向的位置是无效的:

如何解决?

那该怎么解决呢?和insert的解决方式一样,用返回值接收记录pos的位置,g++,vs都行,但是少用: 

 

string其实在insert和erase也会出现迭代器失效的问题,但是用的少,一般都是用下标访问。 

9.头插头删

  1. void push_back(const T& val)
  2. {
  3. if (_finish == _end_of_storage)
  4. {
  5. reserve(capacity() == 0 ? 4 : capacity()* 2);//不能直接扩容二倍,如果开始是0,就错了;这里走完reserve成员变量都被初始化了
  6. }
  7. *_finish = val;//_finsih不会是空指针,因为如果_finish为空,说明都是_start,_end_of_storage都为空,肯定会走上面的if,然后走reserve就初始化了
  8. _finish++;
  9. }
  10. void pop_back()
  11. {
  12. assert(!empty());
  13. --_finish;//这样就找不到末尾的数据了
  14. }

注意头插扩容与头删判空。判空就是_start==_finish为真就是空。 

10.[]重载

  1. T& operator[](size_t pos)
  2. {
  3. assert(pos < size());
  4. return _start[pos];
  5. }
  6. T& operator[](size_t pos) const
  7. {
  8. assert(pos < size());
  9. return _start[pos];
  10. }

注意提供const版本,const的对象调用[]不能修改本身,但是普通对象调用[]后是可以修改的。 

11.完整代码与测试

  1. #pragma once
  2. #include <iostream>
  3. #include <assert.h>
  4. #include <vector>
  5. #include <string>
  6. #include <string.h>
  7. using namespace std;//不能放到头文件的前面,不然头文件展开后,往下找就找不到库了,头文件就不能用了
  8. namespace my_vector
  9. {
  10. template<class T>
  11. class vector
  12. {
  13. public:
  14. typedef T* iterator;
  15. typedef const T* const_iterator;
  16. vector()
  17. :_start(nullptr)//不管调用哪个构造,带参的还是不带参数的,都要给初始化列表,因为不给初始化后成员变量都是随机值;或者是成员变量声明时给缺省
  18. ,_finish(nullptr)
  19. ,_end_of_storage(nullptr)
  20. {}
  21. vector(size_t n, const T& val = T())//使用匿名对象初始化,例如模版参数是int也就成0了
  22. :_start(nullptr)
  23. , _finish(nullptr)
  24. , _end_of_storage(nullptr)
  25. {
  26. reserve(n);
  27. for (size_t i = 0; i < n;++i)
  28. {
  29. push_back(val);
  30. }
  31. }
  32. vector(int n, const T& val = T())//没有这个会出现非法的间接寻址的错误,编译器识别不出来两个参数的构造是调用迭代器的那个还是这个。
  33. :_start(nullptr)
  34. , _finish(nullptr)
  35. , _end_of_storage(nullptr)
  36. {
  37. reserve(n);
  38. for (size_t i = 0; i < n; ++i)
  39. {
  40. push_back(val);
  41. }
  42. }
  43. 不传统的拷贝构造,但是是可以的
  44. //vector(const vector<T>& v)
  45. //{
  46. // reserve(v.capacity());
  47. // for (auto e : v)
  48. // {
  49. // push_back(e);//this->push_back(e)
  50. // }
  51. //}
  52. //vector(const vector<T>& v)
  53. //{
  54. // //reserve(v.capacity());
  55. // //扩容也可不复用
  56. // _start = new T[v.capacity()];
  57. // //memcpy(_start, v._start, sizeof(T) * v.size());
  58. // for (size_t i = 0; i < v.size(); ++i)
  59. // {
  60. // _start[i] = v._start[i];//[]就是解引用
  61. // }
  62. // _finish = _start + v.size();
  63. // _end_of_storage = _start + v.capacity();
  64. //}
  65. //很现代的拷贝构造(不对???为什么???要提供两个迭代器区间的构造才能用)
  66. //vector(const vector<T>& v) //语法上支持拷贝构造和赋值不加模版参数
  67. vector(const vector<T>& v)
  68. {
  69. vector<T> tmp(v.begin(), v.end());//这个要提供两个迭代器区间的构造才能用
  70. swap(tmp);
  71. //swap(v);//不能这样直接调用,v的类型不支持swap的参数
  72. }
  73. void swap( vector<T>& v)
  74. {
  75. std::swap(_start, v._start);
  76. std::swap(_finish, v._finish);
  77. std::swap(_end_of_storage, v._end_of_storage);
  78. }
  79. ~vector()
  80. {
  81. delete[] _start;//销毁_start指向的这块空间
  82. _start = _finish = _end_of_storage = nullptr;
  83. }
  84. vector<T>& operator=(vector<T>& v)
  85. {
  86. swap(v);
  87. return *this;
  88. }
  89. size_t size() const
  90. {
  91. return _finish - _start;
  92. }
  93. size_t capacity() const
  94. {
  95. return _end_of_storage - _start;
  96. }
  97. iterator begin()
  98. {
  99. return _start;
  100. }
  101. iterator end()
  102. {
  103. return _finish;
  104. }
  105. iterator begin() const
  106. {
  107. return _start;
  108. }
  109. iterator end() const//这里的const是修饰的调用者的const,所以调用者不能修改数据;而返回值是如果是const迭代器那就是迭代器不能走了,不能遍历了,不行
  110. {
  111. return _finish;
  112. }
  113. //类模版的成员函数还可以带模版,这个模版可以用主模板的模版参数,也可以用自己的
  114. template<class InputIterator>
  115. vector(InputIterator first, InputIterator last)//用迭代器区间初始化,这个迭代器区间的类型可以是任何迭代器区间的类型,所以给上模版参数
  116. :_start(nullptr)
  117. , _finish(nullptr)
  118. ,_end_of_storage(nullptr)
  119. {
  120. while (first != last)//不能用小于,假设是链表传过来的迭代器区间,空间不是连续的,不能保证前面的节点的地址就小于后面的
  121. {
  122. push_back(*first);
  123. ++first;
  124. }
  125. }
  126. void reserve(size_t n)
  127. {
  128. if (n > capacity())
  129. {
  130. size_t sz = size();
  131. T* tmp = new T[n];
  132. if (_start)//如果旧空间为空,就不进if了,直接让旧空间开好的空间;其次也因为if中要对_start解引用
  133. {
  134. //memcpy是浅拷贝,因为按字节拷贝还是两个开辟出了的指针指向同一块空间
  135. //memcpy(tmp,_start,sizeof(T)*size());//这里乘capacity可能会造成浪费,因为capacity开的空间比较多
  136. for (size_t i = 0; i < size(); ++i)
  137. {
  138. tmp[i] = _start[i];//如果模版参数是string这样的自定义类型,而且有开辟的空间,肯定是要深拷贝的,而这里的赋值就会调用string的赋值,符合深拷贝
  139. }
  140. delete[] _start;
  141. }
  142. _start = tmp;
  143. _finish = sz + _start;//虽然扩容了,但是原有的finish的位置不能变,所以上面要记录一下;而且_start也变了,原来的size()就不能用了
  144. _end_of_storage = _start + n;
  145. }
  146. }
  147. void push_back(const T& val)
  148. {
  149. if (_finish == _end_of_storage)
  150. {
  151. reserve(capacity() == 0 ? 4 : capacity()* 2);//不能直接扩容二倍,如果开始是0,就错了;这里走完reserve成员变量都被初始化了
  152. }
  153. *_finish = val;//_finsih不会是空指针,因为如果_finish为空,说明都是_start,_end_of_storage都为空,肯定会走上面的if,然后走reserve就初始化了
  154. _finish++;
  155. }
  156. void pop_back()
  157. {
  158. assert(!empty());
  159. --_finish;//这样就找不到末尾的数据了
  160. }
  161. void resize(size_t n,T val=T())//任意类型都有默认构造
  162. {
  163. if (n < capacity())
  164. {
  165. _finish = _start + n;
  166. }
  167. else
  168. {
  169. if (n > capacity())
  170. {
  171. reserve(n);
  172. }
  173. while ((_start + n) != _finish)
  174. {
  175. *_finish = val;//源码使用的是定位new,但这里的空间都是直接new出来的,定位new针对的是内存池
  176. _finish++;
  177. }
  178. }
  179. }
  180. iterator insert(iterator pos, const T& val)
  181. {
  182. assert(pos >= _start);
  183. assert(pos <= _finish);
  184. if (_finish == _end_of_storage)
  185. {
  186. size_t len = pos - _start;//虽然扩容了,但是pos与_start的距离不会变,所以记录下来
  187. reserve(capacity() == 0 ? 4 : capacity() * 2);
  188. pos = _start + len;//reserve走完,pos指向的旧空间就找不到或者销毁了,要更新pos的位置,否则会面临迭代器失效的问题
  189. }
  190. iterator end = _finish - 1;
  191. while (pos <= end)
  192. {
  193. *(end + 1) = *end;
  194. --end;//不用担心pos为0,end--变成负的,因为这里是指针
  195. }
  196. *pos = val;
  197. _finish++;
  198. return pos;
  199. }
  200. iterator erase(iterator pos)
  201. {
  202. assert(pos >= _start);
  203. assert(pos < _finish);
  204. iterator start = pos + 1;
  205. while (start != _finish)
  206. {
  207. *(start - 1) = *start;
  208. ++start;
  209. }
  210. --_finish;
  211. return pos;
  212. }
  213. void empty()
  214. {
  215. return _start == _finish;
  216. }
  217. T& operator[](size_t pos)
  218. {
  219. assert(pos < size());
  220. return _start[pos];
  221. }
  222. T& operator[](size_t pos) const
  223. {
  224. assert(pos < size());
  225. return _start[pos];
  226. }
  227. private:
  228. iterator _start;
  229. iterator _finish;
  230. iterator _end_of_storage;
  231. };
  232. void func(const vector<int>& v)
  233. {
  234. for (size_t i = 0; i < v.size(); ++i)
  235. {
  236. cout << v[i] << " ";
  237. }
  238. cout << endl;
  239. vector<int>::const_iterator it = v.begin();
  240. while (it != v.end())
  241. {
  242. cout << *it << " ";
  243. ++it;
  244. }
  245. cout << endl;
  246. }
  247. void Testvector1()
  248. {
  249. vector<int> v1;
  250. v1.push_back(1);
  251. v1.push_back(2);
  252. v1.push_back(3);
  253. v1.push_back(4);
  254. for (size_t i = 0; i < v1.size(); ++i)
  255. {
  256. cout << v1[i] << " ";
  257. }
  258. cout << endl;
  259. vector<int>::iterator it = v1.begin();
  260. while (it != v1.end())
  261. {
  262. cout << *it << " ";
  263. ++it;
  264. }
  265. cout << endl;
  266. for (auto e : v1)
  267. {
  268. cout << e << " ";
  269. }
  270. cout << endl;
  271. func(v1);
  272. }
  273. //template<class T>
  274. //void f()
  275. //{
  276. // T x = T();//都是初始化为0
  277. // cout << x << endl;
  278. //}
  279. //void test_vector2()
  280. //{
  281. // //内置类型有没有构造函数?没有,但是能这样写
  282. // /*int i = int();这样结果是0
  283. // int j = int(1);*/
  284. // f<int>();//匿名对象
  285. // f<int*>();
  286. // f<double>();
  287. //}
  288. void Testvector2()
  289. {
  290. vector<int> v1;
  291. v1.push_back(1);
  292. v1.push_back(2);
  293. v1.push_back(3);
  294. cout << v1.size() << endl;
  295. cout << v1.capacity() << endl;
  296. v1.resize(10);
  297. cout << v1.size() << endl;
  298. cout << v1.capacity() << endl;
  299. v1.resize(3);
  300. func(v1);
  301. }
  302. void Testvector3()
  303. {
  304. vector<int> v1;
  305. v1.push_back(1);
  306. v1.push_back(2);
  307. v1.push_back(3);
  308. v1.push_back(4);//为什么只插入4个会越界呢?因为只插入4个再调insert会扩容,一扩容pos指向的位置会变,就会面临迭代器失效
  309. //而插入5个数据在push_back的时候就已经扩容了,insert就不再扩容了
  310. /*v1.insert(v1.begin(), 0);
  311. func(v1);*/
  312. auto pos = find(v1.begin(), v1.end(), 3);
  313. if (pos != v1.end())
  314. {
  315. pos = v1.insert(pos, 30);
  316. }
  317. func(v1);
  318. //最好不要用,不知道insert什么时候扩容,扩容就会面临着pos失效的问题
  319. (*pos)++;//想对pos位置++但却对在pos位置插入的数据++了,怎么办?
  320. func(v1);
  321. }
  322. void Testvector4()
  323. {
  324. vector<int> v1;
  325. v1.push_back(1);
  326. v1.push_back(2);
  327. v1.push_back(3);
  328. v1.push_back(4);//为什么只插入4个会越界呢?因为只插入4个再调insert会扩容,一扩容pos指向的位置会变,就会面临迭代器失效
  329. //而插入5个数据在push_back的时候就已经扩容了,insert就不再扩容了
  330. /*v1.insert(v1.begin(), 0);
  331. func(v1);*/
  332. auto pos = find(v1.begin(), v1.end(), 3);
  333. if (pos != v1.end())
  334. {
  335. v1.erase(pos);
  336. }
  337. func(v1);
  338. }
  339. void Testvector5()
  340. {
  341. vector<int> v1;
  342. v1.push_back(1);
  343. v1.push_back(2);
  344. v1.push_back(3);
  345. v1.push_back(4);
  346. vector<int>::iterator it = v1.begin();
  347. while (it != v1.end())
  348. {
  349. if (*it % 2 == 0)
  350. {
  351. it = v1.erase(it);//erase以后就不能访问了,g++可以,还是认为erase后迭代器失效,用返回值接收即可
  352. }
  353. else
  354. {
  355. it++;
  356. }
  357. }
  358. for (auto e : v1)
  359. {
  360. cout << e << " ";
  361. }
  362. cout << endl;
  363. }
  364. void Testvector6()
  365. {
  366. vector<int> v1(10, 5);
  367. for (auto e : v1)
  368. {
  369. cout << e << " ";
  370. }
  371. cout << endl;
  372. }
  373. void Testvector7()
  374. {
  375. vector<int> v1(10, 5);
  376. for (auto e : v1)
  377. {
  378. cout << e << " ";
  379. }
  380. cout << endl;
  381. vector<int> v2(v1);//不写构造,对于动态开辟的new出来的需要深拷贝,默认的值拷贝就不行了
  382. for (auto e : v2)
  383. {
  384. cout << e << " ";
  385. }
  386. cout << endl;
  387. vector<std::string> v3(3, "1111111111111111111");
  388. for (auto e : v3)
  389. {
  390. cout << e << " ";
  391. }
  392. cout << endl;
  393. vector<std::string> v4(v3);
  394. for (auto e : v4)
  395. {
  396. cout << e << " ";
  397. }
  398. cout << endl;
  399. v4.push_back("2222222");
  400. v4.push_back("2222222");
  401. v4.push_back("2222222");
  402. for (auto e : v4)
  403. {
  404. cout << e << " ";
  405. }
  406. }
  407. }

总结:

本篇的重点就是拷贝构造和迭代器失效的问题,很重要,后面的容器的实现还会提及。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/546570
推荐阅读
相关标签
  

闽ICP备14008679号