【探寻C++之旅】第六章：STL

媒介

   本日，我们继承踏入追寻C++的冒险进程。上一章我们简单先容而且相识了C++中的模板，而且在末了提到了C++的标准模板库也叫做STL，那么本章将为各人讲授这一告急的部门：STL。下面让我们一起来进入STL的学习。
  1. STL简介

STL(standard template libaray)叫做标准模板库，是C++标准库的告急构成部门。上一章我们讲授了模板，那么通过这个名字我们可以知道STL内里是一些模板，STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），险些全部的代码都采取了模板类和模板函数的方式，如许当我们在必要用到次序表、链表、堆、栈等数据布局时不必要本身去写，而是直接调用库中的即可。STL不光是一个可复用的组件库，而且是一个包罗数据布局与算法的软件框架。
STL 将“在数据上实行的操纵”与“要实行操纵的数据分开”，分别以如下概念指代：

• 容器：包罗、放置数据的地方。
  
• 迭代器：在容器中指出一个位置、或成对使用以规定一个地区，用来限定操纵所涉及到的数据范围。
  
• 算法：要实行的操纵。
  

STL有六大组件，如下图所示：

下面我们会逐一举行相识。
STL是C++中的良好作品，有了它的伴随，很多底层的数据布局以及算法都不必要本身重新造轮子，站在前人的肩膀上，健步如飞的快速开辟。 本章为各人讲授一下常见的STL容器的使用。
2. auto和范围for

在这里增补2个C++11的小语法，方便我们反面的学习。
2.1 auto关键字

在早期C/C++中auto的寄义是：使用auto修饰的变量，是具有自动存储器的局部变量，厥后这个不告急了。C++11中，标准委员会变废为宝赋予了auto全新的寄义即：auto不再是一个存储范例指示符，而是作为一个新的范例指示符来指示编译器，auto声明的变量必须由编译器在编译时期推导而得。

• 用auto声明指针范例时，用auto和auto*没有任何区别，但用auto声明引用范例时则必须加&。
  
• 当在同一行声明多个变量时，这些变量必须是类似的范例，否则编译器将会报错，由于编译器实际只对第一个范例举行推导，然后用推导出来的范例界说其他变量。
  
• auto不能作为函数的参数，可以做返回值，但是发起审慎使用。
  
• auto不能直接用来声明数组。
  

1. #include <iostream>
2. #include <string>
3. #include <map>
4. using namespace std;
5. int main()
6. {
7.         std::map<std::string, std::string> dict = { { "apple", "苹果" },{ "orange","橙子" }, {"pear","梨"}};
8.         // auto的用武之地
9.         //std::map<std::string, std::string>::iterator it = dict.begin();
10.         auto it = dict.begin();
11.         while (it != dict.end())
12.         {
13.                 cout << it->first << ":" << it->second << endl;
14.                 ++it;
15.         }
16.         return 0;
17. }

复制代码

在上述代码中我们可以看到，it的范例名字很长，在我们写步调会不经意间出现写错等小错误，而且浪费时间，这时，我们就可以使用auto关键字去自动推导范例。
2.2 范围for

对于一个有范围的聚集而言，由步调员来分析循环的范围是多余的，偶然间还会容易犯错误。因此C++11中引入了基于范围的for循环。for循环后的括号由冒号“ ：”分为两部门：第一部门是范围内用于迭代的变量，第二部门则体现被迭代的范围，自动迭代，自动取数据，自动判定竣事。

• 范围for可以作用到数组和容器对象上举行遍历。
  
• 范围for的底层很简单，容器遍历实际就是更换为迭代器，这个从汇编层也可以看到。
  

1. #include<iostream>
2. #include <string>
3. #include <map>
4. using namespace std;
5. int main()
6. {
7.         int array[] = { 1, 2, 3, 4, 5 };
8.         // C++98的遍历
9.         for (int i = 0; i < sizeof(array) / sizeof(array[0]); ++i)
10.         {
11.         array[i] *= 2;
12.         }
13.     for (int i = 0; i < sizeof(array) / sizeof(array[0]); ++i)
14.         {
15.         cout << array[i] << endl;
16.         }
17.     // C++11的遍历
18.         for (auto& e : array)
19.                 e *= 2;
20.    
21.         for (auto e : array)
22.                 cout << e << " " << endl;
23.    
24.         string str("hello world");
25.         for (auto ch : str)
26.         {
27.                 cout << ch << " ";
28.         }
29.     cout << endl;
30.         return 0;
31. }

复制代码

在使用范围for时必要注意，当我们在循环的过程时必要用到下标时，那么就不能使用范围for。由于使用范围for我们在循环中得到的直接是下标对应的值，而没有具体的下标。
3. string类

C语言中，字符串是以’\0’末端的一些字符的聚集，为了操纵方便，C标准库中提供了一些str系列的库函数，但是这些库函数与字符串是分离开的，不太符合OOP的头脑，而且底层空间必要用户本身管理，稍不留心大概还会越界访问。 在OJ中，有关字符串的标题根本以string类的情势出现，而且在通例工作中，为了简单、方便、快捷，根本都使用string类，很少有人去使用C库中的字符串操纵函数。
   使用string类时，必须包罗头文件#include<string>和using namespace std;（不睁开定名空间的话必要在使用时指定类域）。
  string是一个类，并不是我们上面所说的模板，这是由于string类出现的时间要比STL的时间早，因此与我们其他的容器差异，它的界说不必要再传模板参数。

看上图可知，string类是由basic_string<char> typedef出来的（相识即可），下面我们来看看string类的常用接口：
3.1 string类对象的常见构造

