STL应用 —— 常用函数

STL应用 —— 常用函数

STL提供了一些常用函数，包含在头文件#include中

• min(x ,y)：求两个元素的最小值。
• max(x ,y)：求两个元素的最大值。
• swap(x ,y)：交换两个元素。
• find(begin,end,x)：返回指向区间[begin,end)第1个值为x的元素指针。如果没找到，则返回end。
• count(begin,end,x)：返回指向区间[begin,end)值为x 的元素数量，返回值为整数。
• reverse(begin,end)：翻转一个序列。
• random_shuffle(begin,end)：随机打乱一个序列。
• unique(begin,end)：将连续的相同元素压缩为一个元素，返回去重后的尾指针。不连续的相同元素不会被压缩，因此一般先排序后去重。
• fill(begin,end,val)：将区间[begin,end)的每个元素都设置为val。
• sort(begin,end,compare)：对一个序列排序，参数begin和end表示一个范围，分别为待排序数组的首地址和尾地址；compare表示排序的比较函数，可省略，默认为升序。stable_sort (begin, end,compare)为稳定排序，即保持相等元素的相对顺序。
• nth_element(begin,begin+k,end,compare)：使区间[begin,end)第k 小的元素处在第k 个位置上，左边元素都小于或等于它，右边元素都大于或等于它，但并不保证其他元素有序。
• lower_bound(begin,end,x ) / upper_bound(begin,end,x)：两个函数都是利用二分查找的方法，在有序数组中查找第1个满足条件的元素，返回指向该元素的指针。
• next_permutation(begin,end)/pre_permutation(begin,end)：next_permutation()是求按字典序的下一个排列的函数，可以得到全排列。pre_permutation()是求按字典序的上一个排列的函数。

【fill(begin,end,val)】

• fill(begin,end,val)将区间[begin,end)的每个元素都设置为val。

与#include中的memset不同，memset是按字节填充的。例如，int占4字节，因此memset(a ,0x3f,sizeof(a ))按字节填充相当于将0x3f3f3f3f赋值给数组a []的每个元素。memset经常用来初始化一
个int型数组为0、-1，或者最大值、最小值，也可以初始化一个bool型数组为true(1)或false(0)。

不可以用memset初始化一个int型数组为1，因为memset(a,1,sizeof(a ))相当于将每个元素都赋值为0000 0001 0000 0001 0000 0001 0000 0001，即将0000 0001分别填充到4字节中。布尔数组可以赋值为true，是因为布尔数组中的每个元素都只占1字节。

memset(a , 0 , sizeof(a)); //初始化为0

memset(a , -1 , sizeof(a)); //初始化为-1

memset(a , 0x3f , sizeof(a));  //初始化为最大值 0x3f3f3f3f

memset(a , 0xcf , sizeof(a));  //初始化为最小值 0xcfcfcfcf
1
2
3
4
5
6
7

注意的是，动态数组或数组作为函数参数时，不可以用sizeof(a)测量数组空间，因为这样只能测量到首地址的空间。可以用memset(a ,0x3f,n ×sizeof(int))的方法处理，或者用fill函数填充。

如果用memset(a ,0x3f,sizeof(a))填充double类型的数组，则经常会得到一个连1都不到的小数。double类型的数组填充极值时需要用fill(a ,a +n ,0x3f3f3f3f)。

尽管0x7fffffff是32-bit int的最大值，但是一般不使用该值初始化最大值，因为0x7fffffff不能满足“无穷大加一个有穷的数依然是无穷大”，它会变成一个很小的负数。0x3f3f3f3f的十进制是1061109567，也就是10^9 级别的（和0x7fffffff在一个数量级），而一般情况下的数据都是小于10^9 的，所以它可以作为无穷大使用而不至于
出现数据大于无穷大的情形。另一方面，由于一般的数据都不会大于10^9 ，所以当把无穷大加上一个数据时，它并不会溢出（这就满足了“无穷大加一个有穷的数依然是无穷大”）。事实上，0x3f3f3f3f + 0x3f3f3f3f=2122219134，这非常大但却没有超过32-bit int的表示范围，所以0x3f3f3f3f还满足了“无穷大加无穷大还是无穷大”的需求。

