C++算法详解

C++是一种广泛使用的编程语言，它支持多种编程范式，如面向对象、泛型和函数式编程。C++也提供了一些标准库，其中包含了许多常用的数据结构和算法，如vector、string、map、sort等。本文将介绍一些C++中的基本算法，以及它们的用法和效率。

算法是一种解决特定问题的步骤或规则。在C++中，算法通常是一些函数模板，它们可以对不同类型的容器或迭代器进行操作。C++标准库中的算法分为几类，如非修改性算法、修改性算法、排序算法、数值算法等。下面我们来看一些例子。

非修改性算法是指不改变容器或迭代器中的元素的算法，如find、count、equal等。例如，我们可以使用find算法来查找一个vector中是否存在某个元素：

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

int main() {
vector<int> v = {1, 2, 3, 4, 5};
int x = 3;
// find返回一个迭代器，指向第一个等于x的元素，如果没有找到，则返回v.end()
auto it = find(v.begin(), v.end(), x);
if (it != v.end()) {
cout << "Found " << x << " at position " << it - v.begin() << endl;
} else {
cout << "Not found " << x << endl;
}
return 0;
}

输出：

1	Found 3 at position 2

修改性算法是指改变容器或迭代器中的元素的算法，如copy、reverse、rotate等。例如，我们可以使用reverse算法来反转一个string：

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

int main() {
string s = "Hello world";
// reverse接受两个迭代器，表示要反转的范围
reverse(s.begin(), s.end());
cout << s << endl;
return 0;
}

输出：

1	dlrow olleH

排序算法是指对容器或迭代器中的元素进行排序的算法，如sort、stable_sort、partial_sort等。例如，我们可以使用sort算法来对一个vector中的元素进行升序排序：

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

int main() {
vector<int> v = {5, 4, 3, 2, 1};
// sort接受两个迭代器，表示要排序的范围，默认使用<运算符比较元素
sort(v.begin(), v.end());
for (int x : v) {
cout << x << " ";
}
cout << endl;
return 0;
}

输出：

1 2 3 4 5

数值算法是指对容器或迭代器中的元素进行数学运算的算法，如accumulate、inner_product、adjacent_difference等。例如，我们可以使用accumulate算法来计算一个vector中所有元素的和：

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

int main() {
vector<int> v = {1, 2, 3, 4, 5};
// accumulate接受两个迭代器，表示要累加的范围，以及一个初始值，默认使用+运算符累加元素
int sum = accumulate(v.begin(), v.end(), 0);
cout << sum << endl;
return 0;
}

输出：

以上就是本文介绍的一些C++中的基本算法，更多的算法可以参考相关文献