(constructor)函数名称功能分析string() （重点）构造空的string类对象，即空字符串string(const char* s) （重点）用C-string来构造string类对象string(size_t n, char c)string类对象中包罗n个字符cstring(const string&s) （重点）拷贝构造函数

1. void Teststring()
2. {
3.         string s1; // 构造空的string类对象s1
4.         string s2("hello world"); // 用C格式字符串构造string类对象s2
5.         string s3(s2); // 拷贝构造s3
6. }

复制代码

3.2 string类对象的容量操纵

函数名称功能分析size（重点）返回字符串有效字符长度length返回字符串有效字符长度capacity返回空间总巨细empty （重点）检测字符串开释为空串，是返回true，否则返回falseclear （重点）清空有效字符reserve （重点）为字符串预留空间**resize （重点）将有效字符的个数该成n个，多出的空间用字符c添补

1. // 测试string容量相关的接口
2. // size/clear/resize
3. void Test()
4. {
5.         // 注意：string类对象支持直接用cin和cout进行输入和输出
6.         string s("hello, wrold!!!");
7.         cout << s.size() << endl;
8.         cout << s.length() << endl;
9.         cout << s.capacity() << endl;
10.         cout << s << endl;
12.         // 将s中有效字符个数增加到10个，多出位置用'a'进行填充
13.         // “aaaaaaaaaa”
14.         s.resize(10, 'a');
15.         cout << s.size() << endl;
16.         cout << s.capacity() << endl;
18.         // 将s中有效字符个数增加到15个，多出位置用缺省值'\0'进行填充
19.         // "aaaaaaaaaa\0\0\0\0\0"
20.         // 注意此时s中有效字符个数已经增加到15个
21.         s.resize(15);
22.         cout << s.size() << endl;
23.         cout << s.capacity() << endl;
24.         cout << s << endl;
26.         // 将s中有效字符个数缩小到5个
27.         s.resize(5);
28.         cout << s.size() << endl;
29.         cout << s.capacity() << endl;
30.         cout << s << endl;
31.    
32.         // 将s中的字符串清空，注意清空时只是将size清0，不改变底层空间的大小
33.         s.clear();
34.         cout << s.size() << endl;
35.         cout << s.capacity() << endl;
36.    
37.         // 测试reserve是否会改变string中有效元素个数
38.         s.reserve(100);
39.         cout << s.size() << endl;
40.         cout << s.capacity() << endl;
42.         // 测试reserve参数小于string的底层空间大小时，是否会将空间缩小
43.         s.reserve(50);
44.         cout << s.size() << endl;
45.         cout << s.capacity() << endl;
46. }

复制代码

注意：

• size()与length()方法底层实现原理完全类似，引入size()的缘故起因是为了与其他容器的接口保持划一，一样平常情况下根本都是用size()。
  
• clear()只是将string中有效字符清空，不改变底层空间巨细。
  
• resize(size_t n) 与 resize(size_t n, char c)都是将字符串中有效字符个数改变到n个，差异的是当字符个数增多时：resize(n)用0来添补多出的元素空间，resize(size_t n, char c)用字符c来添补多出的元素空间。注意：resize在改变元素个数时，假如是将元素个数增多，大概会改变底层容量的巨细，假如是将元素个数淘汰，底层空间总巨细稳定。
  
• reserve(size_t res_arg=0)：为string预留空间，不改变有效元素个数，当reserve的参数小于string的底层空间总巨细时，reserver不会改变容量巨细。
  

3.3 string类对象的访问及遍历操纵

函数名称功能分析operator[] （重点）返回pos位置的字符，const string类对象调用begin+ endbegin获取第一个字符的迭代器 + end获取末了一个字符下一个位置的迭代器rbegin + rend（反向迭代器）rbegin获取末了一个字符的迭代器 + rend获取第一个字符位置之前的迭代器范围forC++11支持更简便的范围for的新遍历方式

对于string类的遍历：

1. // string的遍历
2. // begin()+end()   for+[]  范围for
3. // 注意：string遍历时使用最多的还是for+下标 或者 范围for(C++11后才支持)
4. // begin()+end()大多数使用在需要使用STL提供的算法操作string时，比如：采用reverse逆置string
5. void Test()
6. {
7.         string s("hello World");
8.         // 3种遍历方式：
9.         // 需要注意的以下三种方式除了遍历string对象，还可以遍历是修改string中的字符，
10.         // 另外以下三种方式对于string而言，第一种使用最多
11.         // 1. for+operator[]
12.         for (size_t i = 0; i < s.size(); ++i)
13.                 cout << s[i] << endl;
15.         // 2.迭代器
16.         string::iterator it = s.begin();
17.         while (it != s.end())
18.         {
19.                 cout << *it << endl;
20.                 ++it;
21.         }
23.         // string::reverse_iterator rit = s.rbegin();
24.         // C++11之后，直接使用auto定义迭代器，让编译器推到迭代器的类型
25.         auto rit = s.rbegin();
26.         while (rit != s.rend())
27.                 cout << *rit << endl;
29.         // 3.范围for
30.         for (auto ch : s)
31.                 cout << ch << endl;
32. }

复制代码

3.4 string类对象的修改操纵

函数名称功能分析push_back在字符串后尾插字符cappend在字符串后追加一个字符串operator+= (重点)在字符串后追加字符串strc_str(重点)返回C格式字符串find (重点)从字符串pos位置开始以后找字符c，返回该字符在字符串中的位置rfind从字符串pos位置开始往前找字符c，返回该字符在字符串中的位置substr在str中从pos位置开始，截取n个字符，然后将其返回npos(静态成员常量值)当此值用作字符串成员函数中 len （或 sublen） 参数的值时，体现*“直到字符串的末了”。*

