STL专题-常用算法

本文最后更新于：2021年2月6日晚上

STL常用算法，for_each遍历，transfrom，find，count，sort，merge，reserve，fill以及一些集合算法等。

头文件

算法主要是由头文件<algorithm> <functional> <numeric>组成。
<algorithm>是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历操作、复制、修改等等
<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数
<functional>定义了一些模板类,用以声明函数对象。

常用遍历算法

for_each

for_each(iterator beg, iterator end, _func);
- beg 开始迭代器
- end 结束迭代器
- _func 函数或者函数对象，自定义方式。
通过调用_func 来实现遍历容器元素。

class MyPrint {
public:
	//重载()
	void operator()(int a) {
		cout << a << " ";
	}
};

void test1() {

	//for_each算法

	vector<int> v;
	for (int i = 0; i < 10; i++)
		v.push_back(i);

	for_each(v.begin(),v.end(),MyPrint());
}

transform

transform(iterator beg1, iterator end1, iterator beg2, _func);
- beg1 源容器开始迭代器
- end1 源容器结束迭代器
- beg2 目的容器开始迭代器
- _func 函数或者函数对象，自定义方式。
搬运容器到另一个容器中，中间可通过_func来处理数据。
搬运到新的容器一定要先开辟空间。

class MyPrint {
public:
	//重载()
	void operator()(int a) {
		cout << a << " ";
	}
};

class MyTransform {
public:
	int operator()(int a) {
		return a * 10;
	}
};

void test2() {

	//transform
	vector<int> v;
	for (int i = 0; i < 10; i++)
		v.push_back(i);

	list<int> l;
	l.resize(v.size());	//使用transform前一定要开辟空间,否则就会报错

	transform(v.begin(),v.end(),l.begin(), MyTransform());

	for_each(l.begin(), l.end(), MyPrint());

}

常用查找算法

find

find(iterator beg, iterator end, value);
- beg 开始迭代器
- end 结束迭代器
- value 查找的元素
按值查找元素，找到返回指定位置迭代器，找不到返回end()结束迭代器位置
find底层使用了==运算符，所以自定义数据类型应当重载这个符号。

class Cat {
public:
	Cat(string name, int age) {
		m_name = name;
		m_age = age;
	}

	//自定义数据类型要重载==
	bool operator==(const Cat& other){
		if (m_name == other.m_name && m_age == other.m_age)
			return true;
		else return false;
	}

	string m_name;
	int m_age;
};

void test3() {

	//find
	vector<int> v;
	for (int i = 0; i < 10; i++)
		v.push_back(i);

	vector<int>::iterator it = find(v.begin(),v.end(),5);
	if (it == v.end())
		cout << "没有找到" << endl;
	else cout << "已经找到：" << *it << endl;

	Cat c1("Tom",3);
	Cat c2("Jerry",4);
	Cat c3("Bob",3);

	vector<Cat> vc;

	vc.push_back(c1);
	vc.push_back(c2);
	vc.push_back(c3);

	Cat c("Tom", 3);

	vector<Cat>::iterator itc = find(vc.begin(), vc.end(), c);
	if (itc == vc.end())
		cout << "没有找到" << endl;
	else cout << "已经找到：" << itc->m_name << endl;

}

find_if

find_if(iterator beg, iterator end, _Pred);
- beg 开始迭代器
- end 结束迭代器
- _Pred 函数或者谓词（返回bool类型的仿函数）
按条件查找元素，找到返回指定位置迭代器，找不到返回end()结束迭代器位置

//使用了上面的Cat类
class Greaterive {
public:
	bool operator()(int a) {
		return a > 5;
	}
};

class CatGreater3 {
public:
	bool operator()(const Cat& c) {
		if (c.m_age > 3)
			return true;
		else return false;
	}
};

