6.1 Vector常见用法详解

1. vector定义

ps: 头文件 #include 

  1. vector<typename> name;
  1.  **我们其实可以把vector理解为变长数组。长度可以根据需要进行变化。**
  1. vector<vector<int> > vi;

上面这个可以理解为两个维都可变长的二维数组。

2. vector内元素的访问

（1）下标访问（vi[0]）（但是越界容易出问题，不常用）

（2）迭代器访问（important）

  1. vector<int >::iterator it;
  1. **这样就得到了迭代器it，并可以通过*it来访问vector里的元素。**

3. 常用函数

（1）push_back( ) (在后面加元素)

（2）pop_back( ) (删除尾元素) （不要参数）

（3）size( ) (获得vector中元素的个数)

（4）clear( ) （清空所有元素，size()变为0了）

（5） insert( )

  1.  **insert(it，x)用来向任意迭代器it处插入一个元素x，时间复杂度O(N)**

（6）erase( )

erase（）既可以删除单个元素，也可以删除一个区间的元素，但是注意：区间还是左闭右开
下面的代码综合使用了上述几种函数：

  1. #include <cstdio>
  2. #include <vector>
  3. using namespace std;
  4. int main()
  5. {
  6.     vector<int> vi;
  7.     vector<int>::iterator it;
  8.     for(int i = 0; i < 10; ++i){
  9.         vi.push_back(i);
  10.     }
  11.     vi.pop_back();
  12.     for(it = vi.begin(); it != vi.end(); ++it){
  13.         printf("%d ",*it);
  14.     }
  15.     printf("\n");
  16.     printf("size: %d\n",vi.size());
  17.     vi.insert(vi.begin()+2,-1);
  18.     for(it = vi.begin(); it != vi.end(); ++it){
  19.         printf("%d ",*it);
  20.     }
  21.     printf("\n");
  22.     printf("size: %d\n",vi.size());
  23.     vi.erase(vi.begin()+1);
  24.     for(it = vi.begin(); it != vi.end(); ++it){
  25.         printf("%d ",*it);
  26.     }
  27.     printf("\n");
  28.     printf("size: %d\n",vi.size());
  29.     vi.erase(vi.begin()+5,vi.begin()+7);
  30.     for(it = vi.begin(); it != vi.end(); ++it){
  31.         printf("%d ",*it);
  32.     }
  33.     printf("\n");
  34.     printf("size: %d\n",vi.size());
  35.     vi.clear();
  36.     printf("size: %d  ",vi.size());
  37.     return 0;
  38. }

4. vector常见用途

（1）储存数据

（2）用邻接表存储图

6.2 set的常见用法解析 （集合的原理）

  1.  **set是一个内部自动有序且不含重复元素的容器。**

1. set的定义

  1. set<typename> name;
  2. set<typename> Arrayname[arraysize] ;

2. set容器内元素的访问（only through 迭代器）

注意： 除了vector和string之外的STL容器都不支持*(it+i)的访问方式 ！！ 因此只能通过下列方式枚举。

  1. #include <cstdio>
  2. #include <set>
  3. using namespace std;
  4. int main()
  5. {
  6.     set<int> st;
  7.     set<int>::iterator it;
  8.     st.insert(2);
  9.     st.insert(5);
  10.     st.insert(4);
  11.     for(it = st.begin(); it != st.end(); ++it){
  12.         printf("%d  ",*it);
  13.     }
  14.     return 0;
  15. }

尝试跑一下程序，输出为2 4 5，发现set内的元素自动递增排序，且自动去除了重复元素。

3. set常用函数

（1）insert（）

（2）find（）

find(value) 返回set中对应值为value的迭代器。

（3）erase（） （单个 & 区间）

1）删除单个元素

(a) st.erase(it)
  1. st.erase(st.find(100);  //利用find函数找到100，然后用erase删除

(b) st.erase(value)
  1. st.erase(100);

2）删除区间内所有元素

  1. it = st.find(100);
  2. st.erase(it,st.end());  // 删除元素100至set末尾之间的所有元素

（4） size（） （获得set内元素个数）

（5) clear( ) (清空set内所有元素)

6.3 String常见用法解析

注意：头文件是#include ，和和不一样

1. string的定义

  1. // 两种方法
  2. string s1;
  3. string s2 = "assdf";

2. string中内容的访问

（1）通过下标访问

  1. #include <string>
  2. using namespace std;
  3. int main()
  4. {
  5.     string str = "abcde";
  6.     for(int i = 0; i < str.length(); ++i){
  7.         printf("%c",str[i]);
  8.     }
  9.     return 0;
  10. }