1. // 测试string：
2. // 1. 插入(拼接)方式：push_back  append  operator+=
3. // 2. 正向和反向查找：find() + rfind()
4. // 3. 截取子串：substr()
5. // 4. 删除：erase
6. void Test()
7. {
8.         string str;
9.         str.push_back(' ');   // 在str后插入空格
10.         str.append("hello");  // 在str后追加一个字符"hello"
11.         str += 'w';           // 在str后追加一个字符'w'   
12.         str += "orld";          // 在str后追加一个字符串"orld"
13.         cout << str << endl;
14.         cout << str.c_str() << endl;   // 以C语言的方式打印字符串
16.         // 获取file的后缀
17.         string file("string.cpp");
18.         size_t pos = file.rfind('.');
19.         string suffix(file.substr(pos, file.size() - pos));
20.         cout << suffix << endl;
22.         // npos是string里面的一个静态成员变量
23.         // static const size_t npos = -1;
25.         // 取出url中的域名
26.         string url("http://www.cplusplus.com/reference/string/string/find/");
27.         cout << url << endl;
28.         size_t start = url.find("://");
29.         if (start == string::npos)
30.         {
31.                 cout << "invalid url" << endl;
32.                 return;
33.         }
34.         start += 3;
35.         size_t finish = url.find('/', start);
36.         string address = url.substr(start, finish - start);
37.         cout << address << endl;
39.         // 删除url的协议前缀
40.         pos = url.find("://");
41.         url.erase(0, pos + 3);
42.         cout << url << endl;
43. }

复制代码

注意：

• 在string尾部追加字符时，s.push_back(c) / s.append(1, c) / s += 'c'三种的实现方式差不多，一样平常情况下string类的+=操纵用的比力多，+=操纵不光可以毗连单个字符，还可以毗连字符串。
  
• 对string操纵时，假如可以或许大概预估到放多少字符，可以先通过reserve把空间预留好
  

3.4 string类非成员函数

函数功能分析operator+只管少用，由于传值返回，导致深拷贝服从低getline （重点）获取一行字符串

1. #include <iostream>
2. #include <string>
3. //getline的使用
4. int main ()
5. {
6.   std::string name;
8.   std::cout << "Please, enter your full name: ";
9.   std::getline (std::cin, name);
10.   std::cout << "Hello, " << name << "!\n";
12.   return 0;
13. }

复制代码

3.6 vs下string的布局

下述布局是在32位平台下举行验证，32位平台下指针占4个字节。
string统共占28个字节，内部布局轻微复杂一点，先是有一个团结体，团结体用来界说string中字符串的存储空间：

• 当字符串长度小于16时，使用内部固定的字符数组来存放。
  
• 当字符串长度大于便是16时，从堆上开辟空间。
  

1. union _Bxty
2. {         // storage for small buffer or pointer to larger one
3.         value_type _Buf[_BUF_SIZE];
4.         pointer _Ptr;
5.         char _Alias[_BUF_SIZE]; // to permit aliasing
6. } _Bx;

复制代码

这种筹划也是有肯定原理的，大多数情况下字符串的长度都小于16，那string对象创建好之后，内部已经有了16个字符数组的固定空间，不必要通过堆创建，服从高。其次：尚有一个size_t字段生存字符串长度，一个size_t字段生存从堆上开辟空间总的容量末了：尚有一个指针做一些其他事变。故统共占16+4+4+4=28个字节。
4. vector

vector是序列容器，体现巨细可以厘革的数组。就像数组一样，vector对其元素使用一连的存储位置，这意味着也可以使用指向其元素的通例指针上的偏移量来访问它们的元素，而且与在数组中一样高效。但与数组差异的是，它们的巨细可以动态厘革，其存储由容器自动处置惩罚。
4.1 vector的构造

(constructor)构造函数声明接口分析vector()（重点）无参构造vector（size_type n, const value_type& val = value_type()）构造并初始化n个valvector (const vector& x); （重点）拷贝构造vector (InputIterator first, InputIterator last);使用迭代器举行初始化构造

1. //vector的构造
2. void Test()
3. {
4.     // constructors used in the same order as described above:
5.     vector<int> first;                                // empty vector of ints
6.     vector<int> second(4, 100);                       // four ints with value 100
7.     vector<int> third(second.begin(), second.end());  // iterating through second
8.     vector<int> fourth(third);                        // a copy of third
9.    
10.     cout << "first:";
11.         for (int x : first)
12.             cout << x << ' ';
13.         cout << endl;
15.         cout << "second:";
16.         for (int x : second)
17.             cout << x << ' ';
18.         cout << endl;
20.         cout << "third:";
21.         for (int x : third)
22.             cout << x << ' ';
23.         cout << endl;
25.         cout << "fourth:";
26.         for (int x : fourth)
27.             cout << x << ' ';
28.         cout << endl;
29. }

复制代码

4.2 vector iterator (迭代器)的使用

iterator的使用接口分析begin + end（重点）获取第一个数据位置的iterator/const_iterator， 获取末了一个数据的下一个位置的iterator/const_iteratorrbegin + rend获取末了一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

1. void Test()
2. {
3.         vector<int> v(4, 1);
5.         // 使用迭代器进行遍历打印
6.         vector<int>::iterator it = v.begin();
7.         while (it != v.end())
8.         {
9.                 cout << *it << " ";
10.                 ++it;
11.         }
12.         cout << endl;
14.         // 使用迭代器进行修改
15.         it = v.begin();
16.         while (it != v.end())
17.         {
18.                 *it *= 2;
19.                 ++it;
20.         }
22.         // 使用反向迭代器进行遍历再打印
23.         // vector<int>::reverse_iterator rit = v.rbegin();
24.         auto rit = v.rbegin();
25.         while (rit != v.rend())
26.         {
27.                 cout << *rit << " ";
28.                 ++rit;
29.         }
30.         cout << endl;
31. }

