当前位置:   article > 正文

5. STL——常用算法

5. STL——常用算法

概述:

  1. 算法主要是由头文件 < a l g o r i t h m > <algorithm> <algorithm> < f u n c t i o n a l > <functional> <functional> < n u m e r i c > <numeric> <numeric>组成
  2. < a l g o r i t h m > <algorithm> <algorithm>是所有STL头文件中最大的一个,范围涉及到比较,交换,查找,遍历操作,复制,修改等等
  3. < n u m e r i c > <numeric> <numeric>体积很小,只包含几个在序列上面进行简单数学运算的模板函数
  4. < f u n c t i o n a l > <functional> <functional>定义了一些模板类,用以声明函数对象

5.1 常用遍历算法

学习目标:掌握常用的遍历算法

算法简介:

  1. for_each // 遍历容器
  2. transform // 搬运容器到另一个容器中

5.1.1 for_each

功能描述:实现遍历容器

函数原型:for_each(iterator beg, iterator end, _func);

  1. // 遍历算法,遍历容器元素
  2. // beg 开始迭代器
  3. // end 结束迭代器
  4. // _func 函数或者函数对象

示例:

#include<iostream>
using namespace std;
#include<functional>				// 内建函数对象头文件
#include<vector>
#include<algorithm>
#include<functional>


// 常用遍历算法 for_each

// 普通函数
void pirnt01(int val)
{
	cout << val << "  ";
}

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

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

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

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


int main()
{
	test01();

	system("pause");
	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
  • 47
  • 48
  • 49

总结:for_each在实际开发中是最常用的遍历算法,需要熟练掌握

5.1.2 transform

功能描述:搬运容器到另一个容器中

函数原型:transform(iterator beg1, iterator end1, iterator beg2, _func)

  1. beg1: 源容器开始迭代器
  2. end1:源容器结束迭代器
  3. beg2:目标容器开始迭代器
  4. _func:函数或者函数对象

示例:

#include<iostream>
using namespace std;
#include<functional>				// 内建函数对象头文件
#include<vector>
#include<algorithm>
#include<functional>


// 常用遍历算法transform

class Transform
{
public:
	int operator()(int v)
	{
		return v+100;
	}
};

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

void test01()
{
	vector<int>v;

	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	vector<int>vTarget;			// 目标容器
	vTarget.resize(v.size());			// 目标容器 需要提前开辟空间

	transform(v.begin(), v.end(), vTarget.begin(), Transform());

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


}

int main()
{
	test01();

	system("pause");
	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
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55

总结:搬运的目标容器必须要提前开辟空间,否则无法正常搬运

5.1 常用查找算法

学习目标:掌握常用的查找算法

算法简介:

  1. find // 查找元素
  2. find_if // 按条件查找元素
  3. adjacent_find // 查找相邻重复元素
  4. binary_search // 二分查找法
  5. count // 统计元素个数
  6. count_if // 按条件统计元素个数

5.2.1 find

功能描述:查找指定元素,找到返回指定元素的迭代器,找不到返回结束迭代器end()

函数原型:find(iterator beg, iterator end, value)

  1. 按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置
  2. beg // 开始迭代器
  3. end // 结束迭代器
  4. value // 查找的元素

示例:

#include<iostream>
using namespace std;
#include<functional>				// 内建函数对象头文件
#include<vector>
#include<algorithm>
#include<functional>
#include<string>


// 常用的查找算法
// find

// 查找 内置数据类型
void test01()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	// 查找 容器中 是否有5这个元素
	vector<int>::iterator it = find(v.begin(), v.end(), 5);

	if (it == v.end())
	{
		cout << "没有找到!" << endl;
	}
	else
	{
		cout << "找到:" << *it << endl;
	}
}


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

	// 重载 == 底层find知道如何对比Person数据类型
	bool operator==(const Person& p)
	{
		if (this->m_Name == p.m_Name && this->m_Age == p.m_Age)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	string m_Name;
	int m_Age;
};

// 查找 自定义数据类型
void test02()
{
	vector<Person>v;
	// 创建数据
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);

	// 放入到容器中
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	Person pp("bbb", 20);

	vector<Person>::iterator it = find(v.begin(), v.end(), pp);
	if (it == v.end())
	{
		cout << "没有找到!" << endl;
	}
	else
	{
		cout << "找到:姓名:" << it->m_Name <<"\t年龄:"<<it->m_Age<< endl;
	}
	

}

