当前位置:   article > 正文

初阶C++——STL——string类、vector类和list类(使用方法+模拟实现+测试+思路分析)_c++ stringlist

c++ stringlist

从今天开始,我们正式进入STL的学习。

我们今天会重点讲解三个类——string vector 和 list

目录

STL简介

STL版本

STL的六大组件:

STL的缺陷:(了解)

string类

介绍

string类的常用结构说明

1、常见构造类

2、容量操作类 

3、string类对象的访问及遍历操作​

4、string类对象的修改操作

5、string类非成员函数

string类的模拟实现

vector的使用

vector常用结构说明

1、vector定义(构造)类

2、vector与string相类似的部分

3、vector 迭代器失效问题。

vector的模拟实现

list类 

list 的用法简介

list的构造函数

list的迭代器

其他成员函数 

list的模拟实现(重头戏)


在介绍之前,我们可以先来了解一下,何为STL?它有多少个版本?以及它的优势和缺陷。

STL简介

STL版本

截至今天,目前认为:STL有四大版本:

原始版本(HP版本)
Alexander Stepanov、Meng Lee 在惠普实验室完成的原始版本,本着开源精神,他们声明允许任何人任意运用、拷贝、修改、传播、商业使用这些代码,无需付费。唯一的条件就是也需要向原始版本一样做开源使用。 HP 版本--所有STL实现版本的始祖。


P. J. 版本
由P. J. Plauger开发,继承自HP版本,被Windows Visual C++采用,不能公开或修改,缺陷:可读性比较低,符号命名比较怪异。

RW版本
由Rouge Wage公司开发,继承自HP版本,被C+ + Builder 采用,不能公开或修改,可读性一般。

SGI版本
由Silicon Graphics Computer Systems,Inc公司开发,继承自HP版本。被GCC(Linux)采用,可移植性好,可公开、修改甚至贩卖,从命名风格和编程 风格上看,阅读性非常高。我们后面学习STL要阅读部分源代码,主要参考的就是这个版本。

STL的六大组件:

仿函数;算法;迭代器;空间配置器;容器;配接器。

STL的缺陷:(了解)

1. STL库的更新太慢了。这个得严重吐槽,上一版靠谱是C++98,中间的C++03基本一些修订。C++11出来已经相隔了13年,STL才进一步更新。
2. STL现在都没有支持线程安全。并发环境下需要我们自己加锁。且锁的粒度是比较大的。
3. STL极度的追求效率,导致内部比较复杂。比如类型萃取,迭代器萃取。
4. STL的使用会有代码膨胀的问题,比如使用vector/vector/vector这样会生成多份代码,当然这是模板语法本身导致的

今天,我们将学习其中的三个类——string类、vector类、list类。

string类

介绍

我们先来说一说它的用法,然后再来讲解其模拟实现。

首先我们来简单地介绍一下string类:(了解)