复制代码

vector的遍历使用operator[]+下标和范围for+auto两种方式是比力方便的。

1. void Test()
2. {
3.         vector<int> v{ 1, 2, 3, 4 };
5.         // 通过[]读写第0个位置。
6.         v[0] = 10;
7.         cout << v[0] << endl;
9.         // 1. 使用for+[]小标方式遍历
10.         for (size_t i = 0; i < v.size(); ++i)
11.                 cout << v[i] << " ";
12.         cout << endl;
14.         vector<int> swapv;
15.         swapv.swap(v);
17.         cout << "v data:";
18.         for (size_t i = 0; i < v.size(); ++i)
19.                 cout << v[i] << " ";
20.         cout << endl;
22.         // 2. 使用迭代器遍历
23.         cout << "swapv data:";
24.         auto it = swapv.begin();
25.         while (it != swapv.end())
26.         {
27.                 cout << *it << " ";
28.                 ++it;
29.         }
31.         // 3. 使用范围for遍历
32.         for (auto x : v)
33.                 cout << x << " ";
34.         cout << endl;
35. }

复制代码

4.3 vector的空间使用

容量空间接口分析size获取数据个数capacity获取容量巨细empty判定是否为空resize（重点）改变vector的sizereserve （重点）改变vector的capacity

1. // reisze(size_t n, const T& data = T())
2. // 将有效元素个数设置为n个，如果时增多时，增多的元素使用data进行填充
3. // 注意：resize在增多元素个数时可能会扩容
4. void TestVector3()
5. {
6.         vector<int> v;
8.         // set some initial content:
9.         for (int i = 1; i < 10; i++)
10.                 v.push_back(i);
12.         v.resize(5);
13.         v.resize(8, 100);
14.         v.resize(12);
16.         cout << "v contains:";
17.         for (size_t i = 0; i < v.size(); i++)
18.                 cout << ' ' << v[i];
19.         cout << '\n';
20.        
21.         // 往vecotr中插入元素时，如果大概已经知道要存放多少个元素
22.         // 可以通过reserve方法提前将容量设置好，避免边插入边扩容效率低
23.         vector<int> v;
24.         size_t sz = v.capacity();
25.         v.reserve(100);   // 提前将容量设置好，可以避免一遍插入一遍扩容
26. }

复制代码

注意：

• capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个标题经常会观察，不要固化的以为，vector增容都是2倍，具体增长多少是根据具体的需求界说的。vs是PJ版本STL，g++是SGI版本STL。
  
• reserve只负责开辟空间，假如确定知道必要用多少空间，reserve可以缓解vector增容的代价缺陷标题。
  
• resize在开空间的同时还会举行初始化，影响size。
  

4.4 vector的增删查改

vector增删查改接口分析push_back（重点）尾插pop_back （重点）尾删find查找。（注意这个是算法模块实现，不是vector的成员接口）insert在position之前插入valerase删除position位置的数据swap互换两个vector的数据空间operator[] （重点）像数组一样访问

1. //  vector的增删改查
2. // 尾插和尾删：push_back/pop_back
3. void Test1()
4. {
5.         vector<int> v;
6.         v.push_back(1);
7.         v.push_back(2);
8.         v.push_back(3);
9.         v.push_back(4);
11.         auto it = v.begin();
12.         while (it != v.end())
13.         {
14.                 cout << *it << " ";
15.                 ++it;
16.         }
17.         cout << endl;
19.         v.pop_back();
20.         v.pop_back();
22.         it = v.begin();
23.         while (it != v.end())
24.         {
25.                 cout << *it << " ";
26.                 ++it;
27.         }
28.         cout << endl;
29. }
31. // 任意位置插入：insert和erase，以及查找find
32. // 注意find不是vector自身提供的方法，是STL提供的算法
33. void Test2()
34. {
35.         // 使用列表方式初始化，C++11新语法
36.         vector<int> v{ 1, 2, 3, 4 };
38.         // 在指定位置前插入值为val的元素，比如：3之前插入30,如果没有则不插入
39.         // 1. 先使用find查找3所在位置
40.         // 注意：vector没有提供find方法，如果要查找只能使用STL提供的全局find
41.         auto pos = find(v.begin(), v.end(), 3);
42.         if (pos != v.end())
43.         {
44.                 // 2. 在pos位置之前插入30
45.                 v.insert(pos, 30);
46.         }
48.         vector<int>::iterator it = v.begin();
49.         while (it != v.end())
50.         {
51.                 cout << *it << " ";
52.                 ++it;
53.         }
54.         cout << endl;
56.         pos = find(v.begin(), v.end(), 3);
57.         // 删除pos位置的数据
58.         v.erase(pos);
60.         it = v.begin();
61.         while (it != v.end()) {
62.                 cout << *it << " ";
63.                 ++it;
64.         }
65.         cout << endl;
66. }

复制代码

4.6 vector迭代器失效标题

迭代器的告急作用就是让算法可以或许不消关心底层数据布局，其底层实际就是一个指针，大概是对指针举行了封装，好比：vector的迭代器就是原生态指针T 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被烧毁了，而使用一块已经被开释的空间，造成的效果是步调瓦解(即假如继承使用已经失效的迭代器，步调大概会瓦解)。*
对于vector大概会导致其迭代器失效的操纵有：