void test4() {

	//find_if
	vector<int> v;
	for (int i = 0; i < 10; i++)
		v.push_back(i);

	vector<int>::iterator it = find_if(v.begin(), v.end(), Greaterive());
	if (it == v.end())
		cout << "没有找到大于5" << endl;
	else cout << "已经找到大于5：" << *it << endl;

	Cat c1("Tom", 3);
	Cat c2("Jerry", 4);
	Cat c3("Bob", 3);

	vector<Cat> vc;

	vc.push_back(c1);
	vc.push_back(c2);
	vc.push_back(c3);

	Cat c("Tom", 3);

	vector<Cat>::iterator itc = find_if(vc.begin(), vc.end(), CatGreater3());
	if (itc == vc.end())
		cout << "没有找到3岁以上的猫" << endl;
	else cout << "已经找到3岁以上的猫：" << itc->m_name << endl;

}

adjacent_find 查找相邻重复元素

adjacent_find(iterator beg, iterator end);
- beg 开始迭代器
- end 结束迭代器
查找相邻重复元素,返回相邻元素的第一个位置的迭代器

void test5() {

	//adjacent_find
	vector<int> v;
	v.push_back(2);
	v.push_back(1);
	v.push_back(3);
	v.push_back(2);
	v.push_back(4);
	v.push_back(4);

	vector<int>::iterator it = adjacent_find(v.begin(),v.end());

	if (it == v.end())
		cout << "没有找到相邻且重复的元素" << endl;
	else cout << "找到了相邻且重复的元素" << *it << endl;

}
//结果为4

binary_search 二分查找

bool binary_search(iterator beg, iterator end, value);
- beg 开始迭代器
- end 结束迭代器
- value 查找的元素
使用二分查找查找指定元素
必须对有序序列进行查找，否则结果不可知

void test6() {

	//binary_search
	vector<int> v;
	int num1 = 1;
	int num2 = 20;
	for (int i = 0; i < 10; i++) {
		v.push_back(num1++);
		v.push_back(num2--);
	}

	for_each(v.begin(),v.end(),MyPrint());

	bool flag = binary_search(v.begin(),v.end(),7);

	if (flag) cout << "找到了" << endl;
	else cout << "未找到" << endl;

	sort(v.begin(), v.end());//默认排序之后

	flag = binary_search(v.begin(), v.end(), 7);

	if (flag) cout << "找到了" << endl;
	else cout << "未找到" << endl;

}

输出结果：

1
2

未找到
找到了

count 统计

int count(iterator beg, iterator end, value);
- beg 开始迭代器
- end 结束迭代器
- value 查找的元素
按照值进行统计，返回出现的次数。
对于自定义数据类型应当重载==操作符。

count_if

count_if(iterator beg, iterator end, _Pred);
- beg 开始迭代器
- end 结束迭代器
- _Pred 谓词，自定义
按照自定义的条件来统计元素个数。

class Greater4 {

public:
	bool operator()(int a) {
		return a > 4;
	}

};

void test7() {

	//count count_if

	vector<int> v;
	v.push_back(2);
	v.push_back(1);
	v.push_back(3);
	v.push_back(2);
	v.push_back(4);
	v.push_back(4);
	v.push_back(7);
	v.push_back(9);

	int num = count(v.begin(), v.end(), 4);	//按照值统计
	cout << "4的个数为：" << num << endl;	//2

	num = count_if(v.begin(),v.end(),Greater4());	//按照条件统计
	cout << "大于4的个数为：" << num << endl;	//2

}

常用排序算法

sort 排序

sort(iterator beg, iterator end, _Pred);
- beg 开始迭代器
- end 结束迭代器
- _Pred 谓词，自定义，或者使用STL中已有的谓词
对容器内元素进行排序，默认是升序排序。

void test8() {
	//sort
	vector<int> v;

	v.push_back(5);
	v.push_back(3);
	v.push_back(1);
	v.push_back(6);
	v.push_back(4);
	v.push_back(2);

	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;

	sort(v.begin(), v.end());//默认排序之后

	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;

	sort(v.begin(),v.end(),greater<int>());//从大到小排序

	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;

}

random_shuffle 洗牌

random_shuffle(iterator beg, iterator end);
- beg 开始迭代器
- end 结束迭代器
指定范围内的元素随机调整次序.
可设置随机数种子，使得每次结果均不同。