int main()
{
	// test01();
	test02();

	system("pause");
	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
  • 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
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99

总结:利用find可以在容器中找到指定的元素,返回值是迭代器

5.2.2 find_if

功能描述:按条件查找元素

函数原型:find_if(iterator beg, iterator end, _Pred)

  1. 按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置
  2. beg:开始迭代器
  3. end:结束迭代器
  4. _Pred函数或者谓词(返回bool类型的仿函数)

示例:

#include<iostream>
using namespace std;
#include<functional>				// 内建函数对象头文件
#include<vector>
#include<algorithm>
#include<functional>
#include<string>


// 常用的查找算法 find_if

// 1. 查找内置数据类型
class GreaterFive
{
public:
	bool operator()(int val)
	{
		return val > 5;
	}
};
void test01()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

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

	if (it == v.end())
	{
		cout << "没有找到" << endl;
	}
	else
	{
		cout << "找打大于5的数字为:" << *it << endl;
	}
}

// 2. 查找自定义数据类型
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
	string m_Name;
	int m_Age;
};

class Greater20
{
public:
	bool operator()(Person& p)
	{
		return p.m_Age > 20;
	}
};

void test02()
{
	vector<Person>v;
	
	// 创建数据
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);
	Person p5("eee", 50);

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

	// 找年龄大于20的人
	vector<Person>::iterator it = find_if(v.begin(), v.end(), Greater20());
	if (it == v.end())
	{
		cout << "没有找到" << endl;
	}
	else
	{
		cout << "找到姓名:" << it->m_Name << "\t年龄:" << it->m_Age << endl;
	}


}