注意：读入和输出字符串时这个只能用cin 和 cout.

（2）通过迭代器访问

首先来看一下string 的 迭代器的定义：

  1.     string::iterator it;

借此，可以通过*it来访问string的内容：👇

  1. #include <string>
  2. using namespace std;
  3. int main()
  4. {
  5.     string str = "abcde";
  6.     string::iterator it;
  7.     for(it = str.begin(); it != str.end(); ++it){
  8.         printf("%c",*it);
  9.     }
  10.     return 0;
  11. }

3. 常用函数解析

（1） operator += (字符串拼接，b接到a的后面)

（2）compare operator (可以直接当数字比较，按照字典序比大小)、

（3）length( ) & size（） （length返回字符串string的长度，即存放发字符数）

（4）insert( )

1) insert（pos,string）

  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4. int main()
  5. {
  6.     string str1 = "abcde";
  7.     string str2 = "ppp";
  8.     str1.insert(1,str2);     // str2的位置直接写"ppp"也行
  9.     cout<<str1<<endl;
  10.     return 0;
  11. }
  12. // 输出： apppbcde

2）insert（it,it2,it3）,it为原字符串的欲插入位置，it2和it3为待插入字符串的收尾迭代器（左闭右开【it2,it3））

（5）erase（）

1）删除单个元素

  1. str.erase(it);   // it是要删除元素的迭代器

2) 删除区间内所有元素 (两种方法如下：)

  1. str.erase(it1,it2);   // it1,it2是要删除元素的首尾迭代器（左闭右开）
  1. str.erase(pos,length);   // 删除从pos开始的length个字符

看个例子：

  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4. int main()
  5. {
  6.     string str = "abcdefghi";
  7.     string::iterator it = str.begin();
  8.     for(it = str.begin(); it != str.end(); ++it){
  9.         printf("%c",*it);
  10.     }
  11.     printf("\n");
  12.     it = str.begin();
  13.     str.erase(it+1,it+3);
  14.     for(it = str.begin(); it != str.end(); ++it){
  15.         printf("%c",*it);
  16.     }
  17.     printf("\n");
  18.     it = str.begin();
  19.     str.erase(4,2);
  20.     for(it = str.begin(); it != str.end(); ++it){
  21.         printf("%c",*it);
  22.     }
  23.     printf("\n");
  24.     return 0;
  25. }
  27. //输出：
  28. abcdefghi
  29. adefghi
  30. adefi

(6) clear ()

(7) substr ( )

substr(pos,len)返回从pos号位开始，长度为len的子串。 

  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4. int main()
  5. {
  6.     string str = "abcdefghi";
  7.     cout << str.substr(2,4)<<endl;
  8.     return 0;
  9. }
  10. // 输出： cdef

（8）string::npos

string::npos作为find函数失配时的返回值（当成常数，unsigned_int类型）

（9）find（）

1）str.find（str2），当str2是str的子串时，返回第一次出现的位置（索引）；如果不是子串，返回string::npos

2）str.find(str2,pos)，从str的pos号位开始匹配str2，返回值与上相同

（10）replace( )

1）str.replace（pos,len,str2）把str从pos号位开始，长度为len的子串替换为str2

2) str.replace（it1,it2,str2）把 [ it1, it2 ) 范围的子串替换为str2

4. Example : A1060

如果一台机器只能保存 3 位有效数字，则浮点数 12300 和 12358.9 被认为是相等的，因为它们都保存为 0.123×10^5

问题描述：

用简单的切碎。现在给定机器上的有效位数和两个浮点数，您应该知道它们在该机器中是否被认为相等。

输入规格：

每个输入文件包含一个测试用例，它给出三个数字 N、A 和 B，其中 N (<100) 是有效位数，A 和 B 是要比较的两个浮点数。每个浮点数都是非负数，不大于 10^100 , 并且其总位数小于 100。

输出规格：

对于每个测试用例，如果两个数字相等，则打印一行 YES，然后打印标准格式 0.d[1]…d[N]*10^k (d[1]>0除非数字是 0);或否，如果他们不被平等对待，然后是标准形式的两个数字。所有术语必须用空格分隔，行尾没有多余的空格。
注意：假设简单切碎，不进行四舍五入。

Sample Input 1:

3 12300 12358.9

Sample Output 1:

YES 0.123*10^5

Sample Input 2:

3 120 128

Sample Output 2:

NO 0.12010^3 0.12810^3

题解：

image.png
image.png

