C++ 算法

C++ 算法库

在前面的章节中,你已经了解到数据结构(如向量、列表等)用于存储和组织数据。

算法则用于通过排序、搜索和操作数据结构来解决问题。

<algorithm> 库提供了许多有用的函数,可以通过迭代器来执行这些任务。

要使用这些函数,你必须包含 <algorithm> 头文件:

// 包含算法库
#include <algorithm>

排序算法

要对数据结构中的元素进行排序,你可以使用 sort() 函数。

sort() 函数以迭代器作为参数(通常是由 begin() 返回的起始迭代器和由 end() 返回的结束迭代器):

实例

// 创建一个名为 cars 的字符串向量
vector<string> cars = {"Volvo", "BMW", "Ford", "Mazda"};

// 按字母顺序排序 cars
sort(cars.begin(), cars.end());

亲自试一试

默认情况下,元素按升序排列。在上面的示例中,由于元素是字符串,所以按字母顺序排序。

如果我们有一个整数向量,则会按数值排序:

实例

// 创建一个名为 numbers 的整数向量
vector<int> numbers = {1, 7, 3, 5, 9, 2};

// 按数值排序 numbers
sort(numbers.begin(), numbers.end());

亲自试一试

要反转排序顺序,可以使用 rbegin()rend() 代替 begin()end()

实例

// 创建一个名为 numbers 的整数向量
vector<int> numbers = {1, 7, 3, 5, 9, 2};

// 按数值降序排序 numbers
sort(numbers.rbegin(), numbers.rend());

亲自试一试

如果只想对特定元素进行排序,可以这样写:

实例

// 创建一个名为 numbers 的整数向量
vector<int> numbers = {1, 7, 3, 5, 9, 2};

// 从第四个元素开始按数值排序(仅排序 5、9 和 2)
sort(numbers.begin() + 3, numbers.end());

亲自试一试

搜索算法

要在向量中搜索特定元素,可以使用 find() 函数。

它接受三个参数:start_iteratorend_iteratorvalue,其中 value 是要搜索的值:

实例

在 "numbers" 中搜索数字3:

// 创建一个名为 numbers 的整数向量
vector<int> numbers = {1, 7, 3, 5, 9, 2};

// 搜索数字 3
auto it = find(numbers.begin(), numbers.end(), 3);

亲自试一试

要搜索第一个大于特定值的元素,可以使用 upper_bound() 函数:

实例

在 "numbers" 中查找第一个大于 5 的值:

// 创建一个名为 numbers 的整数向量
vector<int> numbers = {1, 7, 3, 5, 9, 2};

// 将向量按升序排序
sort(numbers.begin(), numbers.end());

// 在已排序的向量中查找第一个大于 5 的值
auto it = upper_bound(numbers.begin(), numbers.end(), 5);

亲自试一试

upper_bound() 函数通常用于已排序的数据结构。这就是为什么我们在上面的示例中首先对向量进行排序。

要查找向量中的最小元素,可以使用 min_element() 函数:

实例

// 创建一个名为 numbers 的整数向量
vector<int> numbers = {1, 7, 3, 5, 9, 2};

// 查找最小的数字
auto it = min_element(numbers.begin(), numbers.end());

亲自试一试

要查找最大的元素,可以使用 max_element() 函数:

实例

// 创建一个名为 numbers 的整数向量
vector<int> numbers = {1, 7, 3, 5, 9, 2};

// 查找最大的数字
auto it = max_element(numbers.begin(), numbers.end());

亲自试一试

修改算法

要将元素从一个向量复制到另一个向量,可以使用 copy() 函数:

实例

将元素从一个向量复制到另一个向量:

// 创建一个名为 numbers 的整数向量
vector<int> numbers = {1, 7, 3, 5, 9, 2};

// 创建一个名为 copiedNumbers 的向量,用于存储6个整数
vector<int> copiedNumbers(6);

// 将元素从 numbers 复制到 copiedNumbers
copy(numbers.begin(), numbers.end(), copiedNumbers.begin());

亲自试一试

要用一个值填充向量中的所有元素,可以使用 fill() 函数:

实例

用值 35 填充 numbers 向量中的所有元素:

// 创建一个名为 numbers 的向量,用于存储6个整数
vector<int> numbers(6);

// 用值 35 填充 numbers 向量中的所有元素
fill(numbers.begin(), numbers.end(), 35);

亲自试一试