• 会引起其底层空间改变的操纵，都有大概是迭代器失效，好比：resize、reserve、insert、assign、push_back等。
  
  1. #include <iostream>
  2. using namespace std;
  3. #include <vector>
  4. int main()
  5. {
  6.         vector<int> v{1,2,3,4,5,6};
  7.         auto it = v.begin();
  8.    
  9.         // 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容
  10.         // v.resize(100, 8);
  11.    
  12.         // reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变
  13.         // v.reserve(100);
  14.    
  15.         // 插入元素期间，可能会引起扩容，而导致原空间被释放
  16.         // v.insert(v.begin(), 0);
  17.         // v.push_back(8);
  18.    
  19.         // 给vector重新赋值，可能会引起底层容量改变
  20.         v.assign(100, 8);
  21.    
  22.         /*
  23.         出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释
  24.         放掉，而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块
  25.         已经被释放的空间，而引起代码运行时崩溃。
  26.         解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给
  27.         it重新赋值即可。
  28.         */
  29.         while(it != v.end())
  30.         {
  31.                 cout<< *it << " " ;
  32.                 ++it;
  33.         }
  34.     cout<<endl;
  35.         return 0;
  36. }

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

  复制代码
  erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：假如pos刚好是末了一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中恣意位置上元素时，vs就以为该位置迭代器失效了。
  
• 与vector类似，string在insert + 扩容操纵 + erase之后，迭代器也会失效
  
  1. #include <string>
  2. using namespace std;
  3. void Test()
  4. {
  5.         string s("hello");
  6.         auto it = s.begin();
  7.    
  8.         // 放开之后代码会崩溃，因为resize到20会string会进行扩容
  9.         // 扩容之后，it指向之前旧空间已经被释放了，该迭代器就失效了
  10.         // 后序打印时，再访问it指向的空间程序就会崩溃
  11.         //s.resize(20, '!');
  12.         while (it != s.end())
  13.         {
  14.                 cout << *it;
  15.                 ++it;
  16.         }
  17.     cout << endl;
  18.    
  19.         it = s.begin();
  20.         while (it != s.end())
  21.         {
  22.                 it = s.erase(it);
  23.                 // 按照下面方式写，运行时程序会崩溃，因为erase(it)之后
  24.                 // it位置的迭代器就失效了
  25.                 // s.erase(it);
  26.                 ++it;
  27.         }
  28. }

  复制代码

   迭代器失效办理办法：在使用前，对迭代器重新赋值即可。
  5. list

list是序列容器，答应对序列中恣意位置的恒定时间插入和删除操纵，以及双向迭代。list容器实现为双向循环链表（对于双向循环链表详情可看）;双向循环链表可以将它们包罗的每个元素存储在差异且不干系的存储位置。排序在内部通过与指向其前面的元素的链接和指向厥后元素的链接的每个元素的关联来保持。
它们与 forward_list 非常相似：告急区别在于 forward_list 对象是单链表，因此它们只能向后迭代，这里涉及到了迭代器的分类，对于差异的容器范例，迭代器也分为几类，此中最为常见的有三类：分别是单向迭代器、双向迭代器、随机迭代器：

• 单向迭代器（Forward iterators）：只能向后走，也就是只能举行++操纵，比方forward_list、unordered_xxx。
  
• 双向迭代器（Bidirectional iterator）：可以向后也可以向前走，也就是可以举行++和–操纵，比方list。
  
• 随机迭代器（RandomAccessIterator）：即可以高出的向前和向后走，也就是可以举行+和-操纵，比方string、vector。
  

5.1 sort函数

在c++的算法库中有一个排序函数，也就是sort，它可以对迭代器范例为随机迭代器的容器的数据举行排序：

使用它时必要包罗头文件<algorithm>，库中的sort函数的底层使用的是快速排序（详情可看），我们知道在使用快排时我们必要可以或许随机访问到数组中的任何一个元素。因此在库函数sort中我们必要传入随机迭代器才气完成我们的排序。那么对于我们的list的排序该怎么呢？从上面我们知道list的迭代器是双向迭代器，不符合要求。着实，为相识决这个标题，list中有本身的成员函数sort：

当我们必要对list举行排序时，直接调用即可。在这两个sort函数中我们可以看到都有一个模板参数Compare，这也就是我们所说的仿函数，它的实际范例为一个类，内里重载了（）运算符，如许在使用时与函数的使用看起来是一样的（告急目标是代码实现方便）。该参数的作用也很简单，是用来控制我们排序是升序照旧降序，默以为升序。下面拿list中的sort函数举个例子：

1. // list::sort
2. #include <iostream>
3. #include <list>
4. #include <string>
5. #include <cctype>
7. // comparison, not case sensitive.
8. bool compare_nocase (const std::string& first, const std::string& second)
9. {
10.           unsigned int i=0;
11.           while ( (i<first.length()) && (i<second.length()) )
12.           {
13.             if (tolower(first[i])<tolower(second[i])) return true;
14.             else if (tolower(first[i])>tolower(second[i])) return false;
15.             ++i;
16.           }
17.           return ( first.length() < second.length() );
18. }
20. int main ()
21. {
22.           //list中每个节点存储的值为字符串
23.           std::list<std::string> mylist;
24.           std::list<std::string>::iterator it;
25.           mylist.push_back ("one");
26.           mylist.push_back ("two");
27.           mylist.push_back ("Three");
29.           mylist.sort();
31.           std::cout << "mylist contains:";
32.           for (it=mylist.begin(); it!=mylist.end(); ++it)
33.             std::cout << ' ' << *it;
34.           std::cout << '\n';
36.           //传入compare_nocase类,使排序按照降序
37.           mylist.sort(compare_nocase);
39.           std::cout << "mylist contains:";
40.           for (it=mylist.begin(); it!=mylist.end(); ++it)
41.             std::cout << ' ' << *it;
42.           std::cout << '\n';
44.           return 0;
45. }

