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_iterator、end_iterator 和 value,其中 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);