C++ STL详解（2）

太过爱你忘了你带给我的痛 2022-10-31 01:00 15阅读 0赞

**上一篇博客：[C++ STL详解（1）][C_ STL_1]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  刷题时常用的STL
 *   *  string
     *   *  size()
         *  clear()
         *  操作符(Operators)
         *  compare()
         *  substr()
         *  c\_str()
         *  find()
         *  关于string的更多用法
     *  priority\_queue
     *   *  push()
         *  top()
         *  empty()
         *  size()
         *  pop()
         *  如何定义小根堆
         *  堆排序

# 刷题时常用的STL #

## string ##

之前写过一篇 **string** 的简介：[C++ String类学习总结][C_ String] 以及一篇有关输入问题的解决： [连着使用cin和getline()只能输入一次的问题][cin_getline] 但是不是特别全面，这里再补充说明一下。

### size() ###

返回字符串中字符的数量

#include<iostream>
    #include<string>
    
    using namespace std;
    
    int main() { 
    	string str = "AC-fun";
    	cout << str.size();
    	// 输出结果：6
    	return 0;
    }

### clear() ###

清空一个字符串

#include<iostream>
    #include<string>
    
    using namespace std;
    
    int main() { 
    	string s = "string";
    	cout << s;
    	s.clear(); // 清空一个字符串 
    	cout << endl;
    	cout << "清空后字符串的长度为：" << s.size() << endl;
    	cout << "清空后字符串的内容为：" << s;
    	return 0;
    }

### 操作符(Operators) ###

你可以用 `==, >, <, >=, <=, !=` 比较字符串，可以用 `+` 或者 `+=` 操作符连接两个字符串，并且可以用 `[]` 获取特定的字符。

### compare() ###

**compare()** 函数以多种方式比较本字符串和 **str**，按照 `字典序` 进行排序。使用 **this** 代表当前字符串，**str** 代表与 **this** 比较的字符串。那么如果 `this > str` 则 返回值大于零；如果 `this = str` 那么 返回值等于零；如果 `this < str` 那么 返回值小于零。此函数也有多种比较方式，下面分别进行介绍。

*  比较自己 **(this)** 和 **str**

#include<iostream>
    #include<string>
    
    using namespace std;
    
    int main() { 
    	string str1 = "aaa", str2 = "ab";
    	if (str1.compare(str2) > 0) cout << "str1 > str2";
    	else if (str1.compare(str2) == 0) cout << "str1 = str2";
    	else cout << "str1 < str2";
    	
    	// 输出结果：str1 < str2 
    	return 0;
    }