int main()
{
	// test01();
	test02();

	system("pause");
	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
  • 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
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101

5.2.3 adjacent_find

功能描述:查找相邻重复元素

函数原型:adjacent_find(iterator beg, iterator end);

  1. 查找相邻重复元素,返回相邻元素的第一个位置的迭代器
  2. beg:开始迭代器
  3. end:结束迭代器
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>


// 常用查找算法 adjacent_find
void test01()
{
	vector<int>v;
	v.push_back(0);
	v.push_back(2);
	v.push_back(0);
	v.push_back(3);
	v.push_back(1);
	v.push_back(4);
	v.push_back(3);
	v.push_back(3);

	vector<int>::iterator pos = adjacent_find(v.begin(), v.end());
	if (pos == v.end())
	{
		cout << "未找到相邻重复元素" << endl;
	}
	else
	{
		cout << "找到相邻重复元素:" << *pos << endl;
	}

}

int main()
{
	test01();


	system("pause");
	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

总结:面试题中如果出现查找相邻重复元素,记得用STL中的adjacent_find算法

5.2.4 binary_search

功能描述:查找指定元素是否存在

函数原型:bool binary_search(iterator beg, iterator end, value);

  1. 查找指定的元素,查到 返回true 否则返回false
  2. 注意:在无序序列中不可以用
  3. beg 开始迭代器
  4. end 结束迭代器
  5. value 查找的元素

示例:

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

// 常用查找算法 binary_search
void test01()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	// v.push_back(2);				// 如果是无序序列,结果未知
	// 查找容器中是否有9 元素
	bool ret = binary_search(v.begin(), v.end(), 9);
	if (ret)
	{
		cout << "找到了元素" << endl;
	}
	else
	{
		cout << "没找到" << endl;
	}

}

int main()
{

	test01();

	system("pause");
	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

总结:二分查找法查找效率很高,值得注意的是查找的容器中元素必须是有序序列

5.2.5 count

统计描述:统计元素个数

函数原型:count(iterator beg, iterator end, value);

  1. 统计元素出现次数
  2. beg开始迭代器
  3. end结束迭代器
  4. value统计的元素
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>

// 常用查找算法 count

// 1. 统计内置数据类型
void test01()
{
	vector<int>v;
	v.push_back(10);
	v.push_back(40);
	v.push_back(30);
	v.push_back(40);
	v.push_back(20);
	v.push_back(40);

	int num = count(v.begin(), v.end(), 40);
	cout << "40的元素个数为:" << num << endl;


}

// 2. 统计自定义数据类型
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
	bool operator==(const Person &p)
	{
		if (this->m_Age == p.m_Age)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	string m_Name;
	int m_Age;
};

void test02()
{
	vector<Person>v;

	Person p1("刘备", 35);
	Person p2("关羽", 35);
	Person p3("张飞", 35);
	Person p4("赵云", 30);
	Person p5("曹操", 40);

	// 将人员插入到容器中
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);


	Person p("诸葛亮", 35);
	int num = count(v.begin(), v.end(), p);
	cout << "和诸葛亮同岁数的人员个数为:" << num << endl;


}


int main()
{

	//test01();
	test02();

	system("pause");
	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
  • 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
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83

总结:统计自定义数据类型的时候,需要配合重载operator==

5.2.6 count_if

功能描述:按条件统计元素个数

函数原型:count_if(iterator beg, iterator end, _Pred);

  1. 按条件统计元素出现次数
  2. beg:开始迭代器
  3. end:结束迭代器
  4. _Pred:谓词

示例:

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

// 常用查找算法 count_if

// 统计内置数据类型
class Greater20
{
public:
	bool operator()(int val)
	{
		return val > 20;
	}
};
void test01()
{
	vector<int>v;
	v.push_back(10);
	v.push_back(40);
	v.push_back(30);
	v.push_back(20);
	v.push_back(40);
	v.push_back(20);

	int num = count_if(v.begin(), v.end(), Greater20());
	cout << "大于20的元素个数为:" << num << endl;

}

// 统计自定义数据类型
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	string m_Name;
	int m_Age;
};

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


void test02()
{
	vector<Person>v;
	Person p1("刘备", 35);
	Person p2("关羽", 35);
	Person p3("张飞", 35);
	Person p4("赵云", 40);
	Person p5("曹操", 20);

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

	// 统计 大于20岁人员个数
	int num = count_if(v.begin(), v.end(), AgeGreater20());
	cout << "大于20岁的人员个数为:" << num << endl;


}


int main()
{

	//test01();  
	test02();

	system("pause");
	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
  • 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
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87

5.3 常用排序算法

学习目标:掌握常用的排序算法

算法简介:

  1. sort // 对容器内元素进行排序
  2. random_shuffle // 洗牌 指定范围内的元素随机调整次序
  3. merge // 容器元素合并,并存储到另一容器中
  4. reverse // 反转指定范围的元素

5.3.1 sort

功能描述:对容器内元素进行排序

函数原型:sort(iterator beg, iterator end, _Pred);

  1. 按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置
  2. beg:开始迭代器
  3. end:结束迭代器
  4. _Pred:谓词

示例:

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

// 常用排序算法
void MyPrint(int val)
{
	cout << val << "  ";
}
void test01()
{
	vector<int>v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

	// 利用sort进行升序
	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;


}


int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结:sort属于开发中最常用的算法之一,需熟练掌握

5.3.2 random_shuffle

功能描述:洗牌 指定范围内的元素随机调整次序

函数原型:random_shuffle(iterator beg, iterator end);

  1. 指定范围内的元素随机调整次序
  2. beg:开始迭代器
  3. end:结束迭代器

示例:

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

// 常用排序算法 random_shuffle
void MyPrint(int val)
{
	cout << val << " ";
}

void test01()
{
	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);
	cout << endl;


}




int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结:random_shuffle洗牌算法比较实用,使用时记得加随机数种子

5.3.3 merge

功能描述:两个容器元素合并,并存储到另一容器中

函数原型:merge(iterator beg1, iterator end1, iterator beg2,iterator end2, iterator dest);

  1. 容器元素合并,并存储到另一容器中
  2. 注意:两个容器必须是有序的
  3. beg1:容器1开始迭代器
  4. end1:容器1结束迭代器
  5. beg2:容器2开始迭代器
  6. end2:容器2结束迭代器
  7. dest:目标容器开始迭代器

示例:

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

// 常用排序算法 merge
void myPrint(int val)
{	
	cout << val << " ";
}
void test01()
{
	vector<int>v1;
	vector<int>v2;

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

	// 目标容器
	vector<int>vTarget;

	// 提前给目标容器分配空间
	vTarget.resize(v1.size() + v2.size());

	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	for_each(vTarget.begin(), vTarget.end(),myPrint);
	cout << endl;

}

int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结:merge合并的两个容器必须是有序序列。

5.3.4 reverse

功能描述:将容器内元素进行反转

函数原型:reverse(iterator beg, iterator end);

  1. 反抓指定范围的元素
  2. beg:开始迭代器
  3. end:结束迭代器

示例:

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


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

// 常用排序算法 reverse
void test01()
{
	vector<int>v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

	cout << "反转前:" << endl;
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;

	cout << "反转后:" << endl;
	reverse(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;


}


int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结:reverse反转区间内元素,面试题可能涉及到

5.4 常用拷贝和替换方法

学习目标:掌握常用的拷贝和替换算法

算法简介:

  1. copy:容器内只当范围的元素拷贝到另一容器中
  2. replace:将容器中指定范围的旧元素修改为新元素
  3. replace_if:容器内指定范围满足条件的元素替换为新元素
  4. swap:互换两个容器的元素

5.4.1 copy

功能描述:容器内指定范围的元素拷贝到另一容器中

函数原型:copy(iterator beg, iterator end, iterator dest);

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


// 常用拷贝和替换算法 copy

void myPrint(int val)
{
	cout << val << " ";

}
void test01()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}

	vector<int>v2;
	v2.resize(v1.size());
	copy(v1.begin(), v1.end(), v2.begin());

	for_each(v2.begin(), v2.end(), myPrint);
	cout << endl;  


}