代码：

  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4. int n;   // 精度数
  5. string change (string s,int& e)  // e是指数
  6. {
  7.     int k = 0;
  8.     while (s.length() > 0 && s[0] == '0')
  9.     {
  10.         s.erase(s.begin());  // 去掉s的前导0
  11.     }
  12.     if(s[0] == '.'){   // 去掉前导0就是小数点，说明s是小于1的数
  13.         s.erase(s.begin());
  14.         while (s.length() > 0 && s[0] == '0'){
  15.             s.erase(s.begin());
  16.             --e;      // 去掉一个0，e就--, 0.003 指数就是-2
  17.         }
  18.     }
  19.     else{  // 去掉前导0后不是小数点，则找到后面的小数点并删除
  20.         while (k < s.length() && s[k] != '.'){
  21.             ++k;
  22.             ++e;
  23.         }
  24.         if(k < s.length()){
  25.             s.erase(s.begin()+k);
  26.         }
  27.     }
  28.     if(s.length() == 0){   // 去掉前导0后长度变为0，则说明这个数就是0
  29.         e = 0;
  30.     }
  31.     int num = 0;
  32.     k = 0;   // !!!!!!! 一定把k重新置0，significant!!!
  33.     string res;
  34.     while (num < n){
  35.         if(k < s.length()){
  36.             res += s[k++];
  37.         }
  38.         else{
  39.             res += '0';
  40.         }
  41.         ++num;
  42.     }
  43.     return res;
  44. }
  45. int main()
  46. {
  47.     string s1,s2,s3,s4;
  48.     int e1 = 0, e2 = 0;
  49.     cin>>n>>s1>>s2;
  50.     s3 = change(s1,e1);
  51.     s4 = change(s2,e2);
  52.     if(s3 == s4 && e1 == e2){
  53.         cout<<"YES 0."<<s3<<"*10^"<<e1<<endl;
  54.     }
  55.     else{
  56.         cout<<"NO 0."<<s3<<"*10^"<<e1<<" "<<"0."<<s4<<"*10^"<<e2<<endl;
  57.     }
  58.     return 0;
  59. }

6.4 map常用用法详解

map可以将任何基本类型映射到任何基本类型。

1. map的定义：

  1. map<typename1, typename2> mp;

注意：如果是字符串到整型的映射，必须是，不能是char数组

2. map元素访问

（1）通过下标访问

我们先来看一组代码：

  1. #include <map>
  2. using namespace std;
  3. int main()
  4. {
  5.     map<char, int> mp;
  6.     mp['c'] = 20;
  7.     mp['c'] = 30;
  8.     printf("%d",mp['c']);
  9.     return 0;
  10. }
  11. // 输出：30

这段代码内部 不仅说明了map可以通过下标来访问，还说明了map中的键值是唯一的，上面代码中30就把20覆盖掉了。

（2）通过迭代器访问

用it->first访问键，用it->second访问值。

  1. #include <map>
  2. using namespace std;
  3. int main()
  4. {
  5.     map<char, int> mp;
  6.     map<char, int>::iterator it;
  7.     mp['m'] = 20;
  8.     mp['r'] = 30;
  9.     mp['a'] = 40;
  10.     for(it = mp.begin(); it != mp.end(); ++it)
  11.     {
  12.         printf("%c %d\n",it->first,it->second);
  13.     }
  14.     return 0;
  15. }
  17. //输出：
  18. a 40
  19. m 20
  20. r 30

我们看一下输出，就会发现输出中键已经被排好序了，从小到大，即a<m<r，这是因为map内部使用红黑树实现的（set也是），因此在建立映射的过程中实现从小到大排序的功能。

3. 常用函数解析

（1）find（）

find（key）返回值为key的映射的迭代器。（一般用it接收一下）(参数是key！！！)

（2）erase（）

1) 删除单个元素：

mp.erase（it）& mp.erase（key）

  1. #include <map>
  2. using namespace std;
  3. int main()
  4. {
  5.     map<char, int> mp;
  6.     map<char, int>::iterator it;
  7.     mp['m'] = 20;
  8.     mp['r'] = 30;
  9.     mp['a'] = 40;
  10.     it = mp.find('m');
  11.     mp.erase(it);
  12.     for(it = mp.begin(); it != mp.end(); ++it){
  13.         printf("%c %d\n",it -> first, it -> second);
  14.     }
  15.     printf("size: %d\n",mp.size());
  16.     mp.erase('r');
  17.     for(it = mp.begin(); it != mp.end(); ++it){
  18.         printf("%c %d\n",it -> first, it -> second);
  19.     }
  20.     printf("size: %d\n",mp.size());
  21.     return 0;
  22. }
  24. // 输出：
  25. a 40
  26. r 30
  27. size: 2
  28. a 40
  29. size: 1

