【C++】STL<algorithm>中算法总结

STL中<algorithm>文件中包含的常用函数

一、非修改性序列操作（12个）

功能	函数
循环对序列中的每个元素执行某操作	for_each()
查找在序列中找出某个值的第一次出现的位置	find()
在序列中找出符合某谓词的第一个元素	find_if()
在序列中找出一子序列的最后一次出现的位置	find_end()
在序列中找出第一次出现指定值集中之值的位置	find_first_of()
在序列中找出相邻的一对值	adjacent_find()
计数在序列中统计某个值出现的次数	count()
在序列中统计与某谓词匹配的次数	count_if()
比较找出两个序列相异的第一个元素	mismatch()
两个序列中的对应元素都相同时为真	equal()
搜索在序列中找出一子序列的第一次出现的位置	search()
在序列中找出一值的连续n次出现的位置	search_n()

二、修改性序列操作（27个）

功能	函数
复制从序列的第一个元素起进行复制	copy()
从序列的最后一个元素起进行复制	copy_backward()
交换 交换两个元素	swap()
交换指定范围的元素	swap_ranges()
交换由迭代器所指的两个元素	iter_swap()
变换将某操作应用于指定范围的每个元素	transform()
替换用一个给定值替换一些值	replace()
替换满足谓词的一些元素	replace_if()
复制序列时用一给定值替换元素	replace_copy()
复制序列时替换满足谓词的元素	replace_copy_if()
填充 用一给定值取代所有元素	fill()
用一给定值取代前n个元素	fill_n()
生成 用一操作的结果取代所有元素	generate()
用一操作的结果取代前n个元素	generate_n()
删除具有给定值的元素	remove()
删除满足谓词的元素	remove_if()
复制序列时删除具有给定值的元素	remove_copy()
复制序列时删除满足谓词的元素	remove_copy_if()
删除相邻的重复元素	unique()
复制序列时删除相邻的重复元素	unique_copy()
反转元素的次序	reverse()
复制序列时反转元素的次序	reverse_copy()
环移循环移动元素	rotate()
复制序列时循环移动元素	rotate_copy()
随机采用均匀分布来随机移动元素	random_shuffle()
划分将满足某谓词的元素都放到前面	partition()
将满足某谓词的元素都放到前面并维持原顺序	stable_partition()

三、序列排序及相关操作（27个）

功能	函数
排序	sort()
排序，并维持相同元素的原有顺序	stable_sort()
将序列的前一部分排好序	partial_sort()
复制的同时将序列的前一部分排好序	partial_sort_copy()
第n个元素 将第n个元素放到它的正确位置	nth_element()
二分检索 找到大于等于某值的第一次出现	lower_bound()
二分检索 找到大于某值的第一次出现	upper_bound()
二分检索 在有序序列中确定给定元素是否存在	binary_search()
找到（在不破坏顺序的前提下）可插入给定值的最大范围	equal_range()
归并 归并两个有序序列	merge()
归并两个接续的有序序列	inplace_merge()
有序结构上的集合操作 一序列为另一序列的子序列时为真	includes()
构造两个集合的有序并集	set_union()
构造两个集合的有序交集	set_intersection()
构造两个集合的有序差集	set_difference()
构造两个集合的有序对称差集（并-交）	set_symmetric_difference()
堆操作 向堆中加入元素	push_heap()
从堆中弹出元素	pop_heap()
从序列构造堆	make_heap()
给堆排序	sort_heap()
最大和最小 两个值中较小的	min()
两个值中较大的	max()
序列中的最小元素	min_element()
序列中的最大元素	max_element()
词典比较 两个序列按字典序的第一个在前	lexicographical_compare()
排列生成器 按字典序的下一个排列	next_permutation()
按字典序的前一个排列	prev_permutation()

四、部分函数操作实例

1.count()与replace()

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int main()
{
	vector<int> a = { 12, 2, 3, 1, 33, 4, 11 ,11,11};
	cout << "11的个数："<<count(a.begin(), a.end(), 11) << endl;
	string str("aaaaaaaaaaasssssaa");
	cout << "源str:" << str << endl;

	cout << "a 的个数"<<count(str.begin(), str.end(), 'a') << endl;
	replace(str.begin(), str.end(), 'a', 'b');
	cout << "使用b替换a后的str:" << str << endl;
	cout << "b 的个数" << count(str.begin(), str.end(), 'b') << endl;

	system("pause");
	return 0;
}

