C++ STL —— 基于算法竞赛

原作者在这里！本文是基于行码棋的文章进行的翻改！

[!NOTE]

相关好文推荐，这篇 STL 我也觉得非常不错！分享给你！

简单分享一下：起初入门 C++，我特别幸运地找到了这篇超级适合 STL 入门和竞赛的文章！一开始只是随便翻了翻，没想到 内容不仅全面详细，而且非常实用，只记得那天下午用了两个小时，从头到尾仔细的看了一遍，结果越看越上头，不靠视频也能高效、快速的学习（对当时完全没阅读习惯的我来说，简直是个奇迹）。后来的几天时间也是断断续续的在看，一周时间就可以 快速上手 STL 了。相信屏幕前的你比我更快！

这篇文章最大的优点就是 实用，不是那种光讲理论、没法落地的内容。在后来的刷题和深入学习的过程中，每次遇到不会的地方，我也时不时的会翻出来查，就像一本随身的 STL 字典。某些地方反复看了很多遍，每次都会有新的收获。随着不断 实践 + 回顾，相关知识越来越清晰，使用起来也越来越顺手，简直就像高中查笔记一样，真的让我受益匪浅！希望也能帮到你~

[!TIP]

实践才是检验真理的唯一标准！

1. vector

1.1 介绍

1.1.1 简介

vector 为可变长数组（动态数组），定义的 vector 数组可以随时添加数值和删除元素。

注意：在局部区域中（比如局部函数里面）开 vector 数组，是在堆空间里面开的。

在局部区域开数组是在栈空间开的，而栈空间比较小，如果开了非常长的数组就会发生爆栈。

故局部区域 不可以 开大长度数组，但是可以开大长度 vector。

包含头文件：

1.1.2 初始化

  • 一维初始化：

    1
    2
    3
    vector<int> a; 				//定义了一个名为 a 的一维数组, 数组存储 int 类型数据
    vector<double> b; 			//定义了一个名为 b 的一维数组，数组存储 double 类型数据
    vector<node> c; 			//定义了一个名为 c 的一维数组，数组存储结构体类型数据，node 是结构体类型

    指定 长度 和 初始值 的初始化

    1
    2
    3
    vector<int> v(n); 			// 定义一个长度为 n 的数组，初始值默认为 0，下标范围 [0, n - 1]
    vector<int> v(n, 1); 		// v [0] 到 v [n - 1] 所有的元素初始值均为 1
    //注意：指定数组长度之后（指定长度后的数组就相当于正常的数组了）

    初始化中有多个元素

    1
    vector<int> a{1, 2, 3, 4, 5};		//数组 a 中有五个元素，数组长度就为 5

    拷贝初始化

    1
    2
    3
    vector<int> a(n + 1, 0);
    vector<int> b(a);               // 两个数组中的类型必须相同, a 和 b 都是长度为 n+1，初始值都为 0 的数组
    vector<int> c = a;              // 也是拷贝初始化, c 和 a 是完全一样的数组

  • 二维初始化：
    定义第一维固定长度为 5，第二维可变化的二维数组

    1
    2
    3
    vector<int> v[5];           //定义可变长二维数组
    //注意：行不可变（只有 5 行）, 而列可变, 可以在指定行添加元素
    //第一维固定长度为 5，第二维长度可以改变

    vector<int> v[5] 可以这样理解：长度为 5 的 v 数组，数组中存储的是 vector<int> 数据类型，而该类型就是数组形式，故 v 为二维数组。其中每个数组元素均为空，因为没有指定长度，所以第二维可变长。可以进行下述操作：

    1
    2
    v[1].push_back(2);
    v[2].push_back(3);

    行列均可变

    1
    2
    //初始化二维均可变长数组
    vector<vector<int>> v;			//定义一个行和列均可变的二维数组

    应用：可以在 v 数组里面装多个数组

    1
    2
    3
    4
    5
    vector<int> t1{1, 2, 3, 4};
    vector<int> t2{2, 3, 4, 5};
    v.push_back(t1);
    v.push_back(t2);
    v.push_back({3, 4, 5, 6}) 		// {3, 4, 5, 6}可以作为 vector 的初始化, 相当于一个无名 vector

    行列长度均固定 n + 1 行 m + 1 列初始值为 0

    1
    vector<vector<int>> a(n + 1, vector<int>(m + 1, 0));

    c++17 及以上支持的形式（定义模板类的对象时，可以不指定模板参数，但必须要在构造函数中能推导出模板参数）

    1
    2
    vector a{1, 2, 3, 4, 5}; 			// 声明一个 int 类型动态数组，初识元素自己指定
    vector b(n + 1, vector(m + 1, 0));

1.2 方法函数

1.2.1 函数总结

注：c 指定为数组名称

代码算法复杂度返回值类型含义
c.front()O(1)引用返回容器中的第一个数据
c.back()O(1)引用返回容器中的最后一个数据
c.at(idx)引用返回 c[idx] ，会进行边界检查，如果越界会报错，比直接使用 [] 更好一些，常在项目中使用
c.size()O(1)返回实际数据个数（unsigned 类型）
c.begin()O(1)迭代器返回首元素的迭代器（通俗来说就是地址）
c.end()O(1)迭代器返回最后一个元素后一个位置的迭代器（地址）
c.empty()O(1)bool判断是否为空，为空返回真，反之返回假
c.reserve(sz)为数组提前分配 sz 的内存大小，即改变了 capacity 的大小，主要是为了防止在 push_back 过程中多次的内存拷贝
c.assign(beg, end)将另外一个容器 [x.begin(), x.end()) 里的内容拷贝到 c 中
c.assign(n, val)将 n 个 val 值拷贝到 c 数组中，这会清除掉容器中以前的内容，c 数组的 size 将变为 n，capacity 不会改变
c.pop_back()O(1)删除最后一个数据
c.push_back(element)O(1)在尾部加一个数据
c.emplace_back(ele)O(1)在数组中加入一个数据，和 push_back 功能基本一样，在某些情况下比它效率更高，支持传入多个构造参数
c.clear()O(N)清除容器中的所有元素
c.resize(n, v)改变数组大小为 n, n 个空间数值赋为 v，如果没有默认赋值为 0
c.insert(pos, x)O(N)向任意迭代器 pos 插入一个元素 x
例：c.insert(c.begin() + 2, -1)将 -1 插入 c[2] 的位置
c.erase(first, last)O(N)删除 [first, last) 的所有元素

1.2.2 注意情况

  • end() 返回的是最后一个元素的后一个位置的地址，不是最后一个元素的地址，所有 STL 容器均是如此

  • 使用 vi.resize(n, v) 函数时，若 vi 之前指定过大小为 pre

    • pre > n ：即数组大小变小了，数组会保存前 n 个元素，前 n 个元素值为原来的值，不是都为 v
    • pre < n ：即数组大小变大了，数组会在后面插入 n - pre 个值为 v 的元素

    也就是说，这个初始值 v 只对新插入的元素生效。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    #include<bits/stdc++.h>
    using namespace std;
    void out(vector<int> &a)
    {
        for (auto &x: a) cout << x << " "; cout << "\n";
    }

    int main()
    {
    	vector<int> a(5, 1);
    	out(a); // 1 1 1 1 1
    	a.resize(10, 2);
    	out(a); // 1 1 1 1 1 2 2 2 2 2
    	a.resize(3, 3);
    	out(a); // 1 1 1
    	return 0;
    }

  • 使用 sort 排序要: sort(c.begin(), c.end());

sort() 为 STL 函数，请参考本文最后面 STL 函数系列。

对所有元素进行排序，如果要对指定区间进行排序，可以对 sort() 里面的参数进行加减改动。

1
2
vector<int> a(n + 1);
sort(a.begin() + 1, a.end()); 	// 对 [1, n] 区间进行从小到大排序

1.3 元素访问

共三种方法：

  1. 下标法： 和普通数组一样。注意：一维数组的下标是从 0 到 v.size() - 1 ，访问之外的数会出现越界错误！

  2. 迭代器法： 类似指针一样的访问 ，首先需要声明迭代器变量，和声明指针变量一样，可以根据代码进行理解（附有注释）。

1
2
vector<int> vi; 							//定义一个 vi 数组
vector<int>::iterator it = vi.begin();		  //声明一个迭代器指向 vi 的初始位置
  1. 使用 auto： 非常简便，但是会访问数组的所有元素（特别注意 0 位置元素也会访问到）。

1.3.1 下标访问

直接和普通数组一样进行访问即可。

1
2
3
4
5
6
7
8
9
10
11
12
//添加元素
for(int i = 0; i < 5; i++)
{
	vi.push_back(i);
}

//下标访问 
for(int i = 0; i < 5; i++)
{
	cout << vi[i] << " ";
}
cout << "\n";

1.3.2 迭代器访问

类似指针，迭代器就是充当指针的作用。

1
2
3
4
5
vector<int> vi{1, 2, 3, 4, 5};
//迭代器访问
vector<int>::iterator it;   
// 相当于声明了一个迭代器类型的变量 it
// 通俗来说就是声明了一个指针变量
  • 方式一：
1
2
3
4
5
6
vector<int>::iterator it = vi.begin(); 
for(int i = 0; i < 5; i++)
{
	cout << *(it + i) << " ";
}
cout << "\n";
  • 方式二：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int>::iterator it;
for(it = vi.begin(); it != vi.end();it ++)
{
	cout << *it << " ";
}
//vi.end()指向尾元素地址的下一个地址

// 或者
auto it = vi.begin();
while (it != vi.end())
{
    cout << *it << "\n";
    it++;
}

1.3.3 智能指针

只能遍历完数组，如果要指定的内容进行遍历，需要另选方法。auto 能够自动识别并获取类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 1. 输入
vector<int> a(n);
for (auto &x: a)
{
    cin >> x; // 可以进行输入，注意加引用
}

// 2. 输出
vector<int> v;
v.push_back(12);
v.push_back(241);
for(auto val : v)
{
	cout << val << " "; // 12 241
}

vector 注意：

  • vi[i] 和 *(vi.begin() + i) 等价，与指针类似。

  • vector 和 string 的 STL 容器支持 *(it + i) 的元素访问，其它容器可能也可以支持这种方式访问，但用的不多，可自行尝试。

2. stack

2.1 介绍

栈为数据结构的一种，是 STL 中实现的一个先进后出，后进先出的容器。

1
2
3
4
5
6
7
// 包含头文件：
#include <queue>

// 初始化：
stack<int> s;
stack<string> s;
stack<node> s;//node 是结构体类型

2.2 方法函数