2）删除区间内所有元素

mp.erase（first, last）（左闭右开）

（3）size（）（获得映射的对数）

（4）clear（）（清空map中所有元素）

4. map常见用途

①需要建立字符（或字符串）与整数之间映射的题目，使用map可以减少代码量。
②判断大整数或者其他类型数据是否存在的题目，可以把map当bool数组用。
③字符串和字符串的映射也有可能会遇到。
延伸:map的键和值是唯一的，而如果一个键需要对应多个值，就只能用multimap。另外，C++11标准中环广加了unordered_map，以散列代替map内部的红黑树实现，使其可以用来处理只映射而不按kev排序的需求，速度比map要快得多，有兴趣的读者可以自行了解,此处不多作说明。

6.5 queue常见用法解析（数据结构——队列）

1. queue的定义

  1.     queue<typename > name;

2. queue元素访问

队列，先进先出，访问方式唯一：front访问队首元素，back( )访问队尾元素。

3. 常用函数解析

（1） push( ) （入队）

（2）front（）、back（） （访问队首和队尾元素）

（3）pop（） （队首元素出队）

（4）empty（） （返回true则空，返回false则不空）

（5）size（） （返回queue内元素的个数）

  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. int main()
  5. {
  6.     queue<int> q;
  7.     for(int i = 1; i <= 5; ++i)
  8.     {
  9.         q.push(i*2);   // 依次入队1、2、3、4、5
  10.     }
  11.     for(int i = 1; i <= 3; ++i){
  12.         q.pop();
  13.     }
  14.     printf("front:%d\n",q.front());
  15.     printf("size:%d\n",q.size());
  16.     if(q.empty() == true){
  17.         printf("Empty!\n");
  18.     }
  19.     if(q.empty() == false){
  20.         printf("Not Empty!\n");
  21.     }
  22.     return 0;
  23. }
  24. //输出：
  25. front:8
  26. size:2
  27. Not Empty!

注意： 使用front( ）和 pop( )函数前，必须用empty( )函数判断队列是否为空，否则可能因队空而出现错误。

4. queue常见用途（感兴趣可以了解deque双端队列）

广搜不用手动实现队列了

6.6 priority_queue常见用法解析

priority_queue称为优先队列，底层用堆来实现。队首元素一定是优先级最高的。（可以定义数越小优先级越高，这个随意定义）

1. priority_queue的定义

  1.     priority_queue<typename > q;

2. priority_queue元素的访问

只能通过top( ) 来访问队首元素（也成为堆顶元素），也就是优先级最高的元素。

3. priority_queue常用函数解析

（1）push( ) (push(x)将令x入队)

（2）top( ) （获得队首元素）

（3）pop( ) （令队首元素出队）

（4）empty( ) (同上)

（5）size( ) （同上）

  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. int main()
  5. {
  6.     priority_queue<int > q;
  7.     q.push(3);
  8.     q.push(4);
  9.     q.push(1);
  10.     printf("top_now: %d\n",q.top());
  11.     q.pop();
  12.     printf("top_now: %d\n",q.top());
  13.     return 0;
  14. }
  15. //输出：
  16. top_now: 4
  17. top_now: 3

4. priority_queue内元素优先级设置

本章最开始我们说了优先级的设置可以自定义，不一定是数字越大优先级越高，接下来我们一起来看一下优先级的设置。

（1）基本数据类型的优先级设置

如果不做特殊的事情，对于基本数据类型，编译器默认数字越大优先级越高。下面两种写法其实是等价的：

  1.     priority_queue<int > q;
  1.     priority_queue<int, vector<int>, less<int> > q;

我们有必要解释一下后两个参数，第二个参数是来承载底层数据结构堆（heap）的容器，第一个参数是int型，这里类型就是int。第三个参数是优先级设置参数，less表示数字越大优先级越高，而greater表示数字越小优先级越大。
因此，要想把数字最小的放在队首，只需如下定义：

  1.     priority_queue<int, vector<int>, greater<int> > q;

还需要说明一下，上面这行代码随后两个“>”要加空格，C++11会把两个连在一起的认为是位运算。

（2）结构体的优先级设置

核心：小于号“<”的重载 （不要重载>号，会有问题，重载<能解决全部问题了）
下面这段代码就实现了价格低的优先级高（在队首）（与sort的cmp的功能相反）

  1. struct fruit{
  2.     string name;
  3.     int price;
  4.     friend bool operator < (fruit f1, fruit f2){
  5.         return f1.price > f2.price;
  6.     }
  7. };

当然，也可以使用三个参数定义priority_queue，然后第三个蚕食换成cmp，就类似sort的用法。
image.png
最后指出，如果结构体内的数据较为庞大（例如出现了字符串或者数组)，建议便用5用来提高效率，此时比较类的参数中需要加上“const”和“&”，如下所示:
image.png

