C++基础知识【算法库 <algorithm>】

C++ 标准库中的 <algorithm> 头文件提供了一组用于操作容器（如数组、向量、列表等）的算法。这些算法包括排序、搜索、复制、比较等，它们是编写高效、可重用代码的重要工具。

<algorithm> 头文件定义了一组模板函数，这些函数可以应用于任何类型的容器，只要容器支持迭代器。这些算法通常接受两个或更多的迭代器作为参数，表示操作的起始和结束位置。
语法

大多数 <algorithm> 中的函数都遵循以下基本语法：

1. algorithm_name(container.begin(), container.end(), ...);

复制代码

这里的 container 是一个容器对象，begin() 和 end() 是容器的成员函数，返回指向容器开始和结束的迭代器。

实例
1. 排序算法

函数：sort

定义：对容器中的元素进行排序。

语法：

1. sort(container.begin(), container.end(), compare_function);

复制代码

其中 compare_function 是一个可选的比较函数，用于自定义排序方式。

实例

1. #include <algorithm>
   
2. #include <vector>
   
3. #include <iostream>
   
4. 
   
5. int main() {
   
6.     std::vector<int> numbers = {5, 2, 9, 1, 5, 6};
   
7.     std::sort(numbers.begin(), numbers.end());
   
8. 
   
9.     for (int num : numbers) {
   
10.         std::cout << num << " ";
    
11.     }
    
12.     std::cout << std::endl;
    
13. 
    
14.     return 0;
    
15. }

复制代码

输出结果：

1 2 5 5 6 9

2. 搜索算法

函数：find

定义：在容器中查找与给定值匹配的第一个元素。

语法：

1. auto it = find(container.begin(), container.end(), value);

复制代码

如果找到，it 将指向匹配的元素；如果没有找到，it 将等于 container.end()。

1. #include <algorithm>
   
2. #include <vector>
   
3. #include <iostream>
   
4. 
   
5. int main() {
   
6.     std::vector<int> numbers = {1, 2, 3, 4, 5};
   
7.     auto it = std::find(numbers.begin(), numbers.end(), 3);
   
8. 
   
9.     if (it != numbers.end()) {
   
10.         std::cout << "Found: " << *it << std::endl;
    
11.     } else {
    
12.         std::cout << "Value not found." << std::endl;
    
13.     }
    
14. 
    
15.     return 0;
    
16. }

复制代码

输出结果：
Found: 3

3. 复制算法

函数：copy

定义：将一个范围内的元素复制到另一个容器或数组。

语法：

1. copy(source_begin, source_end, destination_begin);

复制代码

1. #include <algorithm>
   
2. #include <vector>
   
3. #include <iostream>
   
4. 
   
5. int main() {
   
6.     std::vector<int> source = {1, 2, 3, 4, 5};
   
7.     int destination[5];
   
8.     std::copy(source.begin(), source.end(), destination);
   
9. 
   
10.     for (int i = 0; i < 5; ++i) {
    
11.         std::cout << destination[i] << " ";
    
12.     }
    
13.     std::cout << std::endl;
    
14. 
    
15.     return 0;
    
16. }

复制代码

输出结果：

1 2 3 4 5

1.sort 函数

        sort 函数是 algorithm 中的排序函数，相较于 C stdlib 中的 qsort 函数，用法更简单，也更广泛，同时内部实现也要更复杂。

        对数组使用 sort 函数：

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. 
   
5. int main () {
   
6.     int arr [10] = { 2,4,1,6,7,5,8,10,3,9 };
   
7. 
   
8.     cout << "排序前的数组：";
   
9.     for (int num : arr) {
   
10.         cout << num << " ";
    
11.     }
    
12.     cout << endl;
    
13. 
    
14.     sort (arr , arr + 10);
    
15. 
    
16.     cout << "排序后的数组：";
    
17.     for (int num : arr) {
    
18.         cout << num << " ";
    
19.     }
    
20.     cout << endl;
    
21. 
    
22.     system ("pause");
    
23.     return 0;
    
24. }

复制代码

注意：这里的参数是数组的地址。        

        对容器 vector 使用 sort 函数：

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. 
   
5. int main () {
   
6.     vector<int> arr = { 2,4,1,6,7,5,8,10,3,9 };
   
7. 
   
8.     cout << "排序前的数组：";
   
9.     for (int num : arr) {
   
10.         cout << num << " ";
    
11.     }
    
12.     cout << endl;
    
13. 
    
14.     sort (arr.begin () , arr.end ());
    
15. 
    
16.     cout << "排序后的数组：";
    
17.     for (int num : arr) {
    
18.         cout << num << " ";
    
19.     }
    
20.     cout << endl;
    
21. 
    
22.     system ("pause");
    
23.     return 0;
    
24. }

复制代码

2. reverse 函数

  reverse 函数是 algorithm 中的反转函数，常适用于字符串，但不仅仅可以对字符串使用。

        对 string 使用 reverse 函数：

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. 
   
5. int main () {
   
6.     string s = "Hello world";
   
7. 
   
8.     cout << "反转前的字符串：";
   
9.     cout << s << endl;
   
10. 
    
11.     reverse (s.begin () , s.end ());
    
12. 
    
13.     cout << "反转后的字符串：";
    
14.     cout << s << endl;
    
15. 
    
16.     system ("pause");
    
17.     return 0;
    
18. }

复制代码

3. max & min 函数

        max & min 函数是用来返回两变量之间较大（小）者的函数。

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. 
   
5. int main () {
   
6.     int a , b;
   
7.     a = 1;
   
8.     b = 10;
   
9. 
   
10.     cout << "a：" << a << "，" << "b：" << b << endl;
    
11.     cout << "较大者：" << max (a , b) << endl;
    
12.     cout << "较小者：" << min (a , b) << endl;
    
13. 
    
14.     system ("pause");
    
15.     return 0;
    
16. }

复制代码

4. max_element & min_element 函数

        该函数用于获取数组或容器中最大（小）的元素。

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. 
   
5. int main () {
   
6.     vector<int> arr = { 1,2,3,4,5,6,7,8,9,0 };
   
7.    
   
8.     cout << "数组：";
   
9.     for (int num : arr) {
   
10.         cout << num << " ";
    
11.     }
    
12.     cout << endl;
    
13. 
    
14.     cout << "最大者：";
    
15.     cout << *max_element (arr.begin () , arr.end ()) << endl;
    
16.     cout << "最小者：";
    
17.     cout << *min_element (arr.begin () , arr.end ()) << endl;
    
18. 
    
19.     system ("pause");
    
20.     return 0;
    
21. }

复制代码

注意：该函数的返回值是元素的地址（对于容器，返回迭代器）。

5. binary_search 函数

        函数一共三个参数，第一二个参数参照 sort 的参数，第三个参数是需要寻找的 key。

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <vector>
   
4. 
   
5. using namespace std;
   
6. 
   
7. int main () {
   
8.     vector<int> haystack{ 1, 3, 4, 5, 9 };
   
9.     vector<int> needles{ 1, 2, 3 };
   
10. 
    
11.     for (const auto needle : needles) {
    
12.         cout << "正在搜索 " << needle << '\n';
    
13.         if (binary_search (haystack.begin () , haystack.end () , needle))
    
14.             cout << "找到了 " << needle << '\n';
    
15.         else
    
16.             cout << "没找到！\n";
    
17.     }
    
18. 
    
19.     system ("pause");
    
20.     return 0;
    
21. }

复制代码