代码含义
s.push(ele)元素 ele 入栈，增加元素 O(1)
s.pop()移除栈顶元素 O(1)
s.top()取得栈顶元素（但不删除）O(1)
s.empty()检测栈内是否为空，空为真 O(1)
s.size()返回栈内元素的个数 O(1)

2.3 栈元素访问

2.3.1 栈遍历

栈只能对栈顶元素进行操作，如果想要进行遍历，只能将栈中元素一个个取出来存在数组中。

1
2
3
4
5
6
7
8
9
10
11
stack<int> st;
for (int i = 0; i < 10; ++i)
{
	st.push(i);
}

while (!st.empty())
{
    int tp = st.top(); // 栈顶元素
    st.pop();
}

2.3.2 数组模拟栈进行遍历

通过一个 数组 对栈进行模拟，一个存放下标的变量 top 模拟指向栈顶的指针。

一般来说单调栈和单调队列写法均可使用额外变量 tt 或 hh 来进行模拟

特点： 比 STL 的 stack 速度更快，遍历元素方便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int s[100]; // 栈 从左至右为栈底到栈顶
int tt = -1; // tt 代表栈顶指针, 初始栈内无元素，tt 为-1

for(int i = 0; i <= 5; ++i)
{
	//入栈 
	s[++tt] = i;
}

// 出栈
int top_element = s[tt--]; 

//入栈操作示意
//  0  1  2  3  4  5  
//                tt
//出栈后示意
//  0  1  2  3  4 
//              tt

3. queue

3.1 介绍

队列是一种先进先出的数据结构。

1
2
3
4
// 包含头文件
#include<queue>
// 初始化
queue<int> q;

3.2 方法函数

代码含义
q.front()返回队首元素 O(1)
q.back()返回队尾元素 O(1)
q.push(element)尾部添加一个元素 element 进队 O(1)
q.pop()删除第一个元素 出队 O(1)
q.size()返回队列中元素个数，返回值类型 unsigned int O(1)
q.empty()判断是否为空，队列为空，返回 true O(1)

3.3 队列模拟

使用 q[] 数组模拟队列：

  • hh 表示队首元素的下标，初始值为 0。
  • tt 表示队尾元素的下标，初始值为 -1，表示刚 开始队列为空。

一般来说单调栈和单调队列写法均可使用额外变量 tt 或 hh 来进行模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int q[N];

int main()
{
	int hh = 0,tt = -1;
	
    //	入队 
	q[++tt] = 1;
	q[++tt] = 2; 
    
	//	将所有元素出队 
	while(hh <= tt)
    {
		int t = q[hh++];
		printf("%d ",t);
	}
	return 0;
 }

4. deque

4.1 介绍

首尾都可插入和删除的队列为双端队列。

1
2
3
4
//添加头文件
#include <deque>
//初始化定义
deque<int> dq;

4.2 方法函数

注意双端队列的常数比较大。

代码含义
push_back(x)/push_front(x)把 x 插入队尾后 / 队首 O(1)
back()/front()返回队尾 / 队首元素 O(1)
pop_back() / pop_front()删除队尾 / 队首元素 O(1)
erase(iterator it)删除双端队列中的某一个元素
erase(iterator first,iterator last)删除双端队列中 [first,last) 中的元素
empty()判断 deque 是否空 O(1)
size()返回 deque 的元素数量 O(1)
clear()清空 deque

4.3 注意点

deque 可以进行排序！

双端队列排序一般不用，感觉毫无用处，使用其他 STL 依然可以实现相同功能。

1
2
3
4
5
//从小到大
sort(q.begin(), q.end())
//从大到小排序
sort(q.begin(), q.end(), greater<int>());//deque 里面的类型需要是 int 型
sort(q.begin(), q.end(), greater());//高版本 C++才可以用

5. priority_queue

5.1 介绍

优先队列是在正常队列的基础上加了优先级，保证每次的队首元素都是优先级最大的。可以实现每次从优先队列中取出的元素都是队列中 优先级最大 的一个。它的底层是通过 堆 来实现的。

1
2
#include <queue>		        //头文件
priority_queue<int> q;	        //初始化定义

5.2 函数方法

代码含义
q.top()访问队首元素 O(1)
q.push()入队 O(logN)
q.pop()堆顶（队首）元素出队 O(logN)
q.size()队列元素个数 O(1)
q.empty()是否为空 O(1)
注意 没有 clear()！不提供该方法
优先队列只能通过 top() 访问队首元素（优先级最高的元素）

5.3 设置优先级

5.3.1 基本数据类型的优先级

  • 普通排序容器（sort/set/map）：less = 升序，greater = 降序。
  • priority_queue：less = 大根堆（降序堆顶），greater = 小根堆（升序堆顶）。
1
2
priority_queue<int> pq;                                 // 默认大根堆, 即每次取出的元素是队列中的最大值
priority_queue<int, vector<int>, greater<int>> q;       // 小根堆, 每次取出的元素是队列中的最小值

参数解释：

  • 第一个参数：就是优先队列中存储的数据类型。

  • 第二个参数：vector<int> 是用来承载底层数据结构堆的容器，若优先队列中存放的是 double 型数据，就要填 vector<double> 总之存的是什么类型的数据，就相应的填写对应类型。同时也要改动第三个参数里面的对应类型。

  • 第三个参数：less<int> 表示数字大的优先级大，堆顶为最大的数字 greater<int> 表示数字小的优先级大，堆顶为最小的数字 int 代表的是数据类型，也要填优先队列中存储的数据类型。

下面介绍基础数据类型优先级设置的写法：

  1. 基础写法（非常常用）：
1
2
3
priority_queue<int> q1;                                 // 默认大根堆, 即每次取出的元素是队列中的最大值
priority_queue<int, vector<int>, less<int>> q2;         // 大根堆, 每次取出的元素是队列中的最大值，同第一行
priority_queue<int, vector<int>, greater<int>> q3;      // 小根堆, 每次取出的元素是队列中的最小值
  1. 自定义排序：

下面的代码比较长，基础类型优先级写着太麻烦，用第一种即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct cmp1
{
	bool operator()(int x, int y)
    {
		return x > y;
	}
};
struct cmp2 
{
	bool operator()(const int x, const int y)
    {
		return x < y;
	}
};
priority_queue<int, vector<int>, cmp1> q1; 		// 小根堆
priority_queue<int, vector<int>, cmp2> q2; 		// 大根堆

5.3.2 高级数据类型（结构体）优先级

即优先队列中存储结构体类型，必须要设置优先级，即结构体的比较运算（因为优先队列的堆中要比较大小，才能将对应最大或者最小元素移到堆顶）。

优先级设置可以定义在 结构体内 进行小于号重载，也可以定义在 结构体外。

1
2
3
4
5
//要排序的结构体（存储在优先队列里面的）
struct Point
{
	int x, y;
};
  • 版本一：自定义全局比较规则
1
2
3
4
5
6
7
8
9
10
11
12
//定义的比较结构体
//注意：cmp 是个结构体 
struct cmp				//自定义堆的排序规则 		
{
	bool operator()(const Point& a,const Point& b)
    {
		return a.x < b.x;
	}
};

//初始化定义， 
priority_queue<Point, vector<Point>, cmp> q; 	// x 大的在堆顶
  • 版本二：直接在结构体里面写

因为是在结构体内部自定义的规则，一旦需要比较结构体，自动调用结构体内部重载运算符规则。

结构体内部有两种方式：

方式一 ：

1
2
3
4
5
6
7
8
struct node
{
	int x, y;
	friend bool operator < (Point a, Point b)				//为两个结构体参数，结构体调用一定要写上 friend
    {
		return a.x < b.x;								  //按 x 从小到大排，x 大的在堆顶
	}
};

方式二 ：（推荐此种）

1
2
3
4
5
6
7
8
struct node
{
    int x, y;
    bool operator < (const Point &a) const					//直接传入一个参数，不必要写 friend
    {
        return x < a.x;									  //按 x 升序排列，x 大的在堆顶
    }
};

优先队列的定义

1
priority_queue<Point> q;

注意： 优先队列自定义排序规则和 sort() 函数定义 cmp 函数很相似，但是最后返回的情况是 相反 的。即相同的符号，最后定义的排列顺序是完全相反的。所以只需要记住 sort 的排序规则和优先队列的排序规则是相反的就可以了。

当理解了堆的原理就会发现，堆调整时比较顺序是孩子和父亲节点进行比较，如果是 > ，那么孩子节点要大于父亲节点，堆顶自然是最小值。

5.4 存储特殊类型的优先级

5.4.1 存储 pair 类型

大根堆存储 pair 类型的默认排序规则（降序排序：first ↓，second ↓）：

  1. 先按 first 降序排列（大的排在前面）；
  2. 如果 first 相等，再按 second 降序排列（也是大的排在前面）。

头文件 #include <utility> // 使用 std:: pair

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <utility>  // 使用 std:: pair
#include <queue>    // 使用 std:: priority_queue
using namespace std;
int main()
{
    priority_queue<pair<int, int> >q;
    q.push({ 7, 8 });
    q.push({ 7, 9 });
    q.push(make_pair(8, 7));

    while (!q.empty())
    {
        cout << q.top().first << " " << q.top().second << "\n";
        q.pop();
    }
    return 0;
}

结果：
8 7
7 9
7 8

小根堆则恰恰相反，我们只需要记住：

  • 大根堆（默认）：pair 默认比较结果反过来用 → first ↓，second ↓。
  • 小根堆（加 greater）：pair 默认比较结果直接用 → first ↑，second ↑。

6. map

6.1 介绍

6.1.1 简介

映射类似于函数的对应关系，每个 x 对应一个 y，而 map 是每个键对应一个值。这和 python 的字典类型非常相似。容器中的每个存储对为一个键值对，包含两个元素（键和值）。

6.1.2 初始化

1
2
3
4
//初始化定义
map<string, string> mp;
map<string, int> mp;
map<int, node> mp;			//node 是结构体类型

map 特性：map 会按照键的顺序从小到大自动排序，键的类型必须可以比较大小。

6.2 函数方法

6.2.1 函数方法

