提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

黑马C++笔记——STL常用算法

C++算法笔记 常用 STL 黑马
2023-09-14 09:14:58 时间

STL常用算法

1.概述

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

2.常用算法

1.常用遍历算法

  • for_each 遍历容器
  • transform 搬运一个容器中的元素 到 另一个容器中

1.for_each

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

void print01(int val) {
	cout << val << " ";
}

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

void test() {
	vector<int> v{ 1,2,3,4,5,6,7,8,9,10 };
	
	//1.利用普通函数 for_each
	for_each(v.begin(), v.end(), print01);
	cout << endl;

	cout << "-----------------------------------------------" << endl;
	//2.利用仿函数遍历
	for_each(v.begin(), v.end(), print02());
	cout << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}

2.transform

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

class Transform {
public:
	int operator() (int val) {
		return val;
	}
};

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

void test() {
	vector<int> v{ 1,2,3,4,5,6,7,8,9,10 };
	vector<int> target;

	//利用transform 将容器v 中的元素 搬到target中

	//提前分配足够的容量
	target.resize(v.size());

	//开始搬运
	transform(v.begin(), v.end(), target.begin(), Transform());

	//遍历输出
	for_each(target.begin(), target.end(), Print());
	cout << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}

2.常用查找算法

  • find 查找元素
  • find_if 按照条件查找元素
  • adjacent_find 查找相邻的重复元素
  • binary_search 二分查找元素
  • count 统计元素个数
  • count_if 按条件统计元素个数

1.find

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

//1.查找内置数据类型
void test01() {
	vector<int> v{ 1,2,3,4,5,6,7,8,9,10 };

	//查找是否存在元素6
	auto it = find(v.begin(), v.end(), 6);
	if (it == v.end()) {
		cout << "容器中没有元素6" << endl;
	}
	else {
		cout << "找到了：" << *it << endl;
	}
}

class Person {
public:
	string name;
	int age;
	Person(string name, int age) {
		this->name = name;
		this->age = age;
	}

	bool operator== (const Person& p) {
		return this->name == p.name && this->age == p.age;
	}
};

//2.查找自定义数据类型
void test02() {
	vector<Person> v;
	Person p1("wurusai", 20);
	Person p2("zed", 45);
	Person p3("yassuo", 30);
	Person p4("leesin", 50);
	Person p5("pyke", 100);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);

	Person pp("wurusai", 20);

	//查找是否存在pp
	auto it = find(v.begin(), v.end(), pp);
	if (it == v.end()) {
		cout << "容器中没有pp这个元素" << endl;
	}
	else {
		cout << "找到了：name = " << it->name << " , age = " << it->age << endl;
	}
}

int main() {
	//test01();
	test02();
	system("pause");
	return 0;
}

2.find_if

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

class GreaterFive {
public:
	bool operator()(int val) {
		return val > 5;
	}
};

//1.查找内置数据类型
void test01() {
	vector<int> v{ 1,2,3,4,5,6,7,8,9,10 };

	//查找是否有 大于 5 的元素
	auto it = find_if(v.begin(), v.end(), GreaterFive());

	if (it == v.end()) {
		cout << "该容器中没有大于5的元素" << endl;
	}
	else {
		cout << "找到了大于5的元素：" << *it << endl;
	}
}

class Person {
public:
	int age;
	string name;
	Person(int age, string name) {
		this->age = age;
		this->name = name;
	}
};

class Greater30 {
public:
	bool operator() (const Person& p) {
		return p.age > 30;
	}
};

//2.查找自定义类型
void test02() {
	vector<Person> v;

	Person p1(10, "aaa");
	Person p2(20, "bbb");
	Person p3(30, "ccc");
	Person p4(40, "ddd");
	Person p5(50, "eee");

	//查找是否有年龄大于30的元素
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);

	auto it = find_if(v.begin(), v.end(), Greater30());
	if (it == v.end()) {
		cout << "没有年龄大于30的元素" << endl;
	}
	else {
		cout << "找到了年龄大于30的元素：name = " << it->name << " , age = " << it->age << endl;
	}
}

int main() {
	//test01();
	test02();
	system("pause");
	return 0;
}

3.adjacent_find

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

void test() {
	vector<int> v{ 1,2,3,4,5,6,6,7,7,8,8 };
	//查找相邻重复元素
	//注意：只能找到第一个相邻重复的元素
	auto it = adjacent_find(v.begin(), v.end());

	if (it == v.end()) {
		cout << "容器中没有重复相邻元素" << endl;
	}
	else {
		cout << "找到了：" << *it << endl; //6
	}
}

int main() {
	test();
	system("pause");
	return 0;
}