void test9() {

	//random_shuffle 

	srand((unsigned int)time(NULL));//设置随机数种子，使得每次结果均不同

	vector<int> v;
	for (int i = 0; i < 10; i++)
		v.push_back(i);

	random_shuffle(v.begin(),v.end());

	for_each(v.begin(), v.end(), MyPrint());

}

merge 合并

merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest, _Pred );
- beg1 容器1开始迭代器
- end1 容器1结束迭代器
- beg2 容器2开始迭代器
- end2 容器2结束迭代器
- dest 目标容器开始迭代器
- _Pred 谓词，默认由小到大排序，可省略
将两个容器的元素合并，并存储到另一个容器之中。
两个容器必须是有序的，且顺序相同，并且和merge中的顺序相同，最终排序结果仍然有序。否则就会报错。
目标容器必须先预先分配空间。

void test10() {

	//merge
	vector<int> v1;
	vector<int> v2;

	for (int i = 0; i < 10; i++) {
		v1.push_back(10-i);
		v2.push_back(10-i);//降序插入
	}

	vector<int> v3;
	v3.resize(v1.size()+v2.size());

	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin(),greater<int>());//由大到小排序

	for_each(v3.begin(),v3.end(),MyPrint());
}

reserve 反转

reverse(iterator beg, iterator end);
- beg 开始迭代器
- end 结束迭代器
将容器内元素进行反转。

void test11() {

	//reverse
	vector<int> v1;

	for (int i = 0; i < 10; i++) {
		v1.push_back(10 - i);//降序插入
	}

	reverse(v1.begin(),v1.end());

	for_each(v1.begin(), v1.end(), MyPrint());

}

常用拷贝和替换算法

copy

copy(iterator beg, iterator end, iterator dest);
- beg 开始迭代器
- end 结束迭代器
- dest 目标容器开始迭代器
容器内指定范围的元素拷贝到另一容器中，当然用这些容器提供的自带的构造方法也可以完成。
拷贝前记得给目标容器开辟空间。

class MyPrint {
public:
	void operator()(int val) {
		cout << val << " ";
	}
};

void test1() {

	//copy
	list<int> l;
	for (int i = 0; i < 10; i++)
		l.push_back(i);

	list<int> l2;
	l2.resize(l.size());

	copy(l.begin(), l.end(), l2.begin());

	for_each(l2.begin(),l2.end(),MyPrint());
}

replace

replace(iterator beg, iterator end, oldvalue, newvalue);
- beg 开始迭代器
- end 结束迭代器
- oldvalue 旧元素
- newvalue 新元素
将容器内指定范围的旧元素修改为新元素。

replace_if

replace_if(iterator beg, iterator end, _pred, newvalue);
- beg 开始迭代器
- end 结束迭代器
- _pred 谓词，自定义条件
- newvalue 新元素
将区间内满足条件的元素，替换成指定元素

class Greater3 {
public:
	//谓词
	bool operator()(int val) {
		return val > 3;
	}
};

void test2() {

	//replace replace_if

	vector<int> v;

	v.push_back(2);
	v.push_back(3);
	v.push_back(5);
	v.push_back(1);
	v.push_back(6);
	v.push_back(3);
	v.push_back(7);
	v.push_back(2);

	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;

	//将2替换成-20
	replace(v.begin(),v.end(),2,-20);

	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;

	//将大于3的替换成25
	replace_if(v.begin(),v.end(), Greater3(),25);

	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;
}

swap

swap(container c1, container c2);
- c1 容器1
- c2 容器2，二者为同类型容器
互换两个容器的元素。其实一些容器本身也提供了这样的方法。

常用算术生成算法

算术生成算法属于小型算法，使用时包含的头文件为 #include <numeric>

accumulate —— 元素累加

accumulate(iterator beg, iterator end, value);
- beg 开始迭代器
- end 结束迭代器
- value 表示累加的起始值
计算区间内容器元素累计总和

#include <numeric>//注意头文件