代码含义复杂度
mp.find(key)返回键为 key 的映射的迭代器 注意：用 find 函数来定位数据出现位置，它返回一个迭代器。当数据存在时，返回数据所在位置的迭代器，数据不存在时，返回 mp.end()mp.end()O(logN)
mp.erase(it)删除迭代器对应的键和值O(logN)
mp.erase(key)根据映射的键删除键和值O(logN)
mp.erase(first,last)删除左闭右开区间迭代器对应的键和值O(last-first)
mp.size()返回映射的对数O(1)
mp.clear()清空 map 中的所有元素O(N)
mp.insert()插入元素，插入时要构造键值对O(N)
mp.empty()如果 map 为空，返回 true，否则返回 falseO(1)
mp.begin()返回指向 map 第一个元素的迭代器（地址）O(1)
mp.end()返回指向 map 尾部的迭代器（最后一个元素的 下一个 地址）O(1)
mp.rbegin()返回指向 map 最后一个元素的迭代器（地址）O(1)
mp.rend()返回指向 map 第一个元素前面(上一个）的逆向迭代器（地址）O(1)
mp.count(key)查看元素是否存在，因为 map 中键是唯一的，所以存在返回 1，不存在返回 0O(logN)
mp.lower_bound()返回一个迭代器，指向键值 >= key 的第一个元素
mp.upper_bound()返回一个迭代器，指向键值 > key 的第一个元素

6.2.2 注意情况

下面说明部分函数方法的注意点

查找元素是否存在时，可以使用 ① mp.find() ② mp.count() ③ mp[key]，但是第三种情况，如果不存在对应的 key 时，会自动创建一个键值对（产生一个额外的键值对空间），所以为了不增加额外的空间负担，最好使用前两种方法。

6.2.3 迭代器进行正反向遍历

  • mp.begin() 和 mp.end() 用法：

用于正向遍历 map

1
2
3
4
5
6
7
8
9
10
map<int,int> mp;
mp[1] = 2;
mp[2] = 3;
mp[3] = 4;
auto it = mp.begin();
while(it != mp.end())
{
	cout << it->first << " " << it->second << "\n";
	it ++;
}

示例结果：

1
2
3
1 2
2 3
3 4
  • mp.rbegin() 和 mp.rend()

用于逆向遍历 map

1
2
3
4
5
6
7
8
9
10
map<int,int> mp;
mp[1] = 2;
mp[2] = 3;
mp[3] = 4;
auto it = mp.rbegin();
while(it != mp.rend())
{
	cout << it->first << " " << it->second << "\n";
	it ++;
}

示例结果：

1
2
3
3 4
2 3
1 2

6.2.4 二分查找

二分查找 lower_bound() 和 upper_bound()。

map 的二分查找以第一个元素（即键为准），对 键 进行二分查找，返回值为 map 迭代器类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;

int main()
{
	map<int, int> m{{1, 2}, {2, 2}, {1, 2}, {8, 2}, {6, 2}};//有序
	map<int, int>::iterator it1 = m.lower_bound(2);
	cout << it1->first << "\n";//it1-> first = 2
	
	map<int, int>::iterator it2 = m.upper_bound(2);
	cout << it2->first << "\n";//it2-> first = 6
	
	return 0;
}

6.3 添加元素

1
2
//先声明
map<string, string> mp;
  • 方式一：
1
2
mp["学习"] = "看书";
mp["玩耍"] = "打游戏";
  • 方式二：插入元素构造键值对
1
mp.insert(make_pair("vegetable", "蔬菜"));
  • 方式三：
1
mp.insert(pair<string,string>("fruit","水果"));
  • 方式四:
1
mp.insert({"hahaha","wawawa"});

6.4 访问元素

6.4.1 下标访问

(大部分情况用于访问单个元素)

1
2
mp["菜哇菜"] = "强哇强";
cout << mp["菜哇菜"] << "\n";		//只是简写的一个例子，程序并不完整

6.4.2 遍历访问

  • 方式一：迭代器访问
1
2
3
4
5
6
7
8
9
10
map<string,string>::iterator it;
for(it = mp.begin(); it != mp.end(); it++)
{
	//      键                 值 
	// it 是结构体指针访问所以要用 -> 访问
	cout << it->first << " " << it->second << "\n";
	
	//*it 是结构体变量 访问要用 . 访问
	//cout <<(*it).first << " " <<(* it).second;
}
  • 方式二：智能指针访问
1
2
for(auto i : mp)
cout << i.first << " " << i.second << endl;		//键，值
  • 方式三：对指定单个元素访问
1
2
map<char,int>::iterator it = mp.find('a');
cout << it -> first << " " <<  it->second << "\n";
  • 方式四：c++17 特性才具有
1
2
3
4
5
for(auto [x, y] : mp)
{
	cout << x << " " << y << "\n";
}
//x, y 对应键和值

6.5 与 unordered_map 的比较

这里就不单开一个大目录讲 unordered_map 了，直接在 map 里面讲了。

6.5.1 内部实现原理

  • map：内部用 红黑树 实现，具有 自动排序（按键从小到大）功能。
  • unordered_map：内部用 哈希表 实现，内部元素无序杂乱。

6.5.2 效率比较

  1. map：

    • 优点：内部用红黑树实现，内部元素具有有序性，查询删除等操作复杂度为 O(logN)

    • 缺点：占用空间，红黑树里每个节点需要保存父子节点和红黑性质等信息，空间占用较大。

  2. unordered_map：

    • 优点：内部用哈希表实现，查找速度非常快（适用于大量的查询操作）。

    • 缺点：建立哈希表比较耗时。

两者方法函数基本一样，差别不大。但是需要注意：

  • 随着内部元素越来越多，两种容器的插入删除查询操作的时间都会逐渐变大，效率逐渐变低。

  • 使用 [] 查找元素时，如果元素不存在，两种容器 都是 创建一个空的元素；如果存在，会正常索引对应的值。所以如果查询过多的不存在的元素值，容器内部会创建大量的空的键值对，后续查询创建删除效率会 大大降低。

  • 查询容器内部元素的最优方法是：先判断存在与否，再索引对应值（适用于这两种容器）

    1
    2
    3
    4
    5
    6
    7
    // 以 map 为例
     map<int, int> mp;
     int x = 999999999;
     if(mp.count(x)) 			// 此处判断是否存在 x 这个键
     {
     	cout << mp[x] << "\n";   // 只有存在才会索引对应的值，避免不存在 x 时多余空元素的创建
     }

另外：

还有一种映射：multimap

键可以重复，即一个键对应多个值，如要了解，可以自行搜索。

6.5.3 自定义 hash 函数

由于 unordered_map 中的元素需要具备 hash 特性，如果语言没有自带 hash 特性的话，需要我们自定义 hash 函数，以下举一个 pair<int, int> 的 hash 函数定义的例子，hash 函数看自己怎么定义了（只要能实现 hash 功能就行）。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 使用 lambda 表达式来定义哈希函数
auto hash_pair = [](const std::pair<int, int>& p) -> std::size_t
{
    static hash<long long> hash_ll;
    return hash_ll(p.first + (static_cast<long long>(p.second) << 32));
};

// 使用 lambda 表达式作为哈希函数定义 unordered_map, 10 为桶的数量
std::unordered_map<std::pair<int, int>, int, decltype(hash_pair)> my_map(10, hash_pair);

// 调用：
my_map[{3, 5}] = 100;
cout << my_map[{3, 5}] << endl;  // 输出 100

7. set

7.1 介绍

set 容器中的元素不会重复，当插入集合中已有的元素时，并不会插入进去，而且 set 容器里的元素 自动从小到大排序。即：set 里面的元素 不重复且有序。

1
2
3
4
//头文件
#include<set>
//初始化定义
set<int> s;

7.2 函数方法

代码复杂度含义
s.begin()O(1)返回 set 容器的第一个元素的地址（迭代器）
s.end()O(1)返回 set 容器的最后一个元素的下一个地址（迭代器）
s.rbegin()O(1)返回逆序迭代器，指向容器元素最后一个位置
s.rend()O(1)返回逆序迭代器，指向容器第一个元素前面的位置
s.clear()O(N)删除 set 容器中的所有的元素, 无返回值
s.empty()O(1)判断 set 容器是否为空
s.insert(element)O(logN)插入一个元素
s.size()O(1)返回当前 set 容器中的元素个数
erase(iterator)O(logN)删除定位器 iterator 指向的值
erase(first, second）删除定位器 first 和 second 之间的值
erase(key_value)O(logN)删除键值 key_value 的值
查找
s.find(element)查找 set 中的某一元素，有则返回该元素对应的迭代器，无则返回结束迭代器
s.count(element)查找 set 中的元素出现的个数，由于 set 中元素唯一，此函数相当于查询 element 是否出现
s.lower_bound(k)O(logN)返回大于等于 k 的第一个元素的迭代器
s.upper_bound(k)O(logN)返回大于 k 的第一个元素的迭代器

7.3 元素访问

  • 迭代器访问
1
2
3
4
for(set<int>::iterator it = s.begin(); it != s.end(); it++)
{
	cout << *it << " ";
}
  • 智能指针
1
2
3
4
for(auto i : s)
{
	cout << i << endl;
}
  • 访问最后一个元素
1
2
//第一种
cout << *s.rbegin() << endl;
1
2
3
4
 //第二种
set<int>::iterator iter = s.end();
iter--;
cout << (*iter) << endl; 		//打印 2;
1
2
//第三种
cout << *(--s.end()) << endl;

7.4 重载 < 运算符

  • 基础数据类型

方式一：改变 set 排序规则，set 中默认使用 less 比较器，即从小到大排序。（常用）

1
2
set<int> s1; 						// 默认从小到大排序
set<int, greater<int> > s2; 		 // 从大到小排序

方式二：重载运算符。（很麻烦，不太常用，没必要）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//重载 < 运算符
struct cmp
{
    bool operator () (const int& u, const int& v) const
    {
       // return + 返回条件
       return u > v;
    }
};

set<int, cmp> s; 

for(int i = 1; i <= 10; i++)
{
	s.insert(i);
}
for(auto i : s)
{
	cout << i << " ";
}
// 10 9 8 7 6 5 4 3 2 1

方式三：初始化时使用匿名函数定义比较规则

1
2
3
4
5
6
7
8
9
10
11
12
13
set<int, function<bool(int, int)>> s([&](int i, int j){
    return i > j; // 从大到小
});

for(int i = 1; i <= 10; i++)
{
	s.insert(i);
}

for(auto x : s)
{
	cout << x << " ";
}
  • 高级数据类型（结构体）

直接重载结构体运算符即可，让结构体可以比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct Point
{
	int x, y;
	bool operator < (const Point &p) const
    {
		// 按照点的横坐标从小到大排序, 如果横坐标相同, 纵坐标从小到大
		if(x == p.x)
		{
			return y < p.y;
		}
		return x < p.x;
	}
};

set<Point> s;
for(int i = 1; i <= 5; i++)
{
    int x, y;
    cin >> x >> y;
    s.insert({x, y});
}	
/* 输入
5 4
5 2
3 7
3 5
4 8
*/

for(auto i : s)
{
	cout << i.x << " " << i.y << "\n";
}
/* 输出
3 5
3 7
4 8
5 2
5 4
*/

7.5 multiset

multiset ：元素可以重复，且元素有序（默认升序）。

  • 注意点一：方法函数基本和 set 一样，参考 set 即可。
  • 注意点二：进行删除操作时，要明确删除目标。（ 下面 s 为声明的 multiset 变量名）。
    • 删除多个元素：由于元素可以重复，注意使用 s.erase(val) 方法时，会删除掉所有与 val 相等的元素。
    • 删除一个元素：需要删除一个元素时，需要使用 s.erase(s.find(val)) 操作，先找到一个与 val 相等的元素迭代器，专门删除这个元素。
  • 注意点三：头文件操作为 #include<set>。
  1. unordered_set ：元素无序且只能出现一次。
  2. unordered_multiset ：元素无序可以出现多次。
操作示例说明
插入元素ms.insert(5);O(log n)
删除单个元素（只删一个）ms.erase(ms.find(5));只删一个 5
删除所有某值元素ms.erase(5);删除所有等于 5 的元素
计数某值出现次数ms.count(5);返回值为 size_t
查找元素ms.find(5);返回迭代器，找不到返回 ms.end()
最小值*ms.begin()第一个元素
最大值*ms.rbegin()最后一个元素（反向迭代器）
判断是否为空ms.empty()是否无元素
获取元素个数ms.size()总元素数（含重复）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <set>                  // 包含 multiset 所在头文件
using namespace std;

int main()
{
    multiset<int> ms;           // 声明一个默认升序的 multiset <int>
    // multiset <int, greater<int> > ms;  	// 声明一个降序 multiset
    ms.insert(5);
    ms.insert(3);
    ms.insert(7);
    ms.insert(5);               // 重复插入也是允许的

    for (int x : ms)
    {
        cout << x << " ";       // 遍历输出：3 5 5 7
    }

    return 0;
}
1
2
一个升序的 multiset 可以实现: 1 2 3 3 5
一个降序的 multiset 可以实现: 5 3 3 2 1

8. pair

8.1 介绍

pair 只含有两个元素，可以看作是只有两个元素的结构体。

应用：

  • 代替二元结构体
  • 作为 map 键值对进行插入（代码如下）
1
2
3
4
5
#include <utility>  // 定义 std:: pair 所在的头文件
map<string, int>mp;
mp.insert(pair<string, int>("xingmaqi", 1));
// mp.insert(make_pair("xingmaqi", 1));
// mp.insert({"xingmaqi", 1});
1
2
3
4
5
6
7
8
9
10
11
//头文件
#include<utility>

//1.初始化定义
pair<string, int> p("wangyaqi", 1);				  //带初始值的
pair<string, int> p;							//不带初始值的

//2.赋值
p = {"wang", 18};
p = make_pair("wang", 18);
p = pair<string, int>("wang", 18);

8.2 访问

1
2
3
4
5
6
7
//定义结构体数组
pair<int,int> p[20];
for(int i = 0; i < 20; i++)
{
	//和结构体类似，first 代表第一个元素，second 代表第二个元素
	cout << p[i].first << " " << p[i].second;
}

9. string

9.1 介绍

string 是一个字符串类，和 char 型字符串类似。可以把 string 理解为一个字符串类型，像 int 一样可以定义。需要注意的是 string 类型结尾 不包含 /0！

9.2 初始化及定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//头文件
#include<string>

//1.
string str1; 		                //生成空字符串

//2.
string str2("123456789");           //生成 "1234456789" 的复制品 

//3.
string str3("12345", 0, 3);         //结果为 "123" ，从 0 位置开始，长度为 3

//4.
string str4("123456", 5);           //结果为 "12345" ，长度为 5

//5.
string str5(5, '2');                //结果为 "22222" , 构造 5 个字符'2'连接而成的字符串

//6.
string str6(str2, 2);               //结果为 "3456789"，截取第三个元素（2 对应第三位）到最后

简单使用

  • 访问单个字符：
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
#include<string>
using namespace std;
int main()
{
	string s = "xing ma qi!!!";
	for(int i = 0; i < s.size(); i++)
	{
		cout << s[i] << " ";
	}
	
	return 0;
}
  • string 数组使用：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include<string>
using namespace std;
int main()
{
	string s[10];
	for(int i = 1; i < 10; i++)
    {
		s[i] = "loading...  " ;
		cout << s[i] << i << "\n";
	} 
	
	return 0;
}

结果：

1
2
3
4
5
6
7
8
9
loading...  1
loading...  2
loading...  3
loading...  4
loading...  5
loading...  6
loading...  7
loading...  8
loading...  9

9.3 string 特性

  • 支持 比较 运算符
    string 字符串支持常见的比较操作符 （>,>=,<,<=,==,!=），支持 string 与 C-string 的比较（如 str < "hello"）。在使用 >,>=,<,<= 这些操作符的时候是根据“当前字符特性”将字符按 字典顺序 进行逐一的比较。字典排序靠前的字符小， 比较的顺序是从前向后比较，遇到不相等的字符就按这个位置上的两个字符的比较结果确定两个字符串的大小（前面减后面）。同时，string ("aaaa") <string(aaaaa)。

  • 支持 + 运算 符，代表拼接字符串，string 字符串可以拼接，通过 “+” 运算符进行拼接。

    1
    2
    3
    4
    string s1 = "123";
    string s2 = "456";
    string s = s1 + s2;
    cout << s;   		//123456

9.4 读入详解

读入字符串，遇空格，回车结束

1
2
string s;
cin >> s;

读入一行字符串（包括空格），遇回车结束

1
2
string s;
getline(cin, s);

注意: getline(cin, s) 会获取前一个输入的换行符，需要在前面添加读取换行符的语句。如：getchar() 或 cin.get()

错误读取：

1
2
3
4
int n;
string s;
cin >> n;
getline(cin, s); 		//此时读取相当于读取了前一个回车字符

正确读取：

1
2
3
4
5
int n;
string s;
cin >> n;
getchar(); 				//cin.get()
getline(cin, s);		//可正确读入下一行的输入

cin 与 cin.getline() 混用

cin 输入完后，回车，cin 遇到回车结束输入，但回车还在输入流中，cin 并不会清除，导致 getline() 读取回车，结束。
需要在 cin 后面加 cin.ignore()；主动删除输入流中的换行符。（不常用）

cin 和 cout 解锁（关闭同步流）

代码（写在 main 函数开头）：

1
2
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);

为什么要进行 cin 和 cout 的解锁，原因是：

在一些题目中，读入的 数据量很大，往往超过了 1e5（105）的数据量, 而 cin 和 cout 的读入输出的速度 很慢（是因为 cin 和 cout 为了兼容 C 语言的读入输出在性能上做了妥协），远不如 scanf 和 printf 的速度，具体原因可以搜索相关的博客进行了解。

所以 对 cin 和 cout 进行解锁使 cin 和 cout 的速度几乎接近 scanf 和 printf，避免输入输出超时。

注意：cin cout 解锁使用时，不能与 scanf、getchar、printf、cin、getline() 混用，一定要注意，会出错。

string 与 C 语言字符串（C-string）的区别

  • string：是 C++的一个类，专门实现字符串的相关操作。具有丰富的操作方法，数据类型为 string，字符串结尾没有 \0 字符。
  • C-string：C 语言中的字符串，用 char 数组实现，类型为 const char *, 字符串结尾以 \0 结尾。

一般来说 string 向 char 数组转换会出现一些问题，所以为了能够实现转换，string 有一个方法 c_str() 实现 string 向 char 数组的转换。这个在项目中还算比较常用。

1
2
string s = "xing ma qi";
char s2[] = s.c_str();

9.5 函数方法

  • 获取字符串长度
代码含义
s.size() 和 s.length()返回 string 对象的字符个数，他们执行效果相同。
s.max_size()返回 string 对象最多包含的字符数，超出会抛出 length_error 异常
s.capacity()重新分配内存之前，string 对象能包含的最大字符数
  • 插入
代码含义
s.push_back()在末尾插入
例：s.push_back('a')末尾插入一个字符 a
s.insert(pos,element)在 pos 位置插入 element
例：s.insert(s.begin(),'1')在第一个位置插入 1 字符
s.append(str)在 s 字符串结尾添加 str 字符串
例：s.append("abc")在 s 字符串末尾添加字符串“abc”
  • 删除
代码含义
erase(iterator p)删除字符串中 p 所指的字符
erase(iterator first, iterator last)删除字符串中迭代器区间 [first,last) 上所有字符
erase(pos, len)删除字符串中从索引位置 pos 开始的 len 个字符
clear()删除字符串中所有字符
  • 字符替换
代码含义
s.replace(pos,n,str)把当前字符串从索引 pos 开始的 n 个字符替换为 str
s.replace(pos,n,n1,c)把当前字符串从索引 pos 开始的 n 个字符替换为 n1 个字符 c
s.replace(it1,it2,str)把当前字符串 [it1,it2) 区间替换为 str it1 , it2 为迭代器哦
  • 大小写转换

法一：

代码含义
tolower(s[i])转换为小写
toupper(s[i])转换为大写

法二：

通过 STL 的 transform 算法配合 tolower 和 toupper 实现。
有 4 个参数，前 2 个指定要转换的容器的起止范围，第 3 个参数是结果存放容器的起始位置，第 4 个参数是一元运算。

1
2
3
string s;
transform(s.begin(),s.end(),s.begin(),::tolower);	//转换小写
transform(s.begin(),s.end(),s.begin(),::toupper);	//转换大写
  • 分割
代码含义
s.substr(pos,n)截取从 pos 索引开始的 n 个字符
  • 查找
代码含义
s.find (str, pos)在当前字符串的 pos 索引位置（默认为 0）开始，查找子串 str，返回找到的位置索引，-1 表示查找不到子串
s.find (c, pos)在当前字符串的 pos 索引位置（默认为 0）开始，查找字符 c，返回找到的位置索引，-1 表示查找不到字符
s.rfind (str, pos)在当前字符串的 pos 索引位置开始，反向查找子串 s，返回找到的位置索引，-1 表示查找不到子串
s.rfind (c,pos)在当前字符串的 pos 索引位置开始，反向查找字符 c，返回找到的位置索引，-1 表示查找不到字符
s.find_first_of (str, pos)在当前字符串的 pos 索引位置（默认为 0）开始，查找子串 s 的字符，返回找到的位置索引，-1 表示查找不到字符
s.find_first_not_of (str,pos)在当前字符串的 pos 索引位置（默认为 0）开始，查找第一个不位于子串 s 的字符，返回找到的位置索引，-1 表示查找不到字符
s.find_last_of(str, pos)在当前字符串的 pos 索引位置开始，查找最后一个位于子串 s 的字符，返回找到的位置索引，-1 表示查找不到字符
s.find_last_not_of ( str, pos)在当前字符串的 pos 索引位置开始，查找最后一个不位于子串 s 的字符，返回找到的位置索引，-1 表示查找不到子串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<string>
#include<iostream>
int main()
{
    string s("dog bird chicken bird cat");
    //字符串查找-----找到后返回首字母在字符串中的下标
    // 1. 查找一个字符串
    cout << s.find("chicken") << endl;              // 结果是：9

    // 2. 从下标为 6 开始找字符'i'，返回找到的第一个 i 的下标
    cout << s.find('i', 6) << endl;                 // 结果是：11

    // 3. 从字符串的末尾开始查找字符串，返回的还是首字母在字符串中的下标
    cout << s.rfind("chicken") << endl;             // 结果是：9

    // 4. 从字符串的末尾开始查找字符
    cout << s.rfind('i') << endl;                   // 结果是：18 因为是从末尾开始查找，所以返回第一次找到的字符

    // 5. 在该字符串中查找第一个属于字符串 s 的字符
    cout << s.find_first_of("13br98") << endl;      // 结果是：4---b

    // 6. 在该字符串中查找第一个不属于字符串 s 的字符------先匹配 dog，然后 bird 匹配不到，所以打印 4
    cout << s.find_first_not_of("hello dog 2006") << endl;      // 结果是：4
    cout << s.find_first_not_of("dog bird 2006") << endl;       // 结果是：9

    // 7. 在该字符串最后中查找第一个属于字符串 s 的字符
    cout << s.find_last_of("13r98") << endl;        // 结果是：19

    // 8. 在该字符串最后中查找第一个不属于字符串 s 的字符------先匹配 t--a---c，然后空格匹配不到，所以打印 21
    cout << s.find_last_not_of("teac") << endl;     // 结果是：21
}

std::string::npos 是一个静态常量，用来表示 “未找到” 的情况。 它的类型是 size_t，本质上就是一个无符号整数。官方定义大概是这样的：static const size_t npos = -1;，也就是说，它是 size_t 类型能表示的最大值。

  • string::npos = size_t(-1) = size_t 最大值。
  • 它专门用来表示字符串操作中的 “没找到”。
  • 推荐写法：if (pos == string::npos)。常用于：
1
2
3
4
5
>size_t pos = s.find("abc");
>if (pos == string::npos)
>{
   // 表示没找到
>}
  • string::npos ≈ 特殊的下标（无效下标）。
  • x.end() ≈ 特殊的迭代器（无效迭代器）。

它们的角色类似，都是“查找失败的标志”，但类型不同，不能混用。

为什么值等于 -1？

  • size_t 是 无符号类型（一般是 64 位机器上 unsigned long long）。
  • 把 -1 转成无符号数时，会发生“模 2^n” 的转换。
    举例：
  • 假设 size_t 是 32 位 → -1 会变成 4294967295。
  • 假设 size_t 是 64 位 → -1 会变成 18446744073709551615。

所以说 string::npos 的底层数值确实就是 -1 转成无符号整数后的结果，即“最大可能值”。

  • 排序
1
sort(s.begin(),s.end());  	//按 ASCII 码排序

10. bitset

10.1 介绍

bitset 在 bitset 头文件中，它类似数组，并且每一个元素只能是 ０ 或 １，每个元素只用 １bit 空间。

1
2
//头文件
#include <bitset>

10.2 初始化定义

初始化方法：

代码含义
bitset<n> aa 有 n 位，每位都为 0
bitset<n> a(b)a 是 unsigned long 型 u 的一个副本
bitset<n> a(s)a 是 string 对象 s 中含有的位串的副本
bitset<n> a(s, pos, n)a 是 s 中从位置 pos 开始的 n 个位的副本

注意：n 必须为常量表达式！

演示代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int main()
{
    bitset<4> bitset1;　　        //无参构造，长度为 ４，默认每一位为 0

    bitset<9> bitset2(12);　      //长度为 9，二进制保存，前面用 0 补充

    string s = "100101";
    bitset<10> bitset3(s);　　    //长度为 10，前面用 0 补充

    char s2[] = "10101";
    bitset<13> bitset4(s2);　　   //长度为 13，前面用 0 补充

    cout << bitset1 << endl;　　  //0000
    cout << bitset2 << endl;　　  //000001100
    cout << bitset3 << endl;　　  //0000100101
    cout << bitset4 << endl;　    //0000000010101
    return 0;
}

10.3 特性

bitset 可以进行 位操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bitset<4> foo(string("1001"));
bitset<4> bar(string("0011"));

cout << (foo ^= bar) << endl;       // 1010 (foo 对 bar 按位异或后赋值给 foo)

cout << (foo &= bar) << endl;       // 0001 (按位与后赋值给 foo)

cout << (foo |= bar) << endl;       // 1011 (按位或后赋值给 foo)

cout << (foo <<= 2) << endl;        // 0100 (左移 2 位，低位补 0，有自身赋值)

cout << (foo >>= 1) << endl;        // 0100 (右移 1 位，高位补 0，有自身赋值)

cout << (~bar) << endl;             // 1100 (按位取反)

cout << (bar << 1) << endl;         // 0110 (左移，不赋值)

cout << (bar >> 1) << endl;         // 0001 (右移，不赋值)

cout << (foo == bar) << endl;       // false (1001 == 0011 为 false)

cout << (foo != bar) << endl;       // true  (1001!= 0011 为 true)

cout << (foo & bar) << endl;        // 0001 (按位与，不赋值)

cout << (foo | bar) << endl;        // 1011 (按位或，不赋值)

cout << (foo ^ bar) << endl;        // 1010 (按位异或，不赋值)

访问：

1
2
3
4
5
6
//可以通过 [] 访问元素(类似数组)，注意最低位下标为 0，类似于数的二进制表示，如下：
bitset<4> f("1011"); 
for (int i = 0; i < 4; ++i)
{
    cout << f[i];		// 输出 1101
}

10.4 方法函数

代码含义
b.any()b 中是否存在置为 1 的二进制位，有 返回 true
b.none()b 中是否没有 1，没有 返回 true
b.count()b 中为 1 的个数
b.size()b 中二进制位的个数
b.test(pos)测试 b 在 pos 位置是否为 1，是 返回 true
b[pos]返回 b 在 pos 处的二进制位
b.set()把 b 中所有位都置为 1
b.set(pos)把 b 中 pos 位置置为 1
b.reset()把 b 中所有位都置为 0
b.reset(pos)把 b 中 pos 位置置为 0
b.flip()把 b 中所有二进制位取反
b.flip(pos)把 b 中 pos 位置取反
b.to_ulong()用 b 中同样的二进制位返回一个 unsigned long 值

10.5 bitset 优化

一般会使用 bitset 来优化时间复杂度，大概时间复杂度会除 64 或 32，例如没有优化的时间复杂度为 O(NM) ，使用 bitset 优化后复杂度可能就为 O(NM/64)或者 $O\left(\frac{NM}{64}\right)$。

bitset 还有开动态空间的技巧，bitset 常用在 01 背包 优化等算法中：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 动态长度 bitset 实现
const int N = 1e6 + 5;              // 开空间的上限，一般为数据范围附近的值
template <int len = 1>
void bitset_(int sz)			    // sz 即为想要开的大小
{
    if (len < sz)
    {
        bitset_<min(len * 2, N)>(sz); return;
    }

    bitset<len + 1> dp;
    // 具体算法的实现
}

11. array

11.1 介绍

头文件 #include <array>。array 是 C++11 新增的容器，效率与普通数据相差无几，比 vector 效率要高，自身添加了一些成员函数。和其它容器不同，array 容器的大小是 固定 的，无法动态的扩展或收缩，只允许访问或者替换存储的元素。

注意： array 的使用要在 std 命名空间里。

11.2 声明与初始化

基础数据类型

声明一个大小为 100 的 int 型数组，元素的值不确定：

1
array<int, 100> a;

声明一个大小为 100 的 int 型数组，初始值均为 0(初始值与默认元素类型等效)：

1
array<int, 100> a{};

声明一个大小为 100 的 int 型数组，初始化部分值，其余全部为 0：

1
array<int, 100> a{1, 2, 3};

或者可以用等号

1
array<int, 100> a = {1, 2, 3};

高级数据类型

不同于数组的是对元素类型不做要求，可以套结构体：

1
2
array<string, 2> s = {"ha", string("haha")};
array<node, 2> a;

11.3 存取元素

  • 修改元素
1
2
array<int, 4> a = {1, 2, 3, 4};
a[0] = 4;
  • 访问元素

下标访问：

1
2
3
4
5
array<int, 4> a = {1, 2, 3, 4};
for(int i = 0; i < 4; i++) 
{
	cout << a[i] << " \n"[i == 3];
}

利用 auto 访问：

1
2
3
4
for(auto i : a)
{
	cout << i << " ";
}

迭代器访问：

1
2
3
4
5
auto it = a.begin();
for(; it != a.end(); it++) 
{
	cout << *it << " ";
}

at() 函数访问： 下标为 1 的元素加上下标为 2 的元素，答案为 5

1
2
3
array<int, 4> a = {1, 2, 3, 4};
int res = a.at(1) + a.at(2);
cout << res << "\n";

get 方法访问： 将 a 数组下标为 1 位置处的值改为 x。注意：获取的下标只能写数字，不能填变量！

1
get<1>(a) = x;

11.4 成员函数

成员函数功能
begin()返回容器中第一个元素的访问迭代器（地址）
end()返回容器最后一个元素之后一个位置的访问迭代器（地址）
rbegin()返回最后一个元素的访问迭代器（地址）
rend()返回第一个元素之前一个位置的访问迭代器（地址）
size()返回容器中元素的数量，其值等于初始化 array 类的第二个模板参数 N
max_size()返回容器可容纳元素的最大数量，其值始终等于初始化 array 类的第二个模板参数 N
empty()判断容器是否为空
at(n)返回容器中 n 位置处元素的引用，函数会自动检查 n 是否在有效的范围内，如果不是则抛出 out_of_range 异常
front()返回容器中第一个元素的直接引用，函数不适用于空的 array 容器
back()返回容器中最后一个元素的直接引用，函数不适用于空的 array 容器。
data()返回一个指向容器首个元素的指针。利用该指针，可实现复制容器中所有元素等类似功能
fill(x)将 x 这个值赋值给容器中的每个元素, 相当于初始化
array1.swap(array2)交换 array1 和 array2 容器中的所有元素，但前提是它们具有相同的长度和类型

11.5 部分用法示例

data()：指向底层元素存储的指针。对于非空容器，返回的指针与首元素地址比较相等。

at()

下标为 1 的元素加上下标为 2 的元素，答案为 5

1
2
3
array<int, 4> a = {1, 2, 3, 4};
int res = a.at(1) + a.at(2);
cout << res << "\n";

fill()

array 的 fill() 函数，将 a 数组全部元素值变为 x

1
a.fill(x);

另外还有其它的 fill() 函数: 将 a 数组 [begin, end) 全部值变为 x

1
fill(a.begin(), a.end(), x);

get 方法获取元素值

将 a 数组下标为 1 位置处的值改为 x，注意: 获取的下标只能写数字，不能填变量

1
get<1>(a) = x;

排序

1
sort(a.begin(), a.end());

12. tuple

12.1 介绍

tuple 模板是 pair 的泛化，可以封装不同类型任意数量的对象。可以把 tuple 理解为 pair 的扩展，tuple 可以声明二元组，也可以声明三元组。tuple 可以等价为 结构体 使用。

头文件

1
#include <tuple>

12.2 声明初始化

声明一个空的 tuple 三元组：

1
tuple<int, int, string> t1;

赋值：

1
t1 = make_tuple(1, 1, "hahaha");

创建的同时初始化：

1
tuple<int, int, int, int> t2(1, 2, 3, 4);

可以使用 pair 对象构造 tuple 对象，但 tuple 对象必须是两个元素：

1
2
auto p = make_pair("wang", 1);
tuple<string, int> t3 {p}; 		//将 pair 对象赋给 tuple 对象

12.3 元素操作

获取 tuple 对象 t 的第一个元素：

1
int first = get<0>(t);

修改 tuple 对象 t 的第一个元素：

1
get<0>(t) = 1;

12.4 函数操作

  • 获取元素个数
1
2
tuple<int, int, int> t(1, 2, 3);
cout << tuple_size<decltype(t)>::value << "\n"; // 3
  • 获取对应元素的值

通过 get<n>(obj) 方法获取, n 必须为数字不能是变量

1
2
3
4
tuple<int, int, int> t(1, 2, 3);
cout << get<0>(t) << '\n'; // 1
cout << get<1>(t) << '\n'; // 2
cout << get<2>(t) << '\n'; // 3
  • 通过 tie 解包 获取元素值

tie 可以让 tuple 变量中的三个值依次赋到 tie 中的三个变量中

1
2
3
4
5
int one, three;
string two; 
tuple<int, string, int> t(1, "hahaha", 3);
tie(one, two, three) = t;
cout << one << two << three << "\n"; 		// 1hahaha3

STL 函数

sort —— 排序

时间复杂度： O(N logN)

作用：对一个序列进行排序

1
2
3
//原型：
sort(beg, end);
sort(beg, end, cmp);

几种排序的常见操作：

  • 操作一：对数组正常升序排序
1
2
3
4
5
6
int a[N]; // 普通数组定义
// 对 a 数组的 [1, n] 位置进行从小到大排序
sort(a + 1, a + 1 + n);

vector<int> b(n + 1); // vector 数组定义
sort(b.begin() + 1, b.end());
  • 操作二：使用第三个参数，进行降序排序
1
2
3
4
5
6
7
8
//对 a 数组的 [0, n-1] 位置从大到小排序
sort(a, a + n, greater<int>());
//对 a 数组的 [0, n-1] 位置从小到大排序
sort(a, a + n, less<int>());

vector<int> b(n + 1);
sort(b.begin() + 1, b.end()); // 升序
sort(b.begin() + 1, b.end(), greater<int>()); // 降序
  • 操作三：另外一种降序排序方法，针对 vector
1
2
vector<int> a(n);
sort(a.rbegin(), a.rend()); // 使用反向迭代器进行降序排序
  • 操作四：自定义排序规则
1
2
3
4
5
6
7
8
9
10
11
12
// 1. 使用函数自定义排序，定义比较函数
bool cmp(node a, node b)
{
    //按结构体里面的 x 值降序排列
    return a.x > b.x;
}
sort(node, node + n, cmp); 	// 只能接受以函数为形式的自定义排序规则，无法接受以结构体为形式的自定义排序规则

// 2. 或者使用匿名函数自定义排序规则
sort(node, node + n, [](node a, node b) {
    return a.x > b.x;
});

stable_sort

复杂度： O(N logN)

功能和 sort() 基本一样，区别在于 stable_sort() 能够保证相等元素的相对位置，排序时不会改变相等元素的相对位置。

使用用法和 sort() 一样，见上。

is_sorted

复杂度： O(N)

判断序列是否有序（升序），返回 bool 值

1
2
3
4
5
//如果序列有序，输出 YES
if(is_sorted(a, a + n))
{
	cout << "YES\n";
}

iota

1
iota(beg, end, start)

让序列递增赋值

1
2
3
4
5
6
7
vector<int> a(10);
iota(a.begin(), a.end(), 0);
for(auto i : a)
{
	cout << i << " ";
}
// 0 1 2 3 4 5 6 7 8 9

partial_sort

1
partial_sort(beg, mid, end)

时间复杂度： 大概 O(N logM) ，其中 M 为距离

部分排序, 排序 mid-beg 个元素，mid 为要排序区间元素的尾后的一个位置

从 beg 到 mid 前 的元素都排好序

对 a 数组前 5 个元素排序按从小到大排序

1
2
3
4
5
6
7
8
9
int a[] = {1,2,5,4,7,9,8,10,6,3};
partial_sort(a, a + 5, a + 10);

for(int i = 0; i < 10; i++)
{
	cout << a[i] << ' ';
}
//1 2 3 4 5 9 8 10 7 6
//前五个元素都有序

也可以添加自定义排序规则：

partial_sort(beg,mid,end,cmp)

对 a 的前五个元素都是降序排列

1
2
3
4
5
6
7
8
9
int a[] = {1,2,5,4,7,9,8,10,6,3};
partial_sort(a, a + 5, a + 10, greater<int>());

for(int i = 0; i < 10; i++) 
{
	cout << a[i] << ' ';
}
//10 9 8 7 6 1 2 4 5 3
//前五个元素降序有序

max + min —— 找最值

时间复杂度： O(1)

找多个元素的最大值和最小值

1
2
3
//找 a，b 的最大值和最小值
mx = max(a, b);
mn = min(a, b);
1
2
3
//找到 a, b, c, d 的最大值和最小值
mx = max({a, b, c, d});
mn = min({a, b, c, d});

max_element + min_element —— 找最值

复杂度： O(N)

找最大最小值，头文件：#include <algorithm>。

1
2
3
4
5
6
7
//函数都是返回地址，需要加*解引用取值
int mx = *max_element(a, a + n);
int mn = *min_element(a, a + n);

vector<int> A(n);
int maxval = *max_element(A.begin(), A.end());  // 数组最大值
int minval = *min_element(A.begin(), A.end());  // 数组最小值

nth_element —— 寻找第 n 小的值

1
nth_element(beg, nth, end)

复杂度： 平均 O(N)

寻找第序列第 n 小的值

nth 为一个迭代器，指向序列中的一个元素。第 n 小的值恰好在 nth 位置上。

执行 nth_element() 之后，序列中的元素会围绕 nth 进行划分：nth 之前的元素都小于等于它，而之后的元素都大于等于它

实例：求序列中的第 3 小的元素

1
2
nth_element(a, a + 2, a + n);
cout << a[2] << '\n';

minmax

复杂度： O(1)

返回一个 pair 类型，第一个元素是 min(a, b)， 第二个元素是 max(a, b)

1
2
pair<int, int> t = minmax(4, 2);
// t.first = 2, t.second = 4

minmax_element

1
minmax_element(beg, end)

复杂度： O(N)

返回序列中的最小和最大值组成 pair 的对应的地址，返回类型为 pair<vector<int>::iterator, vector<int>::iterator>

1
2
3
4
5
int n = 10;
vector<int> a(n);
iota(a.begin(), a.end(), 1);
auto t = minmax_element(a.begin(), a.end()); // 返回的是最小值和最大值对应的地址
// *t.first = 1, * t.second = 10 输出对应最小最大值时需要使用指针

to_string —— 将数字转化成字符串

将数字转化为字符串，支持小数（double）

1
2
int a = 12345678;
cout << to_string(a) << '\n';

lower_bound + upper_bound —— 二分查找

复杂度： O(logN)

作用：二分查找

注意：用 * 解引用之后是取出来的是值，减去 begin() 得到的是下标！

  • 三个参数：(起始位置, 结束位置, 目标值)。
  • 范围：左闭右开 [start, end)。
  • 返回值：成功返回有效迭代器/指针，失败返回 end。
  • 前提：数据必须有序！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//如果未找到，返回尾地址的下一个位置的地址
lower_bound(起始迭代器 / 指针, 结束迭代器 / 指针, 目标值);
upper_bound(起始迭代器 / 指针, 结束迭代器 / 指针, 目标值);
lower_bound(a, a + n, x);        //在 a 数组中查找第一个大于等于 x 的元素，返回该元素的地址
upper_bound(a, a + n, x);        //在 a 数组中查找第一个大于 x 的元素，返回该元素的地址

#include <iostream>
#include <vector>
#include <algorithm>             // 包含 lower_bound 和 upper_bound
using namespace std;
int main()
{
    int a[] = { 1, 3, 3, 5, 7, 9, 9, 9, 11 };
    int n = sizeof(a) / sizeof(a[0]);

    // 示例 1：使用 lower_bound 查找第一个 >= 3 的元素
    int x = 3;
    auto it1 = lower_bound(a, a + n, x);
    if (it1 != a + n)
    {
        int index = it1 - a;        // 计算下标
        cout << "第一个大于等于 " << x << " 的元素是 a[" << index << "] = " << *it1 << endl;
        // 第一个大于等于 3 的元素是 a [1] = 3
    }
    else
    {
        cout << "没有找到大于等于 " << x << " 的元素" << endl;
    }

    // 示例 2：使用 upper_bound 查找第一个 > 3 的元素
    auto it2 = upper_bound(a, a + n, x);
    if (it2 != a + n)
    {
        int index = it2 - a;
        cout << "第一个大于 " << x << " 的元素是 a[" << index << "] = " << *it2 << endl;
        // 第一个大于 3 的元素是 a [3] = 5
    }
    else
    {
        cout << "没有找到大于 " << x << " 的元素" << endl;
    }

    // 示例 3：查找不存在的元素
    x = 8;
    auto it3 = lower_bound(a, a + n, x);
    if (it3 != a + n)
    {
        int index = it3 - a;
        cout << "第一个大于等于 " << x << " 的元素是 a[" << index << "] = " << *it3 << endl;
        // 第一个大于等于 8 的元素是 a [5] = 9
    }
    else
    {
        cout << "没有找到大于等于 " << x << " 的元素" << endl;
    }

    // 示例 4：统计某个值出现的次数
    x = 9;
    auto left = lower_bound(a, a + n, x);
    auto right = upper_bound(a, a + n, x);
    cout << x << " 出现的次数: " << right - left << endl;
    // 9 出现的次数: 3

    // 示例 5：在 vector 中使用
    vector<int> v = { 2, 4, 4, 6, 8, 10 };
    auto itv = lower_bound(v.begin(), v.end(), 5);
    if (itv != v.end())
    {
        int index = itv - v.begin();
        cout << "vector 中第一个大于等于 5 的元素是 v[" << index << "] = " << *itv << endl;
        // vector 中第一个大于等于 5 的元素是 v [3] = 6
    }

    return 0;
}

atoi —— 将字符串转整型

将字符串转换为 int 类型

注意参数为 char 型数组，如果需要将 string 类型转换为 int 类型，可以使用 stoi 函数（参考下文），或者将 string 类型转换为 const char * 类型。

关于输出数字的范围：

  • atoi 不做 范围检查，如果超出上界，输出上界，超出下界，输出下界。
  • stoi 会做 范围检查，默认必须在 int 范围内，如果超出范围，会出现 RE（Runtime Error）错误。
1
2
3
string s = "1234";
int a = atoi(s.c_str());
cout << a << "\n"; // 1234

或者

1
2
3
char s[] = "1234";
int a = atoi(s);
cout << a << "\n";

stoi / stoll / stod / … —— 将字符串转整型（更常用）

将对应 string 类型字符串转换为数字（int 型），记忆：s -> t 分别对应两个数据类型的某个字母

注意参数为 string 字符串类型。

如果要转换为其他类型的数字可使用 stoll（转换为 long long） ， stoull（转换为 unsigned long long），stod（转换为 double） 等函数。

关于输出数字的范围：

  • stoi 会做 范围检查，默认必须在 int 范围内，如果超出范围，会出现 RE（Runtime Error）错误。

  • atoi 不做 范围检查，如果超出上界，输出上界，超出下界，输出下界。

1
2
3
string s = "1234";
int a = stoi(s);
cout << a << "\n"; // 1234

reverse —— 翻转

时间复杂度： O(N)

对序列进行前后翻转，包含在头文件 #include <algorithm> 中！

[!NOTE]

reverse 函数在解决回文串相关问题格外好用

1
2
3
4
5
6
7
8
string s = "abcde";
reverse(s.begin(), s.end());//对 s 进行翻转
cout << s << '\n';//edcba

//对 a 数组进行翻转
int a[] = {1, 2, 3, 4};
reverse(a, a + 4);
cout << a[0] << a[1] << a[2] << a[3];//4321

getline + istringstream —— 读取一行/对字符串流进行分割

时间复杂度： O(n)，头文件：<string> (getline)，<sstream>（istringstream）

读取一行（包括空格），搭配 istringstream 实现分割处理

  • getline(输入流, 变量); → 读取整行
  • istringstream(字符串变量); → 把字符串当作输入流
  • getline(字符串流, 变量, 分隔符); → 按分隔符拆分数据
  • while(字符串流 >> 变量) → 按空格拆分数据

istringstream 用于把字符串当作输入流；getline 用于按分隔符拆分数据；while 循环用于按空格拆分数据。

快速记忆：getline(字符串流, 变量, 分隔符); → getline 用于读取一整行包括空格，默认（指定分割符）直到遇到换行符（换行符会被丢弃，不存入变量）才结束。如果指定了分隔符，则会读取到 分隔符 为止（即分隔符的前一个位置，分隔符也会被丢弃，不存入变量），读取的部分会被存储在指定的变量中，而分隔符本身不会被包含在结果中。然后，剩余的部分（分隔符后的字符）会留在输入流中，为下一次读取做准备。下一次调用 getline 会继续从流中读取，直到遇到下一个分隔符或者行结束为止。这个过程会一直继续，直到所有需要的数据都被提取出来。

[!IMPORTANT]

cin 不能读取换行/回车，所以如果在 getline 之前使用了 cin（ 混合输入），那么 getline 实际读取到的是换行/回车，就无法正确读入数据，很多时候就是因为这个原因导致程序出错！常用解决方法：当使用了这样的混合输入必须要在 cin 和 getline 之间写上 getchar(); 或者 cin.ignore(); 来清除输入缓冲区中的换行符！ 例子：

1
2
3
4
5
6
7
8
int n;
cin >> n;
// 清除输入缓冲区中的换行符（任选其一）
// getchar();
cin.ignore();

string s;
getline(cin, s);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <string>                   // 包含 getline
#include <sstream>                  // 包含 stringstream
using namespace std;

int main()
{
    // 示例 1：输入 "YYYY-MM-DD"，输出 "YYYY/MM/DD"
    string year, month, day;
    getline(cin, year, '-');        // 读取到第一个 '-' 为止
    getline(cin, month, '-');       // 继续读取到下一个 '-'
    getline(cin, day);              // 读取剩余部分（默认到行尾）
    cout << year << "/" << month << "/" << day << endl;

    // 示例 2：按空格拆分 "42 3.14 hello"
    string data = "42 3.14 hello";
    istringstream iss(data);        // 将字符串转为流
    int num;
    double pi;
    string word;
    iss >> num >> pi >> word;       // 按空格提取
    cout << num << " " << pi << " " << word << endl;    // 输出: 42 3.14 hello

    // 示例 3：按逗号拆分 CSV 数据 "apple, orange, banana"
    string csv = "apple,orange,banana";
    istringstream iss_csv(csv);
    string fruit;
    while (getline(iss_csv, fruit, ','))
    {
        cout << fruit << " ";       // 输出: apple orange banana
    }
    cout << endl;

    // 示例 4：逐行处理输入（如文件或控制台）
    string line;
    while (getline(cin, line))      // 每次读取一行
    {  
        istringstream ss(line);
        string token;
        while (ss >> token)
        {     
            cout << token << " ";   // 按空格拆分每行
        }
        cout << endl;
    }

    return 0;
}

set_union, set_intersection, set_difference —— 交并差集

复杂度： O(N+M)

求两个集合的并集，交集，差集。手动实现双指针就可以搞定，嫌麻烦可以使用该函数

函数作用说明
set_union并集两个集合所有元素（去重）
set_intersection交集两个集合共同的元素
set_difference差集第一个集合有而第二个集合没有的元素

注意：

  • 必须有序（sorted），但不强制升序或降序。
  • 只要两个输入区间是按照相同的排序规则（比如都是升序、或者都是降序）排好的，就可以正常使用。

两个集合 必须为有序集合，所以下面演示代码使用了排序。vector 容器可以替换成 set 容器，因为 set 自动会对元素进行排序。函数的参数有五个，前两个为第一个容器的首尾迭代器，第三四个为第二个容器的首尾迭代器，最后一个为插入位置，即将结果插入到哪个地址之后。

1
2
3
4
#include <algorithm>		// 头文件
set_union(起始迭代器1, 结束迭代器1, 起始迭代器2, 结束迭代器2, 输出迭代器);
set_intersection(起始迭代器1, 结束迭代器1, 起始迭代器2, 结束迭代器2, 输出迭代器);
set_difference(起始迭代器1, 结束迭代器1, 起始迭代器2, 结束迭代器2, 输出迭代器);
1
2
3
4
5
6
7
8
9
10
vector<int> a = {4, 5, 2, 1, 8}, b = {5, 3, 8, 9, 2};
sort(a.begin(), a.end()); // 1 2 4 5 8
sort(b.begin(), b.end()); // 2 3 5 8 9
vector<int> c, d, e;
// a 并 b：1 2 3 4 5 8 9
set_union(a.begin(), a.end(), b.begin(), b.end(), inserter(c, c.begin()));
// a 交 b：2 5 8
set_intersection(a.begin(), a.end(), b.begin(), b.end(), inserter(d, d.begin()));
// a 差 b： 1 4
set_difference(a.begin(), a.end(), b.begin(), b.end(), inserter(e, e.begin()));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <vector>
#include <algorithm>                    // 包含 set_union、set_intersection、set_difference
using namespace std;

int main()
{
    vector<int> a = { 1, 3, 5 };
    vector<int> b = { 2, 3, 6 };
    vector<int> Intersection(10);       // 交集，预留足够空间
    vector<int> Union(10);              // 并集，预留足够空间
    vector<int> Difference(10);         // 差集，预留足够空间

    // 求交集
    auto it1 = set_intersection(a.begin(), a.end(), b.begin(), b.end(), Intersection.begin());
    Intersection.resize(it1 - Intersection.begin());    // 调整交集实际大小

    // 求并集
    auto it2 = set_union(a.begin(), a.end(), b.begin(), b.end(), Union.begin());
    Union.resize(it2 - Union.begin());                  // 调整并集实际大小

    // 求差集
    auto it3 = set_difference(a.begin(), a.end(), b.begin(), b.end(), Difference.begin());
    Difference.resize(it3 - Difference.begin());        // 调整差集实际大小

    // 输出交集
    for (int num : Intersection)
    {
        cout << num << " ";  // 输出交集元素 3
    }
    cout << endl;

    // 输出并集
    for (int num : Union)
    {
        cout << num << " ";  // 输出并集元素 1 2 3 5 6
    }
    cout << endl;

    // 输出差集
    for (int num : Difference)
    {
        cout << num << " ";  // 输出差集元素 1 5
    }
    cout << endl;

    return 0;
}

back_inserter

back_inserter(容器名) 是一个 生成输出迭代器的小工具，帮你 自动在容器尾部插入元素。平常如果不用 back_inserter，你需要预先分配好大空间，还要 resize，很麻烦。 而用 back_inserter 就可以：

  • 不需要提前开空间！
  • 自动 push_back 加元素！

1. 传统写法（需要开大空间）

1
2
3
vector<int> result(100);  // 必须提前开好足够空间
auto it = set_union(a.begin(), a.end(), b.begin(), b.end(), result.begin());
result.resize(it - result.begin());  // 最后再调整大小

2. 使用 back_inserter（最推荐）

1
2
3
vector<int> result;  // 不需要开空间，空的就行
set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));
// 不需要 resize，直接用 result 即可