4.binary_search

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

void test() {
	vector<int> v{ 1,2,3,4,5,6,7,8,8,8,9,10 };

	//查找元素 8 是否存在
	bool ok = binary_search(v.begin(), v.end(), 8); // 注意：该函数只能用于有序序列
	if (ok) {
		cout << "存在" << endl;
	}
	else {
		cout << "不存在" << endl;
	}
}

int main() {
	test();
	system("pause");
	return 0;
}

5.count

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

//1.统计内置数据类型个数
void test01() {
	vector<int> v{ 1,2,3,4,5,6,7,7,7,7,8,7,8,8,7 };

	//统计元素7的个数
	int cnt = count(v.begin(), v.end(), 7);
	cout << "元素7 的个数为：" << cnt << endl;//6
}

class Person {
public:
	int age;
	string name;
	Person(int age, string name) {
		this->age = age;
		this->name = name;
	}

	bool operator== (const Person& p) {
		return this->age== p.age;
	}
};

//2.统计自定义数据类型的个数
void test02() {
	vector<Person> v;

	Person p1(20, "wurusai");
	Person p2(30, "zed");
	Person p3(40, "aaa");
	Person p4(20, "bbb");
	Person p5(20, "ccc");

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);

	//统计与 Tom 年龄相等的人的数量
	int cnt = count(v.begin(), v.end(), Person(20, "Tom"));

	cout << "与Tom年龄相同的人数：" << cnt << endl;//3
}

int main() {
	//test01();
	test02();
	system("pause");
	return 0;
}

6.count_if

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


class Greater5 {
public:
	bool operator() (int val) {
		return val > 5;
	}
};

//统计内置数据类型
void test01() {
	vector<int> v{ 1,2,3,4,5,6,7,8,9,10 };

	//统计大于5的元素个数
	int cnt = count_if(v.begin(), v.end(), Greater5());

	cout << "大于5的元素个数为：" << cnt << endl;
}

class Person {
public:
	int age;
	string name;
	Person(int age, string name) {
		this->age = age;
		this->name = name;
	}
};

class AgeGreater20 {
public:
	bool operator() (const Person& p) {
		return p.age > 20;
	}
};

//统计自定义类型
void test02() {
	vector<Person> v;
	Person p1(20, "aaa");
	Person p2(15, "bbb");
	Person p3(26, "ccc");
	Person p4(33, "eee");
	Person p5(25, "ddd");

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);

	int cnt = count_if(v.begin(), v.end(), AgeGreater20());

	cout << "年龄大于20的人数为：" << cnt << endl;
}

int main() {
	//test01();
	test02();
	system("pause");
	return 0;
}

3.常见排序算法

  • sort 对容器内的元素进行排序（默认是升序）
  • random_shuffle 将指定范围内的元素随机打乱
  • merge 将两个容器的元素合并到另外一个容器中
  • reverse 反转指定范围的元素

1.sort

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

void test() {
	vector<int> v{ 7,5,12,3,6,4,9,5,1,2,3,5,11,23 };

	//升序排序
	sort(v.begin(), v.end());

	//for_each 用lambda表达式输出
	for_each(v.begin(), v.end(), [](int val) {
		cout << val << " ";
		});
	cout << endl;


	//降序排序
	sort(v.begin(), v.end(), greater<int>());

	for_each(v.begin(), v.end(), [](int val) {
		cout << val << " ";
		});
	cout << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}

2.random_shuffle

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

//随机打乱 容器中的元素
void test() {
	//随机数种子
	srand((unsigned int)time(nullptr));
	vector<int> v{ 1,2,3,4,5,6,7,8,9,10 };
	
	//洗牌
	random_shuffle(v.begin(), v.end());

	//输出
	for_each(v.begin(), v.end(), [](int val) {
		cout << val << " ";
		});
	cout << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}

3.merge

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

void test() {
	//merge 将两个有序列表 合并到 一个列表中（还是有序的）
	vector<int> v1{ 1,3,5,7,9,11,13,15 }, v2{ 0,2,4,6,8,10,12,14 };
	vector<int> t;
	//预留足够的空间
	t.resize(v1.size() + v2.size());

	//merge
	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), t.begin());

	//遍历
	for_each(t.begin(), t.end(), [](int val) {
		cout << val << " ";
		});
	cout << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}

4.reverse

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

void test() {
	//reverse 反转
	vector<int> v{ 1,2,3,4,5,6,7,8,9,10 };

	cout << "反转前:" << endl;
	for_each(v.begin(), v.end(), [](int val) {
		cout << val << " ";
		});
	cout << endl;

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

	cout << "反转后:" << endl;
	for_each(v.begin(), v.end(), [](int val) {
		cout << val << " ";
		});
	cout << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}