复制代码

5.2 list的构造

构造函数（ (constructor)）接口分析list (size_type n, const value_type& val = value_type())构造的list中包罗n个值为val的元素list()构造空的listlist (const list& x)拷贝构造函数list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造list

1. // list的构造
2. void TestList1()
3. {
4.     list<int> l1;                         // 构造空的l1
5.     list<int> l2(4, 100);                 // l2中放4个值为100的元素
6.     list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左闭右开的区间构造l3
7.     list<int> l4(l3);                    // 用l3拷贝构造l4
9.     // 以数组为迭代器区间构造l5
10.     int array[] = { 16,2,77,29 };
11.     list<int> l5(array, array + sizeof(array) / sizeof(int));
13.     // 列表格式初始化C++11
14.     list<int> l6{ 1,2,3,4,5 };
16.     // 用迭代器方式打印l5中的元素
17.     list<int>::iterator it = l5.begin();
18.     while (it != l5.end())
19.     {
20.         cout << *it << " ";
21.         ++it;
22.     }      
23.     cout << endl;
25.     // C++11范围for的方式遍历
26.     for (auto& e : l5)
27.         cout << e << " ";
29.     cout << endl;
30. }

复制代码

5.3 list iterator的使用

函数声明接口分析begin + end返回第一个元素的迭代器+返回末了一个元素下一个位置的迭代器rbegin + rend返回第一个元素的reverse_iterator,即end位置，返回末了一个元素下一个位置的reverse_iterator,即begin位置

1. // list迭代器的使用
2. // 注意：遍历链表只能用迭代器和范围for，因为不支持下标访问
3. void PrintList(const list<int>& l)
4. {
5.     // 注意这里调用的是list的 begin() const，返回list的const_iterator对象
6.     for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
7.     {
8.         cout << *it << " ";
9.         // *it = 10; 编译不通过，因为是const对象
10.     }
12.     cout << endl;
13. }
15. void TestList2()
16. {
17.     int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
18.     list<int> l(array, array + sizeof(array) / sizeof(array[0]));
19.     // 使用正向迭代器正向list中的元素
20.     // list<int>::iterator it = l.begin();   // C++98中语法
21.     auto it = l.begin();                     // C++11之后推荐写法
22.     while (it != l.end())
23.     {
24.         cout << *it << " ";
25.         ++it;
26.     }
27.     cout << endl;
29.     // 使用反向迭代器逆向打印list中的元素
30.     // list<int>::reverse_iterator rit = l.rbegin();
31.     auto rit = l.rbegin();
32.     while (rit != l.rend())
33.     {
34.         cout << *rit << " ";
35.         ++rit;
36.     }
37.     cout << endl;
38. }

复制代码

注意：

• begin与end为正向迭代器，对迭代器实行++操纵，迭代器向后移动
  
• rbegin(end)与rend(begin)为反向迭代器，对迭代器实行++操纵，迭代器向前移动
  

5.4 list的常用类成员函数

函数声明接口分析empty检测list是否为空，是返回true，否则返回falsesize返回list中有效节点的个数front返回list的第一个节点中值的引用back返回list的末了一个节点中值的引用push_front在list首元素前插入值为val的元素pop_front删除list中第一个元素push_back在list尾部插入值为val的元素pop_back删除list中末了一个元素insert在list position 位置中插入值为val的元素erase删除list position位置的元素swap互换两个list中的元素clear清空list中的有效元素

1. // list插入和删除
2. // push_back/pop_back/push_front/pop_front
3. void TestList1()
4. {
5.     int array[] = { 1, 2, 3 };
6.     list<int> L(array, array + sizeof(array) / sizeof(array[0]));
8.     // 在list的尾部插入4，头部插入0
9.     L.push_back(4);
10.     L.push_front(0);
11.     PrintList(L);
13.     // 删除list尾部节点和头部节点
14.     L.pop_back();
15.     L.pop_front();
16.     PrintList(L);
17. }
19. // insert /erase
20. void TestList2()
21. {
22.     int array1[] = { 1, 2, 3 };
23.     list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));
25.     // 获取链表中第二个节点
26.     auto pos = ++L.begin();
27.     cout << *pos << endl;
29.     // 在pos前插入值为4的元素
30.     L.insert(pos, 4);
31.     PrintList(L);
33.     // 在pos前插入5个值为5的元素
34.     L.insert(pos, 5, 5);
35.     PrintList(L);
37.     // 在pos前插入[v.begin(), v.end)区间中的元素
38.     vector<int> v{ 7, 8, 9 };
39.     L.insert(pos, v.begin(), v.end());
40.     PrintList(L);
42.     // 删除pos位置上的元素
43.     L.erase(pos);
44.     PrintList(L);
46.     // 删除list中[begin, end)区间中的元素，即删除list中的所有元素
47.     L.erase(L.begin(), L.end());
48.     PrintList(L);
49. }
51. // resize/swap/clear
52. void TestList3()
53. {
54.     // 用数组来构造list
55.     int array1[] = { 1, 2, 3 };
56.     list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
57.     PrintList(l1);
59.     // 交换l1和l2中的元素
60.     list<int> l2;
61.     l1.swap(l2);
62.     PrintList(l1);
63.     PrintList(l2);
65.     // 将l2中的元素清空
66.     l2.clear();
67.     cout << l2.size() << endl;
68. }

复制代码

5.5 list的迭代器失效

前面说过，此处各人可将迭代器临时明白成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。由于list的底层布局为带头结点的双向循环链表，因此在list中举行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，而且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