5. priority_queue常见用途

（1）解决贪心问题，并对Dijkstra算法优化（本质是堆）

（2）使用top前，必须用empty判断是否为空

6.7 stack常见用法详解 （数据结构——栈）

1. stack的定义

  1. stack<typename > name;

2. stack容器内元素的访问

只能通过top来获取栈顶元素。

3. stack常用函数介绍

（1) push( ) (入栈)

（2）top( ) (获得栈顶元素)

（3）pop( ) (弹出栈顶元素)

（4）empty( ) (同上)

（5）size( ) (同上)

4. stack常见用途

stack用来模拟实现一些递归。

6.8 pair的常见用法解析（头文件：）

pair可以理解为内部有两个元素的结构体。
map头文件包含utility

1. pair的定义

pair有两个参数，分别对应first和second的数据类型：👇

  1. pair<typeName1, typrName2> name;

想要在定义的时候即初始化，如下：👇

  1. pair<string, int> p("hello",6);

2. pair元素访问

pair中一共有两个元素，分别是first和second，当作结构体来访问就OK了。

3. pair常用函数

（1）比较操作函数

两个类型相同的pair可以直接比大小，先比firsr，再比second。

4. pair常见用途

（1）代替二元结构体及其构造函数，节省时间

（2）作为map的键值进行插入，如下：

  1. #include <map>
  2. #include <iostream>
  3. using namespace std;
  4. int main()
  5. {
  6.     map<string, int> mp;
  7.     map<string, int>::iterator it;
  8.     mp.insert(make_pair("aa",5));
  9.     mp.insert(pair<string, int>("bb",66));   // 直接初始化，不用起名字
  10.     for(it = mp.begin(); it != mp.end(); ++it){
  11.        cout << it->first << " " << it->second <<endl;
  12.     }
  13.     return 0;
  14. }
  15. // 输出：
  16. aa 5
  17. bb 66

6.9 algorithm头文件下的常用函数

1. max( ), min( ) ,abs( )

max和min参数必须是2个，可以嵌套。整型用abs( )，浮点型用fabs( )

2. swap( )

swap(a, b) 用来交换a,b的值

3. reverse( )

reverse(it1, it2)可以将数组指针或容器的迭代器在【it1,it2) 范围内的元素进行反转。

4. next_permulation( )

给出一个序列在全排列中的下一个序列，详见：https://blog.csdn.net/sgsyacm/article/details/80139089

5. fill( )

fill函数类似于我们之前学过的memset，但是比memset更好用，我们之前说过，memset只能把整体赋值为0或-1，但是fill可以赋为任意的值。

  1. #include <map>
  2. #include <iostream>
  3. using namespace std;
  4. int main()
  5. {
  6.     int a[5] = {1, 2, 3, 4, 5};
  7.     fill(a, a + 5, 20);
  8.     for(int i = 0; i < 5; ++i){
  9.         printf("%d  ",a[i]);
  10.     }
  11.     return 0;
  12. }

6. sort函数 （略）

7. lower_bound( ) 和 upper_bound( )

lower_bound(first,last,val) 寻找范围内第一个 >= val的位置，返回指针或迭代器 （不存在则返回应插入的位置）
upper_bound(first,last,val) 寻找范围内第一个 > val的位置，返回指针或迭代器 （不存在则返回应插入的位置）
直接调用返回的是指针或者迭代器，如果我们想得到数组元素的下标，那就用一个指针接收返回值，然后减首元素地址（数组名）即可。我们看下这个例子：👇

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. int main()
  5. {
  6.     int a[10] = {1,2,2,3,3,3,5,5,5,5};
  7.     int *lowerPos = lower_bound(a, a + 10, -1);
  8.     int *upperPos = upper_bound(a, a + 10, -1);
  9.     printf("%d, %d\n",lowerPos - a, upperPos - a);
  10.     lowerPos = lower_bound(a, a + 10, 3);
  11.     upperPos = upper_bound(a, a + 10, 3);
  12.     printf("%d, %d\n",lowerPos - a, upperPos - a);
  13.     lowerPos = lower_bound(a, a + 10, 10);
  14.     upperPos = upper_bound(a, a + 10, 10);
  15.     printf("%d, %d\n",lowerPos - a, upperPos - a);
  16. }
  17. //
  18. 输出：
  19. 0, 0
  20. 3, 6
  21. 10, 10