*  比较 **自己的子串** 和 **str**  
     子串以 **index** 索引开始(从 **0** 开始），长度为 **length**。 形式为：`str1.compare(index, length, str2)` 表示比较 **str1** 的子串与 **str2** 的大小。

#include<iostream>
    #include<string>
    
    using namespace std;
    
    int main() { 
    	string str1 = "abcdef", str2 = "ef";
    	int flag = str1.compare(4, 2, str2);
    	if (flag) cout << "str1 > str2";
    	else if (flag == 0) cout << "str1 = str2";
    	else cout << "str1 < str2";
    	
    	// 输出结果：str1 = str2 
    	return 0;
    }

*  比较 **自己的子串** 和 **str的子串**  
     比较形式为：`str1.compare(index, length, str2, index2, length2)`。其中 index2 和 length2 引用 str，index 和 length 引用str1。 如果不写 **index2** 则 **str2** 的子串以索引 **0** 开始，长度为 length2，str1 的子串以 index 开始，长度为 length。

#include<iostream>
    #include<string>
    
    using namespace std;
    
    int main() { 
    	string str1 = "abcdef", str2 = "abef";
    	int flag = str1.compare(4, 2, str2, 2, 2);
    	if (flag) cout << "str1 > str2";
    	else if (flag == 0) cout << "str1 = str2";
    	else cout << "str1 < str2";
    	
    	// 输出结果：str1 = str2 
    	return 0;
    }

### substr() ###

substr()返回本字符串的一个子串，从index开始，长num个字符。形式为：`str.substr(index, length)`。如果不写参数 **length** 或者参数 **length** 超过了 **str** 的长度，那么就将从 index 开始之后的所有字符输出。

#include<iostream>
    #include<string>
    
    using namespace std;
    
    int main() { 
    	string str = "AC-fun";
    	cout << str.substr(3, 3);
    	
    	// 输出结果：fun
    	return 0;
    }

### c\_str() ###

**c\_str()** 函数返回一个指向正规 C 字符串的指针，即返回存储字符串的字符数组的`起始地址`。利用这个函数可以使用 **printf()** 函数来输出 **string** 字符串。

#include<iostream>
    #include<string>
    #include<cstdio>
    
    using namespace std;
    
    int main() { 
    	string str = "AC-fun";
    	printf("%s", str.c_str());
    	
    	// 输出结果：AC-fun
    	return 0;
    }

### find() ###

在字符串中查找字符串。此函数有三种重载方式。下面分别进行介绍。

*  **str1.find(string str2, int index)**  
     返回 **str2** 在字符串 **str1** 中第一次出现的位置（从index开始查找）如果不写 **index** 参数，则直接从 **str1** 的开头开始查找。如果找到了返回 **str2** 第一次出现的位置（下标从 0 开始）；如果没找到则返回 `string::npos`。对于 `string::npos` C++ 的官方文档对它的解释为：

>  `static const size_t npos = -1;` **npos**是一个静态成员常量值，对于 **size\_t** 类型的元素，该常量的最大值可能。该值在字符串成员函数中用作len（或sublen）参数的值时，表示“直到字符串结尾”。 作为返回值，通常用于表示没有匹配项。 该常量定义为值 `-1`，这是因为 **size\_t** 是无符号整数类型，因此它是此类型可能的最大可表示值。

因此，在判断字符串有没有时，可以直接判断是否等于 `string::npos`，也可以判断是否等于 `-1`。

#include<iostream>
    #include<string>
    #include<cstdio>
    
    using namespace std;
    
    int main() { 
    	string str1 = "AC-fun", str2 = "fun", str3 = "good";
    	if (str1.find(str2, 0) != -1) cout << "Yes" << endl;
    	if (str1.find(str3, 0) == string::npos) cout << "No";
    	// 输出结果：Yes
    	// No
    	return 0;
    }

*  **str1.find(char ch, int index)**  
     返回字符 **ch** 在字符串中第一次出现的位置（从 **index** 开始查找）。如果没找到就返回 `string::npos`。

#include<iostream>
    #include<string>
    #include<cstdio>
    
    using namespace std;
    
    int main() { 
    	string str1 = "AC-fun";
    	if (str1.find('-', 0) != -1) puts("Yes");
    	else puts("No");
    	// 输出结果：Yes
    	return 0;
    }

### 关于string的更多用法 ###

string还有很多函数，但是一般常用的函数就是以上提到的，想要学习更多用法请看：[C++ API string][C_ API string]

## priority\_queue ##

**priority\_queue** 优先队列总能 保证优先级最高的元素位于队头，最重要的原因是其底层采用 `堆` 数据结构存储结构。STL 的优先队列默认是 `大根堆`，即最大的元素总是位于队头。其操作方式与队列 **queue** 基本相同。优先队列的头文件也是 `#include<queue>`。时间复杂度为：O(n l o g n logn logn)。

### push() ###

插入元素，并对底层容器排序。

#include<iostream>
    #include<queue>
    
    using namespace std;
    
    int main() { 
    	priority_queue<int> heap;
    	heap.push(1);
    	heap.push(2);
    	heap.push(3);
    	
    	// 使用 top() 访问堆顶元素
    	cout << heap.top();
    	// 输出结果：3 
    	return 0;
    }

### top() ###

访问堆顶元素。演示代码同 **push()**。

### empty() ###

检查底层的容器是否为空。若底层容器为空则为 `true` ，否则为 `false` 。

### size() ###

返回底层容器中的元素个数，即 **heap.size()**。

#include<iostream>
    #include<queue>
    
    using namespace std;
    
    int main() { 
    	priority_queue<int> heap;
    	heap.push(1);
    	heap.push(2);
    	heap.push(3);
    	cout << heap.size(); 
    	// 输出结果：3 
    	return 0;
    }

### pop() ###

弹出堆顶元素。

#include<iostream>
    #include<queue>
    
    using namespace std;
    
    int main() { 
    	priority_queue<int> heap;
    	heap.push(1);
    	heap.push(2);
    	heap.push(3);
    	cout << "当前堆顶元素为:" << heap.top() << endl; 
    	// 弹出堆顶元素 
    	heap.pop();
    	cout << "当前堆顶元素为:" << heap.top();
    	return 0;
    }

### 如何定义小根堆 ###

第一种方式是可以直接插入 **-x**，那么就可以直接利用大根堆创建了小根堆，输出的时候输出 **-x** 即可。  
 第二种方式是使用 **priority\_queue** 提供的方法。

#include<iostream>
    #include<queue>
    #include<vector>
    
    using namespace std;
    
    int main() { 
    	// 定义一个小根堆 
    	priority_queue<int, vector<int>, greater<int> > heap; 
    	heap.push(1);
    	heap.push(2);
    	heap.push(3);
    	cout << "当前堆顶元素为:" << heap.top() << endl; 
    	return 0;
    }

### 堆排序 ###

堆是一棵 **完全二叉树** ，可以使用数组模拟堆的实现。可以使用一维数组 **h\[\]** 来进行存储，对于根节点 **x** ，它的左儿子的下标为 **x  ∗ \* ∗ 2**，右儿子的下标为 **x  ∗ \* ∗ 2 + 1**。

构建一个小跟堆其中最关键的一个函数就是 **down()** 函数。只要当前的根节点不是最小的元素那么就将其向下移动。直到当前的根节点是最小的元素。代码及主要思路如下：

void down(int u) { 
        int t = u;
        // 找出根、左、右三个点做小的那个点
        if (2 * u <= cnt && h[2 * u] < h[t]) t = 2 * u; 
        // 首先判断一下当前的根节点有没有左孩子，如果有判断一下根节点和左孩子的大小
        if (2 * u + 1 <= cnt && h[2 * u + 1] < h[t]) t = 2 * u + 1;
        // 然后再判断一下当前根节点有没有右孩子，如果有判断一下上一步比较出来的做小值和当前右孩子的值的大小
        if (u != t) { 
            swap(h[u], h[t]);
            // 此时原来的元素 h[u] 就被换到了下标为 t 的数组中，所以继续 down(t)
            down(t);
        }
    }

那么如何弹出栈顶元素呢？只要将第一个元素与最后一个元素交换，然后将指向堆中最后一个指针向前移动一个，再 **down(1)** 即可。这样就可以在删除时一直保证堆顶元素时最小的元素。

**完整代码：**

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    
    using namespace std;
    
    const int N = 100010;
    int n, m;
    int h[N], cnt;  // 最好不要使用 size 作为变量，因为有的头文件里会有size函数，容易冲突
    
    void down(int u) { 
        int t = u;
        // 找出根、左、右三个点做小的那个点
        if (2 * u <= cnt && h[2 * u] < h[t]) t = 2 * u; 
        // 首先判断一下当前的根节点有没有左孩子，如果有判断一下根节点和左孩子的大小
        if (2 * u + 1 <= cnt && h[2 * u + 1] < h[t]) t = 2 * u + 1;
        // 然后再判断一下当前根节点有没有右孩子，如果有判断一下上一步比较出来的做小值和当前右孩子的值的大小
        if (u != t) { 
            swap(h[u], h[t]);
            // 此时原来的元素 h[u] 就被换到了下标为 t 的数组中，所以继续 down(t)
            down(t);
        }
    }
    
    int main() { 
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
        cnt = n;
        for (int i = n / 2; i; i--) down(i);
        // 先输入再维护小根堆的时间复杂度为 O(n),而一边输入一边维护的时间复杂度为 Nlog(N)
        while (m--) { 
            printf("%d ", h[1]);
            h[1] = h[cnt];
            cnt--;
            down(1);
        }
        return 0;
    }

--------------------

> 未完待续，持续更新中……  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_ffffff_t_70][]

[C_ STL_1]: https://ac-fun.blog.csdn.net/article/details/113864734
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[C_ String]: https://ac-fun.blog.csdn.net/article/details/104416510
[cin_getline]: https://ac-fun.blog.csdn.net/article/details/104432933
[C_ API string]: http://www.cplusplus.com/reference/string/string/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_ffffff_t_70]: /images/20221024/bc34c8db12744ffb908389ac0c5818c3.png