1. void TestListIterator1()
2. {
3.         int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
4.         list<int> l(array, array+sizeof(array)/sizeof(array[0]));
5.         auto it = l.begin();
6.         while (it != l.end())
7.         {
8.                 // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
9.                 l.erase(it);
10.                 ++it;
11.         }
12. }
13. // 改正
14. void TestListIterator()
15. {
16.     int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
17.         list<int> l(array, array+sizeof(array)/sizeof(array[0]));
18.         auto it = l.begin();
19.         while (it != l.end())
20.         {
21.                 it = l.erase(it++);
22.         }
23. }

复制代码

5.6 list与vector的比力

vector与list都是STL中非常告急的序列式容器，由于两个容器的底层布局差异，导致其特性以及应用场景差异，其告急差异如下：
vectorlist底 层 结 构动态次序表，一段一连空间带头结点的双向循环链表随 机 访 问支持随机访问，访问某个元素服从O(1)不支持随机访问，访问某个元素服从O(N)插 入 和 删 除恣意位置插入和删除服从低，必要搬移元素，时间复杂度为O(N)，插入时有大概必要增容，增容：开辟新空间，拷贝元素，开释旧空间，导致服从更低恣意位置插入和删除服从高，不必要搬移元素，时间复杂度为O(1)空间使用率底层为一连空间，不容易造成内存碎片，空间使用率高，缓存使用率高底层节点动态开辟，末节点容易造成内存碎片，空间使用率低，缓存使用率低迭代器原生态指针对原生态指针（节点指针）举行封装迭 代 器 失 效在插入元素时，要给全部的迭代器重新赋值，由于插入元素有大概会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器必要重新赋值否则会失效插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响使 用 场 景必要高效存储，支持随机访问，不关心插入删除服从大量插入和删除操纵，不关心随机访问6.stack和queue

stack和queue也就是数据布局中的栈和队列，与vector、list等差异，它们在STL中它们并不是以容器的情势存在的，而是容器适配器，简单来说就是通过对其他容器的接口举行包装后形成的。
6.1 容器适配器

我们先相识一下容器适配器到底是什么。
   适配器是一种筹划模式(筹划模式是一套被反复使用的、多数人知晓的、颠末分类编目标、代码筹划履历的总结)，该种模式是将一个类的接口转换成客户渴望的别的一个接口。
  像我们的条记本电脑都会有本身的电源适配器，它的作用就是将差异的电压和电流转换为支持我们条记本最得当的电压电流。容器适配器也是云云，通过已有的常用容器来将它们的接口举行封装从而得到特定的我们想要的接口。

可以看到，stack和queue的模板参数中第二个就是容器，代表我们要用什么容器去实现，缺省值为deque(双端队列)。固然stack和queue中也可以存放元素，但在STL中并没有将其分别在容器的行列，而是将其称为容器适配器，这是由于stack和队列只是对其他容器的接口举行了包装，STL中stack和queue默认使用deque。固然我们也可以通过具体要求去选择更加符合的底层数据布局。下面我们简单相识一下deque。
6.2 deque

deque可以看作是vector与list的团结产物。
   deque(双端队列)：是一种双开口的"一连"空间的数据布局，双开口的寄义是：可以在头尾两头举行插入和删除操纵，且时间复杂度为O(1)，与vector比力，头插服从高，不必要搬移元素；与list比力，空间使用率比力高。

  deque并不是真正一连的空间，而是由一段段一连的小空间拼接而成的，实际deque类似于一个动态的二维数组，每一个位置存放的是指向一块地点的指针，当这块空间存满后再开辟一块空间，然后把指向这块空间的指针放入deque中，当deque满后，再对其举行扩容。
双端队列底层是一段假象的一连空间，实际是分段一连的，为了维护其“团体一连”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器筹划就比力复杂，这里不再赘述。
缺陷

• 与vector比力，deque的上风是：头部插入和删除时，不必要搬移元素，服从特殊高，而且在扩容时，也不必要搬移大量的元素，因此其服从是必vector高的。
  
• 与list比力，其底层是一连空间，空间使用率比力高，不必要存储额外字段。
  

但是，deque有一个致命缺陷：不得当遍历，由于在遍历时，deque的迭代器要频仍的去检测其是否移动到某段小空间的边界，导致服从低下，而序列式场景中，大概必要经常遍历，因此在实际中，必要线性布局时，大多数情况下优先思量vector和list，deque的应用并不多，而现在能看到的一个应用就是，STL用其作为stack和queue的底层数据布局。
为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据布局，因此只要具有push_back()和pop_back()操纵的线性布局，都可以作为stack的底层容器，好比vector和list都可以；queue是先辈先出的特殊线性数据布局，只要具有push_back和pop_front操纵的线性布局，都可以作为queue的底层容器，好比list。但是STL中对stack和queue默认选择deque作为其底层容器，告急是由于：

• stack和queue不必要遍历(因此stack和queue没有迭代器)，只必要在固定的一端大概两头举行操纵。
  
• 在stack中元素增长时，deque比vector的服从高(扩容时不必要搬移大量数据)；queue中的元素增长时，deque不光服从高，而且内存使用率高。
  

使用deque作为底层数据布局团结了deque的优点，而完善的避开了其缺陷。
6.3 stack的使用

• stack是一种容器适配器，专门用于在FILO上下文(先辈后出)中操纵，此中从容器一端（称为栈顶）插入元素且提取元素。
  
• stack作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，stack提供一组特定的成员函数来访问其元素。元素从栈顶入栈，从栈顶出栈。
  
• 底层容器可以是标准容器类模板之一，也可以是其他专门筹划的容器类。该底层容器应至少支持以下操纵:
  

函数分析接口分析stack()构造空的栈empty()检测stack是否为空size()返回stack中元素的个数top()返回栈顶元素的引用push()将元素val压入stack中pop()将stack中尾部的元素弹出