看到了吗？back_inserter 自动帮你扩容，代码更简洁、安全，强烈推荐使用！

isdigit、isalpha —— 判断是否是数字/字符

处于标准库函数（头文件 <cctype>）。正常来说下面前 4 个是较为常用的，记不住也没关系，大多数情况也还是手动实现的

函数名作用示例输入示例输出
isdigit(c)判断是否为数字（0~9）'5'true
isalpha(c)判断是否为字母（A-Z 或 a-z）'a' / 'Z'true
islower(c)判断是否为小写字母'g'true
isupper(c)判断是否为大写字母'G'true
isalnum(c)判断是否为字母或数字'a', '9'true
isspace(c)判断是否为空白字符（空格、\t、\n）' 'true
isxdigit(c)判断是否为十六进制数字（0 9, A F, a~f）'F'true
isprint(c)判断是否为可打印字符'!'true
ispunct(c)判断是否为标点符号'!', ','true
isgraph(c)是否为可见字符（不含空格）'A', '%'true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool my_isdigit(char c)
{
    return c >= '0' && c <= '9';            // 判断是否为数字字符（ASCII: 48~57）
}

bool my_isalpha(char c)
{
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');    // 判断是否为字母（大写或小写，ASCII: a~z: 97~122, A~Z: 65~90）
}