4.常见的拷贝替换算法

  • copy 将容器指定范围的元素拷贝到另一个容器当中去
  • replace 将指定范围内的元素替换为新的元素
  • replace_if 将指定范围内的满足条件的元素替换为新的元素
  • swap 互换两个容器的元素

1.copy

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

void test() {
	vector<int> v{ 1,2,3,4,5,6,7,8,9,10 };
	vector<int> t;

	//预留足够的空间
	t.resize(v.size());

	//copy
	copy(v.begin(), v.end(), t.begin());


	//输出
	for_each(t.begin(), t.end(), [](int val) {
		cout << val << " ";
		});
	cout << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}

2.replace

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

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

void test() {
	vector<int> v{ 1,2,3,4,5,5,5,6,6,4,5,7,5,1 };
	cout << "替换前:" << endl;
	for_each(v.begin(), v.end(), MyPrint());


	//将 5 替换为 -1
	replace(v.begin(), v.end(), 5, -1);

	cout << "替换后:" << endl;
	for_each(v.begin(), v.end(), MyPrint());
	
}

int main() {
	test();
	system("pause");
	return 0;
}

3.replace_if

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

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

class Greater5 {
public:
	bool operator()(int val) {
		return val >= 5;
	}
};

void test() {
	vector<int> v{ 1,2,3,4,5,5,5,6,6,4,5,7,5,1 };
	cout << "替换前:" << endl;
	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;


	//将 大于等于5的元素 替换为 -1
	replace_if(v.begin(), v.end(), Greater5(), -1);

	cout << "替换后:" << endl;
	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}

4.swap

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

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


void test() {
	vector<int> v1{ 1,2,3,4,5,5,5,6,6,4,5,7,5,1 };
	vector<int> v2{ 100,111,112,113,56,12 };
	cout << "交换前:" << endl;
	for_each(v1.begin(), v1.end(), MyPrint());
	cout << endl;
	for_each(v2.begin(), v2.end(), MyPrint());
	cout << endl;


	//交换
	cout << "-----------------------------------------------------" << endl;
	v1.swap(v2);
	

	cout << "交换后:" << endl;
	for_each(v1.begin(), v1.end(), MyPrint());
	cout << endl;
	for_each(v2.begin(), v2.end(), MyPrint());
	cout << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}

5.常用算数算法

  • accumulate 计算容器内元素的累加和
  • fill 填充容器

1.accumulate

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

void test() {
	vector<int> v;
	for (int i = 0; i <= 100; i++) v.push_back(i);

	//元素的累加和
	int sum = accumulate(v.begin(), v.end(), 0);
	cout << "sum = " << sum << endl; //5050
}

int main() {
	test();
	system("pause");
	return 0;
}

2.fill

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

void test() {
	vector<int> v(10);

	//填充为指定元素
	fill(v.begin(), v.end(), 10);

	//遍历
	for_each(v.begin(), v.end(), [](int val) {
		cout << val << " ";
		});
	cout << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}

6.常见集合算法

  • set_intersection 求两个集合的交集
  • set_union 求两个集合的并集
  • set_difference 求两个集合的差集

1.set_intersection

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

void test() {
	//求两个集合的交集
	vector<int> v1{ 1,2,3,4,5,6,7,8,9 }, v2{ 2,2,2,3,3,3,6,7,8,9 };

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

	//求交集
	auto itEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), t.begin());
	

	//遍历输出
	for_each(t.begin(), itEnd, [](int val) {
		cout << val << " ";
		});
	cout << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}

2.set_union

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

void test() {
	//求两个集合的并集
	vector<int> v1{ 1,3,5,7,9 }, v2{ 2,4,6,8,10 };

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

	//求并集
	auto itEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), t.begin());
	

	//遍历输出
	for_each(t.begin(), itEnd, [](int val) {
		cout << val << " ";
		});
	cout << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}

3.set_difference

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

void test() {
	//求两个集合的差集
	vector<int> v1{ 1,2,3,4,5,6,7,8,9 }, v2{ 7,8,9,10,11,12,13 };

	vector<int> t;
	t.resize(max(v1.size() , v2.size()));

	//求并集
	auto itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), t.begin());
	

	//v1 - v2
	for_each(t.begin(), itEnd, [](int val) {
		cout << val << " ";
		});
	cout << endl;

	cout << "-----------------------------------------" << endl;

	//求并集
	itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), t.begin());


	//v2 - v1
	for_each(t.begin(), itEnd, [](int val) {
		cout << val << " ";
		});
	cout << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}

相关文章