• 标准容器类deque和vector满意了这些要求。默认情况下，假如没有为queue实例化指定容器类，则使用标准容器deque。
  

栈的使用较为简单，这里通过一道 标题来看一下stack的使用：

1. class Solution
2. {
3. public:
4.         bool IsPopOrder(vector<int> pushV,vector<int> popV)
5.     {
6.                 //入栈和出栈的元素个数必须相同
7.                 if(pushV.size() != popV.size())
8.                         return false;
9.         
10.                 // 用s来模拟入栈与出栈的过程
11.                 int outIdx = 0;
12.                 int inIdx = 0;
13.                 stack<int> s;
14.                 while(outIdx < popV.size())
15.                 {
16.                         // 如果s是空，或者栈顶元素与出栈的元素不相等，就入栈
17.                         while(s.empty() || s.top() != popV[outIdx])
18.                         {
19.                                 if(inIdx < pushV.size())
20.                                         s.push(pushV[inIdx++]);
21.                                 else
22.                                         return false;
23.                         }
24.             
25.                 // 栈顶元素与出栈的元素相等，出栈
26.                         s.pop();
27.                         outIdx++;
28.                 }
29.         return true;
30.         }
31. };

复制代码

6.4 queue

• 队列是一种容器适配器，专门用于在FIFO上下文(先辈先出)中操纵，此中从容器一端插入元素，另一端提取元素。
  
• 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
  
• 底层容器可以是标准容器类模板之一，也可以是其他专门筹划的容器类。该底层容器应至少支持以下操纵:
  

函数声明接口分析queue()构造空的队列empty()检测队列是否为空，是返回true，否则返回falsesize()返回队列中有效元素的个数front()返回队头元素的引用back()返回队尾元素的引用push()在队尾将元素val入队列pop()将队头元素出队列

• 标准容器类deque和list满意了这些要求。默认情况下，假如没有为queue实例化指定容器类，则使用标准容器deque。
  

队列的使用与stack一样较为简单。不再赘述。
7. priority_queue

priority_queue（优先级队列）也是一种容器适配器。priority_queue默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的布局，因此priority_queue就是堆，全部必要用到堆的位置，都可以思量使用priority_queue。注意：默认情况下priority_queue是大堆（父节点的值大于子节点，详情点击）。 如果想得到一个小堆就必要传入相应的参数。
7.1 priority_queue的类成员函数

函数声明接口分析priority_queue()/priority_queue(first, last)构造一个空的优先级队列empty( )检测优先级队列是否为空，是返回true，否则返回falsetop( )返回优先级队列中最大(最小元素)，即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大(最小)元素，即堆顶元素

注意：

• 默认情况下，priority_queue是大堆。
  
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <functional> // greater算法的头文件
  5. using namespace std;
  7. int main()
  8. {
  9.         // 默认情况下，创建的是大堆，其底层按照小于号比较
  10.         vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };
  11.         priority_queue<int> q1;
  12.         for (auto& e : v)
  13.                 q1.push(e);
  14.         cout << q1.top() << endl;
  16.         // 如果要创建小堆，将第三个模板参数换成greater比较方式
  17.         priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
  18.         cout << q2.top() << endl;
  19. }

  复制代码
  
  
  
• 假如在priority_queue中放自界说范例的数据，用户必要在自界说范例中提供> 大概< 的重载。
  
  1. class Date
  2. {
  3. public:
  4.         Date(int year = 1900, int month = 1, int day = 1)
  5.                 : _year(year)
  6.                 , _month(month)
  7.                 , _day(day)
  8.         {}
  9.         bool operator<(const Date& d)const
  10.         {
  11.                 return (_year < d._year) ||
  12.                         (_year == d._year && _month < d._month) ||
  13.                         (_year == d._year && _month == d._month && _day < d._day);
  14.         }
  15.     bool operator>(const Date& d)const
  16.         {
  17.         return (_year > d._year) ||
  18.                 (_year == d._year && _month > d._month) ||
  19.                 (_year == d._year && _month == d._month && _day > d._day);
  20.         }
  21.     friend ostream& operator<<(ostream& _cout, const Date& d)
  22.         {
  23.                 _cout << d._year << "-" << d._month << "-" << d._day;
  24.                 return _cout;
  25.         }
  26. private:
  27.         int _year;
  28.         int _month;
  29.         int _day;
  30. };
  31. int main()
  32. {
  33.         // 大堆，需要用户在自定义类型中提供<的重载
  34.         priority_queue<Date> q1;
  35.         q1.push(Date(2018, 10, 29));
  36.         q1.push(Date(2018, 10, 28));
  37.         q1.push(Date(2018, 10, 30));
  38.         cout << q1.top() << endl;
  39.    
  40.         // 如果要创建小堆，需要用户提供>的重载
  41.         priority_queue<Date, vector<Date>, greater<Date>> q2;
  42.         q2.push(Date(2018, 10, 29));
  43.         q2.push(Date(2018, 10, 28));
  44.         q2.push(Date(2018, 10, 30));
  45.         cout << q2.top() << endl;
  46. }

  复制代码
  
  
  对于STL中我们常用的一些容器及容器适配器到这里就竣事了。在C++中STL的学习是很告急的，渴望各人可以继承学习下去。网上有句话说：“不懂STL，不要说你会C++”。STL是C++中的良好作品，有了它的伴随，很多底层的数据布局以及算法都不必要本身重新造轮子，站在前人的肩膀上，健步如飞的快速开辟。
  

尾声

   如有马虎或不敷之处接待各人在批评区留言大概私信，同时也接待各位一起探究学习。感谢您的观看！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告