bool my_islower(char c)
{
    return c >= 'a' && c <= 'z';            // 判断是否为小写字母
}

bool my_isupper(char c)
{
    return c >= 'A' && c <= 'Z';            // 判断是否为大写字母
}

gcd —— 最大公约数，lcm —— 最小公倍数

名称所属是否标准头文件支持类型特点说明
std::gcdC++17 标准库✅ 是<numeric>int、long long 等整数类型安全，支持 constexpr，推荐使用于现代 C++
std::lcmC++17 标准库✅ 是<numeric>int、long long 等整数求最小公倍数，现代推荐方式
__gcdGNU 扩展❌ 否<algorithm>原始定义只明确支持 int 类型，后续做了处理，可以接受 long、long long 等整型参数，但仍有部分编译器不支持！GCC 特有，非标准函数，竞赛中常用

C++17 引入，头文件：#include <numeric>

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <numeric>
using namespace std;

int main()
{
	int a = 24, b = 12;
	cout << gcd(a, b) << endl;		// 输出 12
	cout << lcm(a, b) << endl;		// 输出 24

	return 0;
}
1
2
3
4
5
6
7
8
9
10
// 如果环境不支持，可以手动实现其两者功能：
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b)
{
    return (a * b) / gcd(a, b);
}

__gcd —— 最大公约数

