9. 入门并实践STL——algorithm篇

1. How to use?

#include<algorithm>
using namespace std;

2. 常用函数解析

1. max(x, y), min(x, y), abs(i)

• max(x, y), min(x, y): 参数必须是两个，类型可以是浮点数，返回值的类型根据参数类型确定。
• abs(i): x必须是整数，浮点型的绝对值请用math头文件下的fabs

2. swap(x, y)

• 交换x和y的值

3. reverse(it, it2)

• 可以将数组指针在[it, it2)之间的元素或者容器的迭代器在[it, it2)范围内的元素进行反转

4. next_permutation()

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

int a[4] = {1, 2, 3};
do {
    printf("%d%d%d\n", a[0], a[1], a[2]);
} while(next_permutation(a, a+3);

5. fill()

• fill(arr, arr+4, 123); // 将arr[0]~arr[3]均赋值123

6. sort()

• 它会根据具体情形使用不同的排序算法，效率较高。
• sort(首元素地址(必填), 尾元素地址的下一个地址(必填), 比较函数(非必填));
• 如何实现比较函数

bool cmp(int a, int b) {
    return a > b; // 可以理解为当a>b时把a放在b前面
}
- 记忆方法：如果要把数据从小到大排列，那么就用<，因为a<b就是左小右大
- 容器的排序，想set，map这种容器是用，元素本身有序，红黑树实现的，元素本身有序，故不允许使用sort排序。

7. lower_bound()和upper_bound()

• 他们都需要使用在一个有序数组或容器中
• lower_bound(first, end, val)：寻找在数组或容器的[first, end)范围内第一个值大于等于val的元素的位置，如果是数组返回指针，如果是容器返回迭代器。
• upper_bound(first, end, val): 。。。第一个大于val。。。

习题

题目

• 全排列

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

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main() {
    string str;
    while(cin>>str) {
        do{
            cout<<str<<endl;
        } while(next_permutation(str.begin(), str.end()));
        cout<<endl;
    }
    return 0;
}

• 数组逆置
  • 注意输入的字符串可能会有空格。
  • 所以输入不能使用cin，的使用getline

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

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main() {
    string str;
    while(getline(cin,str)) {
        reverse(str.begin(), str.end());
        cout<<str<<endl;
    }
    return 0;
}