1. 字符串是表示字符序列的类
2. 标准的字符串类提供了对此类对象的支持,其接口类似于标准字符容器的接口,但添加了专门用于操作单字节字符字符串的设计特性。
3. string类是使用char(即作为它的字符类型,使用它的默认char_traits和分配器类型(关于模板的更多信息,请参阅basic_string)。
4. string类是basic_string模板类的一个实例,它使用char来实例化basic_string模板类,并用char_traits和allocator作为basic_string的默认参数(根于更多的模板信息请参basic_string)。
5. 注意,这个类独立于所使用的编码来处理字节:如果用来处理多字节或变长字符(如UTF-8)的序列,这个类的所有成员(如长度或大小)以及它的迭代器,将仍然按照字节(而不是实际编码的字符)来操作。
 

string类的常用结构说明

1、常见构造类

我们可以访问相关的网站来看一下:

 框~~可以看到,有这么多函数都可以作为构造函数。

我们介绍几个常用的:

重点来看这么几个:

像上面几种写法,都是可以的。

注意,其隐藏了'\0',用户即便在调式的时候也是看不见的。

实际上,还可以直接用赋值操作,编译器底层会将其优化为先调用一次构造函数,再调用一次拷贝构造

2、容量操作类 

可以看到,又有不少。

我们介绍一下下面这几个,并举出例子(一块说了) 

 

注意:

1. size()与length()方法底层实现原理完全相同,引入size()的原因是为了与其他容器的接口保持一致,一般情况下基本都是用size()。
2. clear()只是将string中有效字符清空不改变底层空间大小
3. resize(size_t n) resize(size_t n, char c)都是将字符串中有效字符个数改变到n个,不同的是当字符个数增多时:resize(n)用0来填充多出的元素空间resize(size_t n, char c)用字符c来填充多出的元素空间。注意:resize在改变元素个数时,如果是将元素个数增多,可能会改变底层容量的大小,如果是将元素个数减少,底层空间总大小不变。
4. reserve(size_t res_arg=0):为string预留空间,不改变有效元素个数,当reserve的参数小于
string的底层空间总大小时,reserver不会改变容量大小。

3、string类对象的访问及遍历操作

 我们主要来介绍上面这么几个:

上面8个分别是返回正向、逆向、常量的迭代器。

下面的是运用的操作符重载函数完成的。

说到这个访问,于是我们就引出了三种常见的遍历访问方式:

  1. #include<iostream>
  2. #include<string>
  3. using namespace std;
  4. int main()
  5. {
  6. string s = "hello jxwd"; //其会转换成temp("hello jxwd"),然后拷贝构造到s中.
  7. //1、迭代器
  8. string::iterator it = s.begin();//也可以去定义反向迭代器,反向遍历。
  9. while (it != s.end())
  10. {
  11. cout << *it;
  12. it++;
  13. }
  14. cout << endl;
  15. //2for+operator[]
  16. for (size_t i = 0; i < s.size(); i++)
  17. {
  18. cout << s[i];
  19. }
  20. cout << endl;
  21. //3、范围for
  22. for (char e : s)
  23. {
  24. cout << e;
  25. }
  26. cout << endl;
  27. return 0;
  28. }

4、string类对象的修改操作

  

 至于功能是什么,上面已经写得很清楚了。

我们现在用这些函数来举几个例子:

  1. #include<iostream>
  2. #include<string>
  3. using namespace std;
  4. int main()
  5. {
  6. string s1 = "hello ";
  7. cout << s1 << endl;
  8. s1 += "jxwd";//其相当于s1.append("jxwd");
  9. cout << s1 << endl;
  10. s1.push_back(' ');
  11. s1.push_back('i');
  12. s1.push_back(' ');
  13. s1.push_back('l');
  14. s1.push_back('o');
  15. s1.push_back('v');
  16. s1.push_back('e');
  17. s1.push_back(' ');
  18. s1.push_back('y');
  19. s1.push_back('o');
  20. s1.push_back('u');
  21. cout << s1 << endl;
  22. cout << s1.c_str() << endl;
  23. return 0;
  24. }

我们接着来说一下substr接口:

 通过上述文献的索引,我们可以直到,substr是从pos的为止开始,向后len个字符为止,返回值为这中间的字符串。

注意到这里的npos是size_t类型的-1,就是说,其是最大的那个数。

 我们再来说一下find接口:

可以看到,其有4种重载形式,每一种也分别代表了不同的含义。

而rfind和find的意思差不多,其主要是从后面去找。

 我们把substr和find接口联系在一块来举个例子:

  1. #include<iostream>
  2. #include<string>
  3. using namespace std;
  4. int main()
  5. {
  6. //获得file的后缀
  7. string file("string.cpp");
  8. size_t pos = file.rfind('.');
  9. cout << pos << endl;
  10. string suffix(file.substr(pos, file.size() - pos));//这里就相当于是suffix(file.substr(6,4));
  11. cout << suffix << endl;
  12. return 0;
  13. }

 我们再来举一个find 和substr结合的例子:

 注意到这样一个接口,和上面的find的四种重载形式,

就是说,我们这里的find可以指定从某一位置开始找,也可以指定在某一范围开始找。(注:如果找不到,则返回-1)

可以找string,可以找C类型的字符串,还可找单个字符。

  1. #include<iostream>
  2. #include<string>
  3. using namespace std;
  4. int main()
  5. {
  6. //打印出下面链接的域名
  7. string url("http://www.cplusplus.com/reference/string/string/find/");
  8. cout << url << endl;
  9. size_t start = url.find("://"); //先找 :// ,找到,返回:位置的下标,找不到,返回npos
  10. if (start == string::npos)
  11. {
  12. cout << "invalid url" << endl;
  13. return -1;
  14. }
  15. start += 3; //让其向后偏移三个位置
  16. size_t finish = url.find('/', start); //start的位置开始向后找,找'/'
  17. string address = url.substr(start, finish - start); //截取finish到start位置中间的字串
  18. cout << address << endl;
  19. return 0;
  20. }

 删除和插入:

 这两者我想笔者都不用再过多的举例,文献当中已经说的很清楚了。

5、string类非成员函数

实际上,这些我们已经不需要再举过多的例子了,相信各位已经或多或少地会用了。我们在后面的模拟实现中会具体地说到其原理。

string类的模拟实现

实际上,用博客的形式来介绍还是比较生硬的,但是不妨碍能够将其说清楚。

好长一大段。

下面,笔者将耐心地为大家一点一点解释。

  1. #include<iostream>
  2. #include<string.h>
  3. #include<assert.h>
  4. namespace jxwd
  5. {
  6. class string
  7. {
  8. /*string(const string& s)
  9. :_str(new char[strlen(s._str+1)])
  10. {
  11. strcpy(_str, s._str);
  12. }*///传统写法
  13. //string& operator=(const string& s)
  14. //{
  15. /*if (this != &s)
  16. {
  17. delete[] _str;
  18. _str = new char[strlen(s._str) + 1];
  19. strcpy(_str, s._str);
  20. }
  21. return *this;*///传统写法
  22. //}
  23. public:
  24. typedef char* iterator;
  25. typedef const char* const_iterator;
  26. iterator begin() //定义迭代器
  27. {
  28. return _str; //可读可写
  29. }
  30. iterator end() //同理,定义end()函数返回的迭代器,这里,我们用指针来去实现
  31. { //注意其返回的是最后一个元素的下一个位置
  32. return _str + _size;
  33. }
  34. const_iterator begin() const
  35. {
  36. return _str; //仅可读版本
  37. }
  38. const_iterator end() const
  39. {
  40. return _str + _size;
  41. }
  42. string(const char* str = "", size_t capacity = 1,size_t size = 0) //构造函数
  43. {
  44. _str = new char[strlen(str) + 1]; //先创建这么大的空间
  45. if (capacity > strlen(str))_capacity = capacity; //如果现有容量比其小,则现有容量扩大至新的容量大小
  46. else _capacity = strlen(str); //(这取决于你传过来的capacity有多大)
  47. _size = _capacity;
  48. strcpy(_str, str); //在自己开辟的_str里,将str的内容拷贝过来。
  49. }
  50. ~string() //析构函数
  51. {
  52. delete[] _str;
  53. _str = nullptr;
  54. _size = _capacity = 0;
  55. }
  56. void swap(string& s) //自己创建的swap函数
  57. {
  58. std::swap(_str, s._str);
  59. std::swap(_size,s._size);
  60. std::swap(_capacity, s._capacity);
  61. }
  62. string(const string& s) //拷贝构造函数 在创建类的时候调用
  63. :_str(nullptr) //初始化三个成员变量 即this指针指向的对象
  64. ,_size(0)
  65. ,_capacity(0)
  66. {
  67. string tmp(s._str); //调用其构造函数
  68. std::swap(_str, tmp._str); //可以直接swap(tmp);
  69. std::swap(_size,tmp._size); //将其三个量全部交换
  70. std::swap(_capacity,tmp._capacity);
  71. }
  72. string& operator=(string s)
  73. {
  74. std::swap(_str, s._str); //直接调用库中的swap 函数,将变量的内容交换
  75. return *this; //可以直接swap(s),这样的 话调用的是jxwd::swap
  76. }//现代写法 地址会变 //返回*this
  77. char& operator[](size_t i) //操作符重载,重载[]操作符//可读可写
  78. {
  79. assert(i < _size);
  80. return _str[i];
  81. }
  82. const char& operator[](size_t i) const //操作符重载,重载[]操作符//仅读
  83. {
  84. assert(i < _size);
  85. return _str[i];
  86. }
  87. const char* c_str() const //c_str函数,用于返回其数组
  88. {
  89. return _str;
  90. }
  91. size_t size() const //返回数组元素的大小
  92. {
  93. return _size;
  94. }
  95. void reserve(size_t n) //reserve函数,用于重置空间
  96. {
  97. if (n > _capacity) //开空间,扩展capacity,如果传过来的n>_capacity才开辟,否则就当视而不见
  98. {
  99. char* tmp = new char[n + 1]; //动态开辟n+1个(最后一个用于存放'\0')
  100. strncpy(tmp, _str,_size); //拷贝,将原先_str里面的_size个数据全部拷贝到tmp里面。
  101. delete[] _str; //销毁原有的_str
  102. _str = tmp; //让_str指向tmp
  103. _capacity = n; //_capacity赋值成n
  104. }
  105. }
  106. void resize(size_t n , char val = '\0')
  107. { //开空间+初始化,并且可能拓展capacity
  108. if (n < _size)
  109. {
  110. _size = n;
  111. _str[_size] = '\0'; //要注意需要在最后位置放上'\0'
  112. }
  113. else
  114. {
  115. if (n > _capacity)
  116. {
  117. reserve(n);
  118. }
  119. for (size_t i = _size; i < n; i++)
  120. {
  121. _str[i] = val;
  122. }
  123. _str[n] = '\0';
  124. _size = n;
  125. }
  126. }
  127. void push_back(char ch) //尾插
  128. {
  129. if (_size == _capacity) //如果空间不够,则自动扩容
  130. {
  131. reserve(_capacity == 0 ? 4 : _capacity*2);
  132. }
  133. _str[_size] = ch; //将最后原先最后一个位置赋值成ch
  134. _str[_size + 1] = '\0'; //然后将下一个位置赋值成'\0'
  135. _size++; //让_size自增。因为push_back后元素多了一个
  136. }
  137. void append(const char* str) //这就是在后面增加了一个字符串
  138. {
  139. size_t len = _size + strlen(str);
  140. if (len > _capacity) //先计算是否需要扩容
  141. {
  142. reserve(len);
  143. }
  144. strcpy(_str + _size, str); //再将str拷贝至_str+_size的位置
  145. _size = len; //重新赋值_size的值
  146. }
  147. string& insert(size_t pos, char ch) //在pos的位置插入ch 很像顺序表的插入
  148. {
  149. assert(pos <= _size); //先断言,判断能否去插入
  150. if (_size == _capacity)
  151. {
  152. reserve(_capacity * 2); //计算是否需要扩容
  153. }
  154. size_t end = _size + 1; //计算新的容量大小
  155. while (end > pos)
  156. {
  157. _str[end] = _str[end - 1]; //模拟顺序表的插入
  158. end--;
  159. }
  160. _str[pos] = ch;
  161. _size++;
  162. return *this;
  163. }
  164. string& insert(size_t pos, const char* str) //与上面的构成重载,插入一个字串
  165. {
  166. assert(pos <= _size);
  167. size_t len = strlen(str);
  168. if (_size + len > _capacity)
  169. {
  170. reserve(_size + len); //和上面一样,该断言断言,该开空间就开空间
  171. }
  172. char* end = _str + _size + len; //标注出尾部的地址
  173. while (end >= _str + pos) //同样地道理向后移动,腾出来len个空间
  174. {
  175. *(end + 1) = *end;
  176. end--;
  177. }
  178. strncpy(_str + pos, str, len); //同样道理去拷贝
  179. _size += len; //_size重新计算
  180. }
  181. string& erase(size_t pos,size_t len = npos) //同理,相当于顺序表的尾删
  182. {
  183. size_t leftLen = _size - pos; //如果len缺省,就是从pos的位置,向后全删了
  184. if (len > leftLen) //如果len > leftLen还要大,那就全删了
  185. {
  186. _str[pos] = '\0'; //注意'\0'
  187. _size = pos;
  188. }
  189. else
  190. { //否则
  191. strcpy(_str + pos, _str + pos + len); //直接将后面的元素连着'\0'一块,拷到前面的位置
  192. _size -= len; //重新计算_size
  193. }
  194. }
  195. string& operator+=(char ch) //重载+= ,如果是加等一个字符,主要是调用push_back
  196. {
  197. push_back(ch);
  198. return *this;
  199. }
  200. string& operator+=(const char* str) //如果是+=一个字串,就调用append
  201. {
  202. append(str);
  203. return *this;
  204. }
  205. size_t find(char ch, size_t pos = 0) //find函数,主要就是一个一个去遍历寻找,找到了就返回下标,否则,返回npos
  206. { //这是找字符
  207. for (size_t i = pos; i < _size; i++)
  208. {
  209. if (_str[i] == ch)
  210. {
  211. return i;
  212. }
  213. }
  214. return npos;
  215. }
  216. size_t find(const char* str, size_t pos = 0)
  217. {
  218. const char* ret = strstr(_str, str); //这是找字串,直接调用strstr函数
  219. if (ret)
  220. {
  221. return ret - _str;
  222. }
  223. else
  224. {
  225. return npos;
  226. }
  227. }
  228. void clear() //清除所有数据
  229. {
  230. _size = 0;
  231. _str[_size] = '\0';
  232. }
  233. std::istream& getline(std::istream& cin, string& s) //getline函数,主要获取一行的信息
  234. {
  235. s.clear(); //首先是清楚所有数据,
  236. char ch;
  237. ch = cin.get();
  238. while (ch != '\n') //然后一个一个字符获取,直到获取到'\n'为止
  239. {
  240. s += ch;
  241. ch = cin.get();
  242. }
  243. return cin; //定义要求返回输入流
  244. }
  245. private: //这里定义其私有类
  246. char* _str; //由于是字串,我们定义一个数组
  247. size_t _size; //并且定义出其容量和元素个数的大小
  248. size_t _capacity;
  249. static const size_t npos; //定义一个静态变量npos,我们等会会看到在外部去定义,定义其为-1.
  250. };
  251. //接下来的都是运算符重载
  252. inline bool operator<(const string& s1, const string& s2) //关系运算符的重载
  253. {
  254. return strcmp(s1.c_str(), s2.c_str()) < 0; //直接调用strcmp函数
  255. }
  256. inline bool operator>(const string& s1, const string& s2) //下面的直接复用上面的
  257. {
  258. return !(s1 <= s2);
  259. }
  260. inline bool operator==(const string& s1, const string& s2) //同上
  261. {
  262. return strcmp(s1.c_str(), s2.c_str()) == 0;
  263. }
  264. inline bool operator<=(const string& s1, const string& s2)
  265. {
  266. return s1 < s2 || s1 == s2;
  267. }
  268. inline bool operator>=(const string& s1, const string& s2)
  269. {
  270. return!(s1 < s2);
  271. }
  272. inline bool operator!=(const string& s1, const string& s2)
  273. {
  274. return !(s1 == s2);
  275. }
  276. std::ostream& operator<<(std::ostream& cout, string& s) //输出一个字串
  277. {
  278. for (auto ch : s) //一个一个输出直到将s内容全部输出(遇到空格 Tab和回车都会停止输出)
  279. {
  280. cout << ch;
  281. }
  282. return cout;
  283. }
  284. std::istream& operator>>(std::istream& cin, string& s) //输入一个字串
  285. {
  286. s.clear();
  287. char ch;
  288. ch = cin.get(); //调用cin.get()函数
  289. while (ch != ' ' && ch != '\n') //一个一个输入,直到遇到空格、换行符或者Tab
  290. {
  291. s += ch;
  292. ch = cin.get();
  293. }
  294. return cin;
  295. }
  296. const size_t string::npos = -1; //定义静态变量为-1(由于其是size_t,所以其为很大很大的数)
  297. }

各位可以复制到本地的ide中去看。

我们可以测试测试。

比如:(测试用例:)

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<string.h>
  4. #include<assert.h>
  5. namespace jxwd
  6. {
  7. void test_string1()
  8. {
  9. string s1("hello world");
  10. string s2(s1);
  11. std::cout << s1.c_str() << std::endl;
  12. std::cout << s2.c_str() << std::endl;
  13. string s3("hello bit");
  14. s1 = s3;
  15. std::swap(s1, s3);//效率低
  16. }
  17. void test_string2()
  18. {
  19. string s1("hello world");
  20. s1[0] = 'x';
  21. std::cout << s1[0] << std::endl;
  22. std::cout << s1.c_str() << std::endl;
  23. }
  24. void test_string3()
  25. {
  26. string s1("hello bit");
  27. string::iterator it = s1.begin();
  28. while (it != s1.end())
  29. {
  30. std::cout << *it << " ";
  31. it++;
  32. }
  33. for (auto ch : s1)//会被替代成迭代器,是有迭代器支持的
  34. {
  35. std::cout << ch << " ";
  36. }
  37. std::cout << std::endl;
  38. }
  39. void test_string4()
  40. {
  41. string s1("hello");
  42. s1 += '!';
  43. s1.resize(8, 'z');
  44. std::cout << s1.c_str() << std::endl;
  45. s1.resize(1, 's');
  46. std::cout << s1.c_str() << std::endl;
  47. s1.resize(3);
  48. std::cout << s1.c_str() << std::endl;
  49. }
  50. void test_string5()
  51. {
  52. string s1("hello ljx");
  53. std::cout << s1.find("hel") << std::endl;
  54. }
  55. }
  56. using namespace std;
  57. int main()
  58. {
  59. jxwd::test_string1();
  60. jxwd::test_string2();
  61. jxwd::test_string3();
  62. jxwd::test_string4();
  63. jxwd::test_string5();
  64. return 0;
  65. }

我们得出:

我们下面来看vector.

vector的使用

与string同理,vector实际上与string有许许多多的地方都是一样的。

有关vector的一些说明:

1. vector是表示可变大小数组的序列容器。
2. 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
3. 本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小。
4. vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何,重新分配都应该是对数增长的间隔大小,以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。 因此,vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长。
5. 与其它动态序列容器相比(deques, lists and forward_lists), vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作,效率更低。比起lists和forward_lists统一的迭代器和引用更好

相比于string而言,vector甚至更简单。因为其不需要再末尾考虑'\0'的问题了。

对于vector的学习,我们同样的道理,还是借助于文档来完成。

vector常用结构说明

1、vector定义(构造)类

 可以看出,密密麻麻的,我们根据具体的用法简化一下:

我们可以这样构造

 第一个:无参构造;

第二个:构造并初始化n个val;

第三个:拷贝构造                    //也就是文档中的copy

第四个:用迭代器进行构造。

还需要注意的是:

我们可以看到,其定义出来的时候,需要一个模板参数,所以,我们在定义vector类的时候就需要加上这么个模板参数,形成显式模板转换,要不然就会出错。

我们来举几个例子:

 如上图所示。各种方法已经标出。

2、vector与string相类似的部分

 我们之前说过,vector和string有许许多多类似的地方。

接下来,我们将对比学习。

首先,是二者的迭代器。一样的用法:

再次,是vector的增删查改。

看不出来什么不一样。

 

并且,vector的空间增容等问题与string基本也是一样的。

 这些东西,笔者就不再赘述了,如果以后遇到了问题,可以先于string类进行比较,然后如果有具体问题我们再做补充。

3、vector 迭代器失效问题。

迭代器的主要作用就是让算法能够不用关心底层数据结构,其底层实际就是一个指针,或者是对指针进行了封装。

比如:vector的迭代器就是原生态指针T*。因此迭代器失效,实际就是迭代器底层对应指针所指向的空间被销毁了,而使用一块已经被释放的空间,造成的后果是程序崩溃

(即如果继续使用已经失效的迭代器,程序可能会崩溃)

对于vector可能会导致其迭代器失效的操作有:

1. 会引起其底层空间改变的操作,都有可能是迭代器失效,比如:resize、reserve、insert、assign、push_back等。

它们实际上都是由于底层可能会增容导致。我们在string类的模拟实现中就提到过,如果增容用的是calloc,也就是说vector底层原理旧空间被释放掉,而在打印时,it还使用的是释放之间的旧空间,在对it迭代器操作时,实际操作的是一块已经被释放的空间,而引起代码运行时崩溃那么其迭代器所指向的那部分空间,就很有可能失效了。

那有什么解决办法呢?

解决方式:在以上操作完成之后,如果想要继续通过迭代器操作vector中的元素,只需给it重新
赋值即可。

2、指定位置删除元素——erase

  1. #include <iostream>
  2. using namespace std;
  3. #include <vector>
  4. int main()
  5. {
  6. int a[] = { 1, 2, 3, 4 };
  7. vector<int> v(a, a + sizeof(a) / sizeof(int));
  8. // 使用find查找3所在位置的iterator
  9. vector<int>::iterator pos = find(v.begin(), v.end(), 3);
  10. // 删除pos位置的数据,导致pos迭代器失效。
  11. v.erase(pos);
  12. cout << *pos << endl; // 此处会导致非法访问
  13. return 0;
  14. }

erase删除pos位置元素后,pos位置之后的元素会往前搬移,没有导致底层空间的改变,理论上讲迭代器不应该会失效,但是:如果pos刚好是最后一个元素,删完之后pos刚好是end的位置,而end位置是没有元素的,那么pos就失效了。

因此删除vector中任意位置上元素时,vs就认为该位置迭代器失效了。

迭代器失效解决办法:在使用前,对迭代器重新赋值即可

关于底层: 

我们给个图来理解一下:

注意:其不一定直接在原位置上开辟新空间。其可能是另外开辟,然后其拷贝,再释放旧空间的过程。

vector的模拟实现

  1. #include<iostream>
  2. #include<assert.h>
  3. using namespace std;
  4. namespace ljx
  5. {
  6. template <class T>
  7. class vector
  8. {
  9. public:
  10. typedef T* iterator; //定义出迭代器,可以看出,这里底层是用指针来实现的
  11. typedef const T* const_iterator;
  12. vector() //构造函数,实际上,构造函数应当有重载的形式
  13. :_start(nullptr)
  14. , _finish(nullptr)
  15. , _endofstorage(nullptr)
  16. {}
  17. vector(int a, int b) //构造函数的重载形式 fill 的形式
  18. :_start(nullptr)
  19. ,_finish(nullptr)
  20. ,_endofstorage(nullptr)
  21. {
  22. for (int i = 0; i < a; i++)
  23. this->push_back(b);
  24. }
  25. vector(const vector<T>& v) //拷贝构造 也可以用交换的方法
  26. {
  27. _start = new T[v.capacity()]; //首先开辟空间,首地址返回给_start
  28. _finish = _start; //_finish 给_start
  29. _endofstorage = _start + v.capacity(); //计算尾部的容量
  30. for (size_t i = 0; i < v.size(); i++)
  31. {
  32. *_finish = v[i];
  33. ++_finish;
  34. }
  35. }
  36. /*
  37. vector(const vector<T>& v)
  38. :_start(nullptr)
  39. ,_finish(nullptr)
  40. ,_endofstorage(nullptr)
  41. {
  42. reserve(v.capacity());
  43. for(const auto e : v)
  44. push_back(e);//可以直接调?!
  45. }
  46. */
  47. vector<T>& operator=(const vector<T>& v) //赋值构造
  48. {
  49. if (this != &v)
  50. {
  51. delete[] _start;
  52. _start = new T[v.capacity()];
  53. memcpy(_start, v._start, sizeof(T) * v.size);
  54. }
  55. return *this;
  56. }
  57. //还可以这样写:
  58. /*vector<T>& operator=(vector<T> v)
  59. {
  60. ::swap(_start, v._start);
  61. ::swap(_finish, v._finish);
  62. ::swap(_endofstorage, v._endofstorage);//可以把它们合成一个Swap函数
  63. return *this;
  64. }*/
  65. //如果要交换,不建议直接swap.因为会有三个深拷贝
  66. //可以用v1.swap(v2),这样只是三个指针的拷贝
  67. void print_vector() const //打印
  68. {
  69. vector v = *this;
  70. vector<int>::const_iterator it = v.begin();
  71. while (it != v.end())
  72. {
  73. cout << *it << " ";
  74. it++;
  75. }
  76. cout << endl;
  77. }
  78. size_t size() const //返回size,即元素个数
  79. {
  80. return _finish - _start;
  81. }
  82. size_t capacity() const //返回capacity,即容量大小
  83. {
  84. return _endofstorage - _start;
  85. }
  86. void reserve(size_t n) //重新定义空间大小
  87. {
  88. if (n > capacity())
  89. {
  90. size_t sz = size();
  91. T* tmp = new T[n]; //重新在新的为止上开辟空间
  92. if (_start)
  93. {
  94. //memcpy(tmp, _start, sizeof(T) * sz);
  95. for (size_t i = 0; i < sz; i++)
  96. {
  97. tmp[i] = _start[i];//如果T是string等自定义类型,那么这样就会按照string的深拷贝来进行
  98. } //注意,这里不能用memcpy.因为memcpy所对应的是浅拷贝,只是按照二进制,将对应的地址拷贝过去
  99. delete[] _start;
  100. }
  101. _start = tmp;
  102. _finish = tmp + sz;
  103. _endofstorage = tmp + n;
  104. }
  105. }
  106. const_iterator begin() const //定义返回头部第一个元素的迭代器
  107. {
  108. return _start; //仅可读
  109. }
  110. const_iterator end() const //定义返回尾部的迭代器
  111. {
  112. return _finish; //仅可读
  113. }
  114. iterator begin()
  115. {
  116. return _start;
  117. }
  118. iterator end()
  119. {
  120. return _finish;
  121. } //
  122. void push_back(const T& x) //尾插
  123. {
  124. if (_finish == _endofstorage) //问:是否要增容?
  125. {
  126. size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
  127. reserve(newcapacity);
  128. }
  129. *_finish = x;
  130. _finish++;
  131. }
  132. T& operator[](size_t i) //重载[]运算符
  133. {
  134. assert(i < size());
  135. return _start[i];
  136. }
  137. T& operator[](size_t i) const //第二个版本
  138. {
  139. assert(i < size());
  140. return _start[i];
  141. }
  142. void pop_back() //尾删
  143. {
  144. assert(_start < _finish);
  145. --_finish;
  146. }
  147. void insert(iterator pos, const T& x) //插入
  148. {
  149. assert(pos <= _finish);
  150. if (_finish == _endofstorage) //判断是否要增容
  151. {
  152. size_t n = pos - _start;
  153. size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
  154. reserve(newcapacity);
  155. pos = _start + n;
  156. }
  157. iterator end = _finish - 1;
  158. while (end >= pos) //向后移动
  159. {
  160. *(end + 1) = *end;
  161. --end;
  162. }
  163. *pos = x; //在pos位置插入
  164. ++_finish;
  165. }
  166. iterator erase(iterator pos) //删除
  167. {
  168. assert(pos < _finish);
  169. iterator it = pos; //把后面的位置往前移动
  170. while (it < _finish)
  171. {
  172. *it = *(it + 1);
  173. ++it;
  174. }
  175. --_finish; //减减最后元素的门神
  176. return pos;
  177. }
  178. void resize(size_t n,const T& val = T()) //重新开辟元素空间大小
  179. {
  180. if (n < this->size())
  181. {
  182. _finish = _start + n; //问:是否比我原有的size要大?
  183. }
  184. else
  185. {
  186. if (n > capacity()) //问:是否要增容
  187. {
  188. reserve(n);
  189. }
  190. while (_finish < _start + n) //接下来,就将剩下的新增元素初始化为val
  191. {
  192. *_finish = val;
  193. ++_finish;
  194. }
  195. }
  196. }
  197. private:
  198. iterator _start; //左指针
  199. iterator _finish; //左闭右开,右指针
  200. iterator _endofstorage; //容量的尾部
  201. };
  202. }

我们可以来测试一下:

(让主函数去调用这两个函数)

  1. void test_vector1()
  2. {
  3. vector<int> v;
  4. v.push_back(1);
  5. v.push_back(2);
  6. v.push_back(3);
  7. v.push_back(4);
  8. v.push_back(5);
  9. vector<int>::iterator it = v.begin();
  10. while (it != v.end())
  11. {
  12. cout << *it << " ";
  13. ++it;
  14. }
  15. cout << endl;
  16. }
  17. void test_vector2()
  18. {
  19. vector<int> v;
  20. v.push_back(1);
  21. v.push_back(2);
  22. v.push_back(3);
  23. v.push_back(4);
  24. v.push_back(5);
  25. vector<int>::iterator it = v.begin();
  26. while (it != v.end())
  27. {
  28. if (*it % 2 == 0)
  29. {
  30. it = v.erase(it);
  31. }
  32. else
  33. {
  34. it++;
  35. }
  36. }
  37. v.print_vector();
  38. }

我们得到:

ok。有关vector的内容暂且介绍到这里,后期我们刷题时还会重新见面的。

list类 

对于list类,我们重点说其迭代器的模拟实现。

如果说vector是一个数组,是一个顺序表,那么list就是一个链表。

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
2. list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。
4. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息
 

如果要更准确地说,我们的list 是双向循环带头链表。

list 的用法简介

关于list的用法,实际上,我们通过查看文档就是可以理解的。因为我们已经有了上面string和vector的基础了。

list的构造函数

我们可以看到,其构造的方式有4种。

简而言之,我们可以用迭代器区间去进行构造,可以直接去填充,也可以进行拷贝。

举几个例子:

  1. int main(){
  2. std::list<int> l1; // 构造空的l1
  3. std::list<int> l2 (4,100); // l2中放4个值为100的元素
  4. std::list<int> l3 (l2.begin(), l2.end()); // 用l2的[begin(), end())左闭右开的区间构
  5. 造l3
  6. std::list<int> l4 (l3); // 用l3拷贝构造l4
  7. // 以数组为迭代器区间构造l5
  8. int array[] = {16,2,77,29};
  9. std::list<int> l5 (array, array + sizeof(array) / sizeof(int) );
  10. // 用迭代器方式打印l5中的元素
  11. for(std::list<int>::iterator it = l5.begin(); it != l5.end(); it++)
  12. std::cout << *it << " ";
  13. std::cout<<endl;
  14. // C++11范围for的方式遍历
  15. for(auto& e : l5)
  16. std::cout<< e << " ";
  17. std::cout<<endl;
  18. return 0;
  19. }

 那么链表有两种遍历方式。

一种是用显示的迭代器去遍历;

还有一种是用范围for(本质上还是迭代器)(如上述代码)

list的迭代器

1. begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动

这些东西和string、vector几乎都是一样的,就是要注意的是其是循环的。这个链表的思路我们在数据结构的时候就曾说过。

其他成员函数 

 我们这里就说一个:assign(其余的我们将在模拟实现的时候一笔带过)

它的意思就是说,先把原有的链表内容清空,然后将n个val的值拷贝入新的链表中。

我们再说一个:

 

用于拼接,就是说,我能将list& x拼接到list中(就是调用该函数的类)

后面的二者是迭代器,即拼接的范围。  

注意:在list中,使用insert后,原本的迭代器不会失效。但是在使用erase时,使用完的迭代器便会失效。

list的模拟实现(重头戏)

在此之前,我们需要将一个思想:

由于list的底层在存储的时候地址不是连续的,但是我们有需要实现++;--;*等运算操作,我们需要自己构建一个迭代器类,将其封装起来然后使用。这也是我们模拟实现list的重点。

 

 我们接下来进行模拟实现:

  1. #include<iostream>
  2. #include<assert.h>
  3. namespace jxwd
  4. {
  5. template<class T>
  6. struct _list_node //该结构体是为了要构建结点(即链表的结点)
  7. {
  8. T val;
  9. _list_node<T>* _next;
  10. _list_node<T>* _prev;
  11. _list_node(const T& x = T())
  12. :val(x)
  13. ,_next(nullptr)
  14. ,_prev(nullptr)
  15. {}
  16. };
  17. template <class T ,class Ref ,class Cal> //封装着迭代器的类
  18. struct _list_iterator
  19. {
  20. typedef _list_node<T> node; //而在这里,我就是想要进行一个浅拷贝
  21. typedef _list_iterator<T,Ref,Cal> self; //所以这里拷贝构造、operator、析构我们不写,编译器默认生成的就可以用
  22. node* _pnode; //定义一个_pnode结点,即用于迭代器的底层实现——实际上就是一个链表结点的指针
  23. _list_iterator(node* pnode) //迭代器类的构造函数
  24. :_pnode(pnode)
  25. { }
  26. Ref operator*() //解引用,返回T&类型
  27. {
  28. return _pnode->val;
  29. }
  30. Cal operator->() //重载->操作符,返回T*
  31. {
  32. return &_pnode->val;
  33. }
  34. bool operator!=(const self& s) const //操作符重载,并且提供const与否的两种类型
  35. {
  36. return _pnode != s._pnode;
  37. }
  38. bool operator==(const self& s) const
  39. {
  40. return _pnode == s._pnode;
  41. }
  42. self& operator++() //重载前置++,返回一个迭代器类型
  43. {
  44. _pnode = _pnode->_next;
  45. return *this;
  46. }
  47. //it++ -> it.operator++(&it,0)
  48. //++it ->it.operator++(&it)
  49. self operator++(int) //重载后置++,返回未++的迭代器,并将迭代器++
  50. {
  51. self tmp(*this);
  52. _pnode = _pnode->_next;
  53. return tmp;
  54. }
  55. self& operator--() //++
  56. {
  57. _pnode = _pnode->_prev;
  58. return *this;
  59. }
  60. self operator--(int)
  61. {
  62. self tmp(*this);
  63. _pnode = _pnode->_prev;
  64. return tmp;
  65. }
  66. };
  67. template<class T>
  68. class list
  69. {
  70. typedef _list_node<T> node;
  71. public:
  72. typedef _list_iterator<T , T&, T*> iterator; //将封装的迭代器类重命名未iterator
  73. typedef _list_iterator<T, const T&,const T*> const_iterator;//同上,只不过定义要求了另外一种const 类型
  74. iterator begin() //返回第一个结点的迭代器
  75. {
  76. return iterator(_head->_next);
  77. }
  78. iterator end() //返回最后一个结点的下一个位置的迭代器(即头节点)
  79. {
  80. return iterator(_head);
  81. }
  82. const_iterator begin() const //第二种类型
  83. {
  84. return const_iterator(_head->_next);
  85. }
  86. const_iterator end() const
  87. {
  88. return const_iterator(_head);
  89. }
  90. list() //构造函数
  91. {
  92. _head = new node;
  93. _head-> _next = _head;
  94. _head-> _prev = _head;
  95. }
  96. ~list() //析构函数
  97. {
  98. clear();
  99. delete _head;
  100. _head = nullptr;
  101. }
  102. list(const list<T>& x) //拷贝构造
  103. {
  104. _head = new node;
  105. _head->_next = _head;
  106. _head->_prev = _head;
  107. for (const auto& e : x)
  108. {
  109. push_back(e);
  110. }
  111. }
  112. //list<int>& operator=(const list<T>& lt)
  113. //{
  114. // if (this != &lt)
  115. // {
  116. // clear();
  117. // for (const auto& e : lt)
  118. // {
  119. // push_back(e);
  120. // }
  121. // }
  122. // return *this;
  123. //}//传统写法
  124. list<T>& operator=(list<T>& lt) //赋值运算符重载
  125. {
  126. ::swap(_head, lt._head);
  127. return *this;
  128. }
  129. void clear()
  130. {
  131. iterator it = begin();
  132. while (it != end())
  133. {
  134. it = erase(it);
  135. }
  136. }
  137. void push_back(const T& x)
  138. {
  139. node* newnode = new node(x);
  140. node* tail = _head->_prev;
  141. tail->_next = newnode;
  142. newnode->_prev = tail;
  143. newnode->_next = _head;
  144. _head->_prev = newnode;
  145. //insert(end(),x); //尾插,一种思路时复用insert()
  146. }
  147. void push_front(const T& x)
  148. {
  149. insert(begin(), x);
  150. }
  151. void pop_back()
  152. {
  153. erase(--end());
  154. }
  155. void pop_front()
  156. {
  157. erase(begin());
  158. }
  159. void insert(iterator pos, const T& x) //在pos前面插入
  160. {
  161. assert(pos._pnode);
  162. node* cur = pos._pnode; //三结点之间的关系
  163. node* prev = cur->_prev;
  164. node* newnode = new node(x);
  165. prev->_next = newnode;
  166. newnode->_prev = prev;
  167. newnode->_next = cur;
  168. cur->_prev = newnode;
  169. }
  170. iterator erase(iterator pos) //删除pos结点
  171. {
  172. assert(pos._pnode);
  173. assert(pos != end());
  174. node* prev = pos._pnode->_prev;
  175. node* next = pos._pnode->_next;
  176. delete pos._pnode;
  177. prev->_next = next;
  178. next->_prev = prev;
  179. return iterator(next);
  180. }
  181. bool empty() //判断是否为空
  182. {
  183. return begin() == end();
  184. }
  185. size_t size() //计算结点数
  186. {
  187. size_t sz = 0;
  188. iterator it = begin();
  189. while (it != end())
  190. {
  191. sz++;
  192. it++;
  193. }
  194. return sz;
  195. }
  196. private:
  197. node* _head; //定义一个哨兵位——头节点
  198. };
  199. }

我们这里的模拟实现,主要是针对迭代器封装的模拟,其他的链表成员我们都简略或者省略了。

我们可以测试看看:

  1. namespace jxwd{
  2. void func()
  3. {
  4. list<int> lt;
  5. lt.push_back(1);
  6. lt.push_back(2);
  7. lt.push_back(3);
  8. lt.push_back(4);
  9. lt.push_back(5);
  10. list<int> llt(lt);
  11. list<int>::iterator it = llt.begin(); //这里是将返回的迭代器 进行拷贝构造
  12. while (it != llt.end())
  13. {
  14. std::cout << *it << " ";
  15. ++it;
  16. }
  17. std::cout << std::endl;
  18. }
  19. void test_list2()
  20. {
  21. list<int> lt;
  22. lt.push_back(10);
  23. lt.push_back(20);
  24. list<int> lt2(lt);
  25. list<int>::iterator it = lt2.begin();
  26. while (it!=lt2.end())
  27. {
  28. std::cout << *it << " ";
  29. it++;
  30. }
  31. }
  32. }

我们将上面的函数放在main函数中测试一下看看,发现程序成功运行了起来。下面是运行截图:

这就说明我们模拟成功了。

对于迭代器的封装模拟使用也是正确的。

好耶!!!

至于vector和list 的对比,实际上就是链表和顺序表的对比,如果想看的话,我们下节再啰嗦一遍吧

好啦,我们本节的内容就先到这里吧,我们下节再见。

下班啦,下班啦~~~~

记得关注  关注  关注我呦!!

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