求 a 和 b 的最大公约数，使用时要包含 <algorithm> 头文件。准确的来说它是一个 GNU 扩展，不属于 STL。

__gcd(12,15) = 3

__gcd(21,0) = 21

__lg

  1. 求一个数二进制下最高位位于第几位（从 第 0 位 开始）（或二进制数下有几位）
  2. __lg(x) 相当于返回 $log_2 x$
  3. 复杂度 O(1)

__lg(8) = 3

__lg(15) = 3

accumulate —— 序列求和

1
accumulate(beg, end, init)

复杂度： O(N)

作用：对一个序列的元素求和

init 为对序列元素求和的 初始值

返回值类型：与 init 相同

  • 基础累加求和：
1
2
3
4
5
6
7
int a[]={1, 3, 5, 9, 10};

//对 [0,2] 区间求和，初始值为 0，结果为 0 + 1 + 3 + 5 = 9
int res1 = accumulate(a, a + 3, 0);

//对 [0,3] 区间求和，初始值为 5，结果为 5 + 1 + 3 + 5 + 9 = 23
int res2 = accumulate(a, a + 4, 5);
  • 自定义二元对象求和：

使用 lambda 表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef long long ll;
struct node
{
    ll num;
} st[10];

for(int i = 1; i <= n; i++)
{
	st[i].num = i + 10000000000;
}