【sort(begin,end,compare)】

【举个栗子：使用默认的函数排序】

#include
#include

using namespace std;

int main(){
	
	int a[10] = {7,4,5,23,2,73,41,52,28,60};
	
	sort(a , a+10);  //数组a 按升序排序
	
	for(int i = 0 ; i < 10 ; i++){
		
		cout << a[i] << " ";
		
	} 
	
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

【自定义比较函数】

sort函数默认为升序排序。自己可以编写一个比较函数来实现，接着调用含3个参数的sort(begin,end,compare)，前两个参数分别为待排序数组的首地址和尾地址，最后一个参数表示比较的类型。自定义比较函数同样适用于结构体类型，可以指定按照结构体的某个成员进行升序或降序排序。

[举个栗子]

#include
#include

using namespace std;

bool cmp(int a , int b){
	
	return a > b;
	
}

int main(){
	
	int a[10] = {7,4,5,23,2,73,41,52,28,60};
	
	sort(a , a + 10 , cmp);
	
	for(int i = 0 ; i < 10 ; i++){
		
		cout << a[i] << " ";
		
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

【利用functional 标准库】

对于任务（类型支持“<”“>”等比较运算符），完全没必要自己写一个类出来，引入头文件#include即可。functional提供了一些基于模板的比较函数对象。

• equal_to：等于。
• not_equal_to：不等于。
• greater：大于。
• greater_equal：大于或等于。
• less：小于。
• less_equal：小于或等于。
• 升序：sort(begin,end,less())。
• 降序：sort(begin,end,greater())。

[举个栗子]

#include
#include
#include

using namespace std;

int main(){
	
	int a[10] = {7,4,5,23,2,73,41,52,28,60};
	
	sort(a , a + 10 , greater<int>());  //从大到小排序
	
	for(int i = 0 ; i < 10 ; i ++){
		
		cout << a[i] << " ";
		
	} 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

【nth_element(begin,begin+k ,end,compare)】

当省略最后一个参数时，该函数使区间[begin,end)第k（k从0开始）小的元素处在第k 个位置上。当最后一个参数为greater()时，该函数使区间[begin,end)第k 大的元素处在第k 个位置上。

注意：在函数执行后会改变原序列，但不保证其他元素有序。

[举个栗子]

#include
#include
#include

using namespace std;

void print(int a[] , int n){
	
	for(int i = 0 ; i < n ; i++){
		
		cout << a[i] << " ";
		
	}
	cout << endl;
}

int main(){
	
	int a[7] = {6,2,7,4,20,15,5};
	
	nth_element(a , a + 2 , a + 7);
	
	print(a , 7);
	
	int b[7] = {6,2,7,4,20,15,5};
	
	nth_element(b , b + 2, b + 7 , greater<int>());
	
	print(b , 7);
	
	return 0;
}
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

当然是从 “0” 开始的。

lower_bound(begin,end,x)/upper_bound(begin,end,x)

lower_bound()和upper_bound()都是用二分查找的方法在一个有序数组中查找第1个满足条件的元素。

【在从小到大的排序数组中】

• lower_bound(begin,end,x)：从数组的begin位置到end-1位置二分查找第1个大于或等于x 的元素，找到后返回该元素的地址，不存在则返回end。通过返回的地址减去起始地址begin，得到元素在数组中的下标。

• upper_bound(begin,end,x)：从数组的begin位置到end-1位置二分查找第1个大于x 的元素，找到后返回该元素的地址，不存在则返回end。

【在从大到小的排序数组中】

• lower_bound(begin,end,x ,greater())：从数组的begin位置到end-1位置二分查找第1个小于或等于x 的元素，找到后返回该元素的地址，不存在则返回end。

• lower_bound(begin,end,x ,greater())：从数组的begin位置到end-1位置二分查找第1个小于或等于x 的元素，找到后返回该元素的地址，不存在则返回end。

[举个例子]

#include
#include
#include

using namespace std;

void print(int a[] , int n){
	
	for(int i = 0 ; i < n ; i++){
		
		cout << a[i] << " ";
		
	}
	cout << endl;
}

int main(){
	
	int a[6] = {6,2,7,4,20,15};
	
	sort(a , a + 6);  //从小到大排序
	
	print(a , 6);
	
	int pos1 = lower_bound(a , a + 6 , 7) - a ; //返回数组中第1个大于或等于7的元素下标
	
	int pos2 = upper_bound(a , a +6 , 7) - a;  //返回数组中第1个大于7的元素下标
	
	cout << pos1 << " " << a[pos1] << endl;
	
	cout << pos2 << " " << a[pos2] << endl;  //排完序后看
	
	sort(a , a + 6 , greater<int>()); //从大到小排序
	
	print(a , 6); 
	
	int pos3 = lower_bound(a , a + 6, 7 , greater<int>()) - a;   //返回第一个小于等于7的元素下标
	
	int pos4 = upper_bound(a , a + 6 , 7, greater<int>()) - a; //返回第一个小于7的元素下标
	
	cout << pos3 << " " << a[pos3] << endl;
	
	cout << pos4 << " " << a[pos4] << endl; 
	 
	return 0; 
} 
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

next_permutation(begin,end)/pre_permutation(begin,end)

next_permutation()是求按字典序排序的下一个排列的函数，可以得到全排列。pre_permutation()是求按字典序排序的上一个排列的函数。

【int类型的next_permutation】

[举个栗子]

#include
#include
#include

using namespace std;

int main(){
	
	int a[3];
	
	a[0] = 1;
	a[1] = 2;
	a[2] = 3;
	
	do{
		cout << a[0] << " " << a[1] << " " << a[2] << endl;
	}while(next_permutation(a , a + 3));
	
	//如果存在a之后的排列，就返回true
	//如果a是最后一个排列且没有后继，则返回false
	//每执行一次，a就变成它的后继
	
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

如果改成“while(next_permutation(a ,a +2));”

现在只对前两个元素进行字典序排序。

再改一下

这就只对1进行排序了。

若排列本来就最大且没有后继，则在next_permutation执行后，对排列进行字典升序排序，相当于循环。

[举个例子]

#include
#include
#include

using namespace std;

int main(){
	
	int list[3] = {3,2,1};
	
	next_permutation(list , list + 3);
	
	cout << list[0] << " " << list[1] << " " << list[2] << endl;
	
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

【char类型的next_permutation】

[举个栗子]

#include
#include
#include
#include

using namespace std;

int main(){
	
	char ch[205];
	
	cin >> ch;
	
	sort(ch , ch + strlen(ch)); //对输入的数组进行字典升序排序
	
	char *first = ch;
	
	char *last = ch + strlen(ch);
	
	do{
		cout << ch << endl;
	}while(next_permutation(first , last));
	
	return 0;
} 
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

【string类型的next_permutation】

[举个栗子]

#include
#include
#include
#include
#include

using namespace std;

int main(){
	
	string s;
	
	while(cin >> s && s != "#"){
		
		sort(s.begin() , s.end()); //全排列
		
		cout << s << endl;
		
		while(next_permutation(s.begin() , s.end())){
			
			cout << s << endl;
			
		} 
		
	}
	
	return 0;
} 
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

【自定义优先级的next_permutation】

[举个栗子]

#include
#include
#include
#include
#include

using namespace std;

int cmp(char a, char b){ // 自定义 A < a < B < b < ... < Z < z 
	
	if(tolower(a) != tolower(b)){
		
		return tolower(a) < tolower(b);
		
	}
	else{
		
		return a < b;	
	}
	
}

int main(){
	
	char ch[205];
	
	cin >> ch;
	
	sort(ch , ch + strlen(ch) , cmp);
	
	do{
		printf("%s\n",ch);
	}while(next_permutation(ch , ch + strlen(ch) , cmp));
	
	return 0;
} 
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