int main()
{

	test01();  
	//test02();

	system("pause");
	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

利用copy算法在拷贝时,目标容器记得提前开辟空间

5.4.2 replace

功能描述:将容器内指定范围的旧元素修改为新元素

函数原型:replace(iterator beg, iterator end, oldvalue, newvalue);

  1. 将区间内旧元素 替换成 新元素
  2. beg 开始迭代器
  3. end 结束迭代器
  4. oldvalue 旧元素
  5. newvalue 新元素

示例;

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


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

// 常用拷贝和替换方法 replace
void test01()
{
	vector<int>v;
	v.push_back(20);
	v.push_back(30);
	v.push_back(50);
	v.push_back(30);
	v.push_back(40);
	v.push_back(20);
	v.push_back(10);
	v.push_back(20);

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

	// 将20 替换成 2000
	replace(v.begin(), v.end(), 20, 2000);
	cout << "替换后:" << endl;
	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;


}


int main()
{

	test01();  
	//test02();

	system("pause");
	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
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

总结:replace会替换区间内满足条件的元素

5.4.3 replace_if

功能描述:将区间内满足条件的元素,替换成指定元素

函数原型:replace_if(iterator beg, iterator end, _pred, newvalue);

  1. 按条件替换元素,满足条件的替换成指定元素
  2. beg:开始迭代器
    3 end:结束迭代器
  3. _pred:谓词
  4. newvalue:替换的新元素

示例:

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



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

class Greater30
{
public:
	bool operator()(int val)
	{
		return val >= 30;
	}
};

// 常用的拷贝和替换算法 replace_if
void test01()
{
	vector<int>v;
	v.push_back(10);
	v.push_back(40);
	v.push_back(20);
	v.push_back(40);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(30);

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

	// 将大于等于30 替换为 3000
	replace_if(v.begin(), v.end(), Greater30(), 3000);
	cout << "替换后:" << endl;
	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;



}


int main()
{

	test01();  
	//test02();

	system("pause");
	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
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63

总结:replace_if按条件查找,可以利用仿函数灵活筛选满足的条件

5.4.4 swap

功能描述:互换两个容器的元素

函数原型:swap(container c1, container c2);

  1. 互换两个容器的元素
  2. c1容器1
  3. c2容器2

示例:

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


// 常用拷贝和替换方法 swap
void myPrint(int val)
{
	cout << val << "  ";
}
void test01()
{
	vector<int>v1;
	vector<int>v2;

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

	cout << "交换前:" << endl;
	for_each(v1.begin(), v1.end(), myPrint);
	cout << endl;

	for_each(v2.begin(), v2.end(), myPrint);
	cout << endl;

	swap(v1, v2);

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

	for_each(v2.begin(), v2.end(), myPrint);
	cout << endl;

}

int main()
{

	test01();  
	//test02();

	system("pause");
	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
  • 47
  • 48
  • 49
  • 50

总结:swap交换容器时,注意交换的容器要同种类型

5.5 常用算术生成算法

学习目标:掌握常用的算术生成算法

注意:算术生成算法属于小型算法,使用时包含的头文件为KaTeX parse error: Expected 'EOF', got '#' at position 1: #̲include<numeric…

算法简介:

  1. accumulate:计算容器元素累计总和
  2. fill:向容器中添加元素

5.5.1 accumulate

功能描述:计算区间内容器元素累计总和

函数原型:accumulate(iterator beg, iterator end, value);

  1. 计算容器元素累计总和
  2. beg开始迭代器
  3. end结束迭代器
  4. value:起始值

示例:

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


// 常用算术生成算法
void test01()
{
	vector<int>v;
	for (int i = 0; i <= 100; i++)
	{
		v.push_back(i);
	}

	// 参数3 起始累加值
	int total = accumulate(v.begin(), v.end(), 0);
	cout << "total = " << total << endl;

}



int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结:accumulate使用时头文件注意时numeric,这个算法很实用

5.5.2 fill

功能描述:向容器中填充指定的元素

函数原型:fill(iterator beg, iterator end, value)

  1. 向容器中填充元素
  2. beg开始迭代器
  3. end结束迭代器
  4. value填充的值

示例:

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


// 常用算术生成算法
void myPrint(int val)
{
	cout << val << "  ";
}
void test01()
{
	vector<int>v;
	v.resize(10);

	// 后期重新填充
	fill(v.begin(), v.end(), 100);

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


int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结:利用fill可以将容器区间内元素填充为指定的值

5.6 常用集合算法

学习目标:掌握常用的集合算法

算法简介:

  1. set_intersection // 求两个容器的交集
  2. set_union // 求两个容器的并集
  3. set_difference // 求两个容器的差集

5.6.1 set_intersection

功能描述:求两个容器的交集

函数原型:set_intersection(iterator beg1, iteration end1, iteration beg2, iteration end2, iteration dest)

  1. 求两个集合的交集
  2. 注意:两个集合必须是有序序列
  3. beg1:容器1开始迭代器
  4. end1:容器1结束迭代器
  5. beg2:容器2开始迭代器
  6. end2:容器2结束迭代器
  7. dest:目标容器开始迭代器

示例:

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


 // 常用集合算法 set_intersection
void myPrint(int val)
{
	cout << val << "  ";

}
void test01()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i + 5);
	}

	vector<int>vTarget;
	
	// 目标容器需要提前开辟空间
	// 最特殊情况 大容器包含小容器 开辟空间 取小容器的size即可
	vTarget.resize(min(v1.size(), v2.size()));

	// 获取交集
	vector<int>::iterator itEnd =  set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());


	for_each(vTarget.begin(), itEnd, myPrint);
	cout << endl;
}


int main()
{

	test01();  
	//test02();

	system("pause");
	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
  • 47
  • 48

总结:

  1. 求交集的两个集合必须时有序序列
  2. 目标容器开辟空间需要从两个容器中取最小值
  3. set_intersection返回值就是交集中最后一个元素的位置

5.6.2 set_union

功能描述:求两个集合的并集

函数原型:set_union(iterator beg1, iteration end1, iteration beg2, iteration end2, iteration dest)

  1. 求两个集合的并集
  2. 注意:两个集合必须是有序序列
  3. beg1:容器1开始迭代器
  4. end1:容器1结束迭代器
  5. beg2:容器2开始迭代器
  6. end2:容器2结束迭代器
  7. dest:目标容器开始迭代器

示例:

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


 // 常用集合算法 set_union
void myPrint(int val)
{
	cout << val << "  ";

}
void test01()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i + 5);
	}

	vector<int>vTarget;
	
	// 目标容器需要提前开辟空间
	// 最特殊情况  两个容器没有并集 并集就是两个容器size相加 
	vTarget.resize(v1.size()+ v2.size());

	// 获取交集
	vector<int>::iterator itEnd =  set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());


	for_each(vTarget.begin(), itEnd, myPrint);
	cout << endl;
}