//返回值类型与 init 一致，同时注意参数类型（a）也要一样
//初始值为 1，累加 1+10000000001+10000000002+10000000003 = 30000000007
ll res = accumulate(st + 1, st + 4, 1ll, [](ll a,node b) {
    return a + b.num;
})

ceil —— 向上取整

头文件：<cmath>/<math.h>。

ceil 函数的功能是返回不小于给定参数 x 的最小整数，也就是我们所说的 向上取整。

1
2
3
double ceil(double x);
float ceil(float x);                    // C++ 中新增的重载版本
long double ceil(long double x);        // C++ 中新增的重载版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cmath>                        // 包含了 ceil 函数的头文件
using namespace std;

int main()
{
    int a = 1;
    cout << ceil(a) << endl;            // 输出 1

    double b = 2.5;
    cout << ceil(b) << endl;            // 输出 3

    double c = -2.4;
    cout << ceil(c) << endl;            // 输出 -2

    long double d = 3.1415926;
    cout << ceil(d) << endl;            // 输出 4

    return 0;
}

fill

复杂度： O(N)

对一个序列进行初始化赋值

1
2
3
4
5
6
7
8
9
//对 a 数组的所有元素赋 1
int a[5];
fill(a, a + 5, 1);

for(int i = 0; i < 5; i++)
{
	cout << a[i] << " ";
}
//1 1 1 1 1