void test3() {

	//accumulate

	vector<int>v;
	for (int i = 1; i <= 100; i++) {
		v.push_back(i);
	}

	int total1 = accumulate(v.begin(),v.end(),0);		//5050
	int total2 = accumulate(v.begin(),v.end(),1000);	//6050

	cout << total1 << endl;
	cout << total2 << endl;
}

fill —— 填充

fill(iterator beg, iterator end, value);
- beg 开始迭代器
- end 结束迭代器
- value 填充的值
向容器中填充指定的元素。

//#include <numeric> 并非再这个头文件之中
void test4() {

	//fill
	vector<int> v;

	v.resize(10);

	fill(v.begin(), v.end(), 99);

	for_each(v.begin(),v.end(),MyPrint());

}

常用集合算法

set_intersection 求交集

set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
- beg1 容器1开始迭代器
- end1 容器1结束迭代器
- beg2 容器2开始迭代器
- end2 容器2结束迭代器
- dest 目标容器开始迭代器
求两个容器的交集。两个集合必须是有序序列。
函数返回值是最后一个元素的迭代器地址的下一个位置。
记得给目标容器开辟空间。

void test6() {

	vector<int> v1;
	vector<int> v2;

	for (int i = 0; i < 10; i++) {
		v1.push_back(i);
		v2.push_back(i+8);
	}

	vector<int> v3;
	v3.resize(min(v1.size(),v2.size()));	//开辟空间，并且空间只需要两个容器中最小的空间

	//返回值是容器截至的迭代器的下一个位置，即通俗意义的end()
	vector<int>::iterator itEnd = set_intersection(v1.begin(), v1.end(),v2.begin(),v2.end(),v3.begin());

	for_each(v3.begin(), itEnd,MyPrint());	//8 9
	cout << endl;

	for_each(v3.begin(), v3.end(), MyPrint());//8 9 0 0 0 0 0 0 0 0

}

set_union 求并集

set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
- beg1 容器1开始迭代器
- end1 容器1结束迭代器
- beg2 容器2开始迭代器
- end2 容器2结束迭代器
- dest 目标容器开始迭代器
求两个容器的并集。两个集合必须是有序序列。
函数返回值是最后一个元素的迭代器地址的下一个位置。
记得给目标容器开辟空间。

void test7() {
	//set_union

		//set_intersection

	vector<int> v1;
	vector<int> v2;

	for (int i = 0; i < 10; i++) {
		v1.push_back(i);
		v2.push_back(i + 8);
	}

	vector<int> v3;
	v3.resize(v1.size()+v2.size());	//开辟空间，极端情况是两个空间之和

    //函数返回值是最后一个元素的迭代器地址的下一个位置。
	vector<int>::iterator itEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());

	for_each(v3.begin(),itEnd,MyPrint());

}

set_difference

set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
- beg1 容器1开始迭代器
- end1 容器1结束迭代器
- beg2 容器2开始迭代器
- end2 容器2结束迭代器
- dest 目标容器开始迭代器
求两个容器的差集。两个集合必须是有序序列。
函数返回值是最后一个元素的迭代器地址的下一个位置。
记得给目标容器开辟空间。

void test8() {

	//set_difference

	vector<int> v1;
	vector<int> v2;

	for (int i = 0; i < 10; i++) {
		v1.push_back(i);
		v2.push_back(i + 8);
	}

	vector<int> v3;
	v3.resize(max(v1.size(), v2.size()));	//开辟空间，v2相对于v1的差集，最大就是两者中空间最大的那个

	vector<int>::iterator itEnd = set_difference(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin());

	cout << "v1 对于 v2 的差集" << endl;
	for_each(v3.begin(), itEnd, MyPrint());
	cout << endl;

	itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), v3.begin());

	cout << "v2 对于 v1 的差集" << endl;
	for_each(v3.begin(), itEnd, MyPrint());
	cout << endl;

}

运行结果：

v1 对于 v2 的差集
0 1 2 3 4 5 6 7
v2 对于 v1 的差集
10 11 12 13 14 15 16 17

C/C++

C++ STL

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

STL专题-函数对象上一篇

STL专题-deque 下一篇