int main()
{

	test01();  
	//test02();

	system("pause");
	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
  • 47
  • 48

总结:

  1. 求并集的两个集合必须时有序序列
  2. 目标容器开辟空间需要从两个容器中取和
  3. set_union返回值就是交集中最后一个元素的位置

5.6.3 set_difference

功能描述:求两个集合的差集

函数原型: set_difference(iterator beg1, iteration end1, iteration beg2, iteration end2, iteration dest)

  1. 求两个集合的差集
  2. 注意:两个集合必须是有序序列
  3. beg1:容器1开始迭代器
  4. end1:容器1结束迭代器
  5. beg2:容器2开始迭代器
  6. end2:容器2结束迭代器
  7. dest:目标容器开始迭代器

示例:

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


 // 常用集合算法 set_difference
void myPrint(int val)
{
	cout << val << "  ";

}
void test01()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i + 5);
	}

	vector<int>vTarget;
	
	// 目标容器需要提前开辟空间
	// 最特殊情况  两个容器没有交集 取两个容器中大的size作为目标容器开辟空间
	vTarget.resize(max(v1.size(),v2.size()));

	// 获取交集
	vector<int>::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	cout << "v1和v2的差集为:" << endl;
	for_each(vTarget.begin(), itEnd, myPrint);
	cout << endl;
}


int main()
{

	test01();  
	//test02();

	system("pause");
	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
  • 47
  • 48

总结:

  1. 求差集的两个集合必须时有序序列
  2. 目标容器开辟空间需要从两个容器中取最大值
  3. set_difference返回值就是交集中最后一个元素的位置
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/运维做开发/article/detail/919450?site
推荐阅读
相关标签
  

闽ICP备14008679号