2.sort()与for_each

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int main()
{
	vector<int> a = { 12, 2, 3, 1, 33, 4, 11, 11, 11 };
	/*遍历*/
	for_each(a.begin(), a.end(), [](int x){cout << x << ' '; });
	cout << endl;
	/*sort默认升序*/
	sort(a.begin(), a.end());
	for_each(a.begin(), a.end(), [](int x){cout << x << ' '; });
	
	/*自定义降序*/
	sort(a.begin(), a.end(), [](int x, int y){return x > y; });
	cout << endl;
	for_each(a.begin(), a.end(), [](int x){cout << x << ' '; });
	cout << endl;

	/*字符串*/
	string str("bashdiahwdbawdhoaiw");
	for_each(str.begin(), str.end(), [](char x){cout << x; });

	/*sort默认升序*/
	sort(str.begin(), str.end());
	for_each(str.begin(), str.end(), [](char x){cout << x ; });
	cout << endl;
	
	/*自定义降序*/
	sort(str.begin(), str.end(), [](char c, char d){return c > d; });
	for_each(str.begin(), str.end(), [](char x){cout << x; });
	
	system("pause");
	return 0;
}

3.sort_heap(),pop_heap(),push_heap()与make_heap()

#include <iostream>     // std::cout
#include <algorithm>
#include <vector>       // std::vector
using namespace std;
int main()
{
	int ia[9] = { 0, 1, 2, 3, 5, 4, 9, 7, 6};
	vector <int> ivec(ia, ia + 9);
	
	/*创建一个最大堆*/
	make_heap(ivec.begin(), ivec.end());	
	for_each(ivec.begin(), ivec.end(), [](int x){cout << x << ' '; });  //9 7 4 6 5 0 2 3 1
	cout << endl;
	
	/*加入元素8*/
	ivec.push_back(8);
	push_heap(ivec.begin(), ivec.end());	
	for_each(ivec.begin(), ivec.end(), [](int x){cout << x << ' '; }); //9 8 4 6 7 0 2 3 1 5
	cout << endl;

	/*弹出最大元素,并未在ivec中删除*/
	pop_heap(ivec.begin(), ivec.end());
	for_each(ivec.begin(), ivec.end(), [](int x){cout << x << ' '; }); //8 7 4 6 5 0 2 3 1 9
	cout << endl;
	cout << ivec.back() << endl;  //9
	
	/*ivec中删除*/
	ivec.pop_back();
	for_each(ivec.begin(), ivec.end(), [](int x){cout << x << ' '; }); //8 7 4 6 5 0 2 3 1
	cout << endl;

	/*堆排序*/
	sort_heap(ivec.begin(), ivec.end());
	for_each(ivec.begin(), ivec.end(), [](int x){cout << x << ' '; }); //0 1 2 3 4 5 6 7 8
	cout << endl;

	system("pause");

	return 0;
}

4.binary_search(),lower_bound(),upper_bound和equal()

#include <iostream>     // std::cout
#include <algorithm>    // 
#include <vector>       // std::vector
using namespace std;

int main()
{
	int arr[9] = { 1, 12, 7, 6, 4, 5, 3, 2, 9 };
	vector<int> ivec(arr, arr + 9);
	vector<int> ivec_bak(arr, arr + 9);
	ivec.push_back(9);
	ivec_bak.push_back(10);
	/*使用二分查找前提是序列有序*/
	sort(ivec.begin(), ivec.end());

	/*查找序列是否有元素7*/
	cout << binary_search(ivec.begin(), ivec.end(), 7)  << endl;  //1
	/*二分搜索 lower_bound查找序列中第一个>=7的位置,返回值为迭代器*/
	cout << *lower_bound(ivec.begin(), ivec.end(), 7) << endl;
	/*二分搜索 upper_bound查找序列中> 7的元素中最小值位置,返回值为迭代器*/
	cout << *upper_bound(ivec.begin(), ivec.end(), 9) << endl;

	/*注意，equal是默认两个比较的序列长度是相同的，所以在使用前，需要判断长度是否一致*/
	cout << equal(ivec.begin(), ivec.end(), ivec_bak.begin()) << endl;  // 0

	system("pause");
	return 0;
}

5.remove()，remove_if()，max_element()和min_element()

#include <iostream>     // std::cout
#include <algorithm>    // 
#include <vector>       // std::vector
#include <string>
using namespace std;