注意区分 memset：void *memset(需要填充内存的指针，填充的值，字节数);，memset() 是按 字节 进行赋值，对于初始化赋 0 或 -1 有比较好的效果。

如果赋某个特定的数会 出错，赋值特定的数建议使用 fill()。

next_permutation

1
next_permutation(beg, end)

时间复杂度： O(N)

求序列的下一个排列，下一个排列是字典序大一号的排列

返回 true 或 false

  • next_permutation(beg, end)

    如果是最后一个排列，返回 false, 否则求出下一个序列后，返回 true

1
2
//对 a 序列进行重排
next_permutation(a, a + n);

应用：求所有的排列

输出 a 的所有排列

1
2
3
4
5
6
7
8
9
// 数组 a 不一定是最小字典序序列，一定注意将它排序
sort(a, a + n);
do
{
 	for(int i = 0; i < n; i++)
 	{
 		printf("%d ", a[i]);
 	}
} while(next_permutation(a, a + n));
  • prev_permutation(beg, end)

求出前一个排列，如果序列为最小的排列，将其重排为最大的排列，返回 false。

random_shuffle

复杂度： O(N)

  1. 随机打乱序列的顺序
  2. random_shuffle 在 C++14 中被弃用，在 C++17 中被废除，C++11 之后应尽量使用 shuffle 来代替。
1
2
3
4
5
6
7
8
vector<int> b(n);
iota(b.begin(), b.end(), 1);// 序列 b 递增赋值 1, 2, 3, 4,...

// 对 a 数组随机重排
random_shuffle(a, a + n);

// C++11 之后尽量使用 shuffle
shuffle(b.begin(), b.end());

transform

复杂度： O(N)

作用：使用给定操作，将结果写到 dest 中

1
2
//原型：
transform(beg, end, dest, unaryOp);

一般不怎么使用，徒增记忆负担，不如手动实现。

1
2
3
//将序列开始地址 beg 到结束地址 end 大小写转换，把结果存到起始地址为 dest 的序列中
transform(beg, end, dest, ::tolower);
transform(beg, end, dest, ::toupper);

unique

复杂度： O(N)

消除重复元素，返回消除完重复元素的下一个位置的地址

如：a[] = {1, 3, 2, 3, 6};

unique 之后 a 数组为 {1, 2, 3, 6, 3} 前面为无重复元素的数组，后面则是重复元素移到后面，返回 a[4] 位置的地址（不重复元素的尾后地址）

消除重复元素一般需要原序列是 有序序列

应用：离散化

  • 方法一：利用数组离散化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for (int i = 0; i < n; i++)
{
    cin >> a[i];
    b[i] = a[i];                    //将 a 数组复制到 b 数组
}

// 排序后 b：{1, 2, 3, 3, 6}
sort(b, b + n);                     //对 b 数组排序

// 消除重复元素 b：{1, 2, 3, 6, 3} 返回的地址为最后一个元素 3 的地址 
int len = unique(b, b + n) - b;     //消除 b 的重复元素，并获取长度

for (int i = 0; i < n; i++)
{
    //因为 b 有序，查找到的下标就是对应的 相对大小（离散化后的值）
    int pos = lower_bound(b, b + len, a[i]) - b;        //在 b 数组中二分查找第一个大于等于 a [i] 的下标
    a[i] = pos;                     // 离散化赋值
}
  • 方法二：利用 vector 进行离散化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> a(n);
for (int i = 0; i < n; ++i)
{
    cin >> a[i];
}

vector<int> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());

for (int i = 0; i < n; ++i)
{
	a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1; 	// 离散后的数据从 1 开始   
}

__builtin_ 内置位运算函数

需要注意：内置函数有相应的 unsigned lnt 和 unsigned long long 版本，unsigned long long 只需要在函数名后面加上 ll 就可以了，比如 __builtin_clzll(x) ，默认是 32 位 unsigned int

很多题目和 long long 数据类型有关，如有需要注意添加 ll

  • __builtin_ffs

二进制中对应最后一位 1 的位数，比如 4 会返回 3（100）

  • __builtin_popcount
1
__builtin_popcount(x)

x 中 1 的个数

  • __builtin_ctz

x 末尾 0 的个数（count tail zero）

  • __builtin_clz

x 前导 0 的个数（count leading zero）

1
2
cout << __builtin_clz(32); // 26
//因为共有 6 位, 默认数据范围为 32 位，32 - 6 = 26
  • __builtin_parity

x 中 1 的个数的奇偶性， 奇数输出 1，偶数输出 0

C++20 ranges

ranges 主要用来简化迭代器操作，可以少写很多迭代器操作相关的代码。
ranges 集成了很多 STL 函数

1
2
3
4
ranges::sort(a); 						// sort(a.begin(), a.end());
ranges::sort(a, greater<int>()); 		 // sort(a.begin(), a.end(), greater <int>());
int mx = *ranges::max_element(a);
int mn = *ranges::min_element(a);

可参考链接：

  1. C++语法糖 https://www.luogu.com.cn/blog/AccRobin/grammar-candies