【C++标准模板库】algorithm头文件下的常用函数

1、max()最大值、min()最小值、abs()绝对值

顾名思义，注意max()和min()的参数必须是两个。
abs()的参数是一个，但必须是整数，浮点数的绝对值用math头文件下的fabs。

	int x, y,z;
	x = -11;
	y = 12;
	z = 9;
	//三个数比较时
	cout << "最大值：" << max(abs(x), max(y, z))<<endl;
	cout << "最小值：" << min(abs(x), min(y, z)) << endl;

2、swap()交换两个值

	y = 12;
	z = 9;
	swap(y, z);
	cout << "z:" << z << "\ty:" << y << endl;

3、reverse()反转

reverse(it,it2)可以将数组指针在[it,it2)之间的元素或容器的迭代器在[it,it2)范围内的元素进行反转。（字符串也可以使用）

	int a[10] = { 0,1,2,3,4,5,6,7,8,9 };
	reverse(a, a + 5);
	for (int i = 0;i < 10;i++) {
		cout << a[i] << "\t";
	}

4、next_permutation()

给出一个序列在全排列中的下一个序列。

	int b[3] = { 1,2,3 };
	do {
		cout << "\n" << b[0] <<b[1] << b[2] ;
	} while (next_permutation(b, b + 3));

在到达全排列的最后一个时会返回false，如果使用while会直接跳到下一个序列在输出，会少一个123。所以不能使用while。

5、fill()

把数组或容器中的某一段区间赋为某个相同的值。和memset不同，这里的赋值可以是数组类型对应范围中的任意值。

	int b[3] = { 1,2,3 };
	fill(b, b + 3, 555);
	for (int i = 0;i < 3;i++) {
		cout << b[i] << endl;
	}

sort()排序

默认从小到大排序。

sort(首元素地址(必填),尾元素地址的下一个地址(必填),比较函数(非必填));

	int b[3] = { 3,1,2 };
	sort(b,b+3);
	for (int i = 0;i < 3;i++) {
		cout << b[i] << endl;
	}

比较函数cmp

1、基础数据类型数组排序

如果想要从大到小排序，可以在前面重写cmp

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

2、数据结构的比较

在第一个元素相等的情况下，再按照第二个元素进行排序。

struct node {
	int a;
	int b;
}ssd[3];
bool cmp(node x, node y) {
	if (x.a != y.a) return x.a > y.a;
	else return x.b > y.b;
}
void functionTest() {
	ssd[0].a = 1;
	ssd[0].b = 0;
	ssd[1].a = 4;
	ssd[1].b = 1;
	ssd[2].a = 2;
	ssd[2].b = 8;
	sort(ssd, ssd + 3, cmp);
	for (int i = 0;i < 3;i++) {
		cout << ssd[i].a << "\t" << ssd[i].b << endl;
	}
}

3、容器的比较

只有vector、string、deque可以使用sort。set、map等用红黑树实现的元素本身就有序。
关于容器的内容在另一篇文章：vector、set、map容器

C和C++字符的区别
以vector使用sort为例：

bool cmp(int a, int b) {
	return a > b;
}
void functionTest() {
	vector<int> vi;
	vi.push_back(1);
	vi.push_back(5);
	vi.push_back(2);
	vi.push_back(19);
	vi.push_back(6);
	sort(vi.begin(), vi.end(), cmp);
	for (vector<int>::iterator v = vi.begin();v != vi.end();v++) {
		cout << *v << endl;
	}
}

lower_bound()和upper_bound()

这两个函数需要用在一个有序数组或容器中。
1、lower_bound(first,last,val)：是用来寻找在数组或容器的[first,last)范围内第一个值大于等于val的元素的位置，如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器。
2、upper_bound(first,last,val)：是用来寻找在数组或容器的[first,last)范围内第一个值大于val的元素的位置，如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器。
如果数组或容器中没有需要寻找的元素，则均返回可以插入该元素的位置的指针或迭代器。复杂度均为O(log(last-first)).

void functionTest1() {
	int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int* lowerPos = lower_bound(a, a + 10, -1);
	int* upperPos = upper_bound(a, a + 10, -1);
	cout << "寻找-1：" << lowerPos-a << "\t" << upperPos-a << endl;
	lowerPos = lower_bound(a, a + 10, 1);
	upperPos = upper_bound(a, a + 10, 1);
	cout << "寻找1：" << lowerPos - a << "\t" << upperPos - a << endl;
	lowerPos = lower_bound(a, a + 10, 5);
	upperPos = upper_bound(a, a + 10, 5);
	cout << "寻找5：" << lowerPos - a << "\t" << upperPos - a << endl;
	lowerPos = lower_bound(a, a + 10, 6);
	upperPos = upper_bound(a, a + 10, 6);
	cout << "寻找6：" << lowerPos - a << "\t" << upperPos - a << endl;
	lowerPos = lower_bound(a, a + 10, 4);
	upperPos = upper_bound(a, a + 10, 4);
	cout << "寻找4：" << lowerPos - a << "\t" << upperPos - a << endl;
}

如果知识想获得想查找元素的下标，就可以不使用指针，直接返回值减去数组首地址就行。如果不减去首地址返回的是物理地址。

	int b[10] = { 1,2,2,3,3,3,5,5,5,5 };
	cout << lower_bound(b, b + 10, 3) - b<<"\t" << upper_bound(b, b + 10, 3) - b << endl;

关于C++标准模板库的常见函数、容器的理论知识就分享到这里了，接下来会有一些实践的题分享。
队列和栈