int  main()
{

	string str("waadddaadwadawdwarfa");

	/*删除字符'd'*/
	auto str_it = remove(str.begin(), str.end(), 'd');
	cout << str << endl;	// waaaawaawwarfadwarfa
	str.erase(str_it, str.end());
	cout << str << endl; // waaaawaawwarfa

	/*删除字符'w'*/
	str.erase(remove(str.begin(), str.end(), 'w'));
	cout << str << endl; // aaaaaaarfarfa



	vector<int> ivec{1,5,11,55,77,12,46};

	/*序列中最大元素*/
	cout << *max_element(ivec.begin(), ivec.end()) << endl; //77
	/*序列中最小元素*/
	cout << *min_element(ivec.begin(), ivec.end()) << endl; //1

	/*满足条件的元素的位置被后面的元素进行移动覆盖。所在空间并未删除，返回指向在条件之外的序列的尾部*/
	auto it = remove_if(ivec.begin(), ivec.end(), [](int x){ return (x >5) && (x < 46) ; });

	for_each(it, ivec.end(), [](int x){cout << x << ' '; });  // 12 46
	cout << endl;

	//for_each(ivec.begin(), ivec.end(), [](int x){cout << x << ' '; }); 
	for (auto i : ivec) cout << i << ' '; // 1 5 55 77 12 46
	cout << endl;

	/*erase和remove_if进行搭配使用*/
	ivec.erase(it, ivec.end());

	for (auto i : ivec) cout << i << ' '; // 1 5 55 77 
	cout << endl;

	system("pause");
	return 0;
}

6.unique(),reverse()和mismatch()

#include <iostream>     // std::cout
#include <algorithm>    // 
#include <vector>       // std::vector
#include <string>
#include <list>
using namespace std;

int main()
{

	string str1("adwafafawgdaihdaowiyeabddauwiodha");

	/*使用unique时需要先进行排序，同二分查找*/
	cout << "str1: " << str1 << endl;  //str1: adwafafawgdaihdaowiyeabddauwiodha
	/*使用unique时需要先进行排序，同二分查找*/
	sort(str1.begin(), str1.end(), [](char c, char d){ return c > d; });

	cout << "str1: " << str1 << endl; //str1: ywwwwuooiiihhgffeddddddbaaaaaaaaa

	str1.erase(unique(str1.begin(), str1.end()), str1.end());
	cout << "str1: " << str1 << endl; //str1: ywuoihgfedba

	/*逆转*/
	string str2("hfoiahoaojcnuiwepawyajdoawjopurawcia");
	cout << "str2: " << str2 << endl;  // str2: hfoiahoaojcnuiwepawyajdoawjopurawcia
	reverse(str2.begin(), str2.end());
	cout << "str2: " << str2 << endl; // str2: aicwarupojwaodjaywapewiuncjoaohaiofh

	/*逆转*/
	list<int> il{ 1, 5, 8, 6, 2, 88, 11, 55 }; 
	for (auto i : il) cout << i <<' ';   //1 5 8 6 2 88 11 55
	cout << endl;
	list<int>::iterator ite = il.begin();
	for (int i = 0; ; i++)
	{
		ite++;
		if (i == 4)
			break;
	}
	reverse(ite, il.end());
	for (auto i : il) cout << i << ' ';  //1 5 8 6 2 55 11 88
	cout << endl;

	/*mismatch。两个序列中第一个不匹配的位置*/
	string s1 = "aaaaaaavvvvvvvvvvvvvwwwwwwwwww";
	string s2 = "aaaaaaavvvvvvvvetvvvwwwwwwwwww";
	/*返回pair<string::iterator,string::iterator> ,
	  first指向第一个序列中不同元素的位置，而second则
	  指向第二个序列*/
	auto it = mismatch(s1.begin(), s1.end(), s2.begin()); 
	cout << *it.first <<" " <<*it.second << endl;  // v e
	system("pause");
	return 0;
}

7.find(),find_if()和find_first_of()

#include <iostream>     // std::cout
#include <algorithm>    // 
#include <vector>       // std::vector
#include <string>
#include <list>
using namespace std;

/*find find_if find_first_of*/
int main()
{

	string str = "adnahdawio12131w2131jmaklwhdajdaoiwjdioa";
	/*找到第一个为2的字符的位置迭代器*/
	cout << *find(str.begin(), str.end(), '2') << endl; //2
	/*计算第一个为i的字符在第几个位置*/
	cout << distance(str.begin(),find_if(str.begin(), str.end(), [](char c){return c == 'i'; }))<<endl; //8
	cout << str[8] << endl; // i
	string s1 = "aaaeeebbbeee";
	/*找到区间[first1,last1] 中第一个在区间[first2,last2]中的元素*/
	cout << *find_first_of(s1.begin(), s1.begin() +6 , s1.begin() + 7, s1.end()) << endl; //e


	system("pause");
	return 0;
}

参考自 https://blog.csdn.net/Bw9839/article/details/81054773