当前位置：首页 > news >正文

泛型算法——只读算法（三）

news 2025/5/1 18:03:01

find

在 C++ 中，std::find是标准库algorithm头文件提供的泛型查找算法，用于在容器或序列中查找特定元素。

函数原型

template <class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value);

● 参数：
  ○ first, last：查找范围的迭代器（左闭右开区间 [first, last)）。
    ○ value：要查找的目标值。
● 返回值：
    ○ 若找到目标值，返回指向该元素的迭代器。
    ○ 若未找到，返回 last（即范围的结束迭代器）。

示例代码：在 vector 中查找整数

#include <algorithm>
#include <vector>
#include <iostream>int main() {std::vector<int> nums = {10, 20, 30, 40, 50};int target = 30;auto it = std::find(nums.begin(), nums.end(), target);if (it != nums.end()) {std::cout << "找到元素 " << *it << "，位置索引：" << std::distance(nums.begin(), it) << std::endl;} else {std::cout << "未找到元素" << std::endl;}// 输出：找到元素 30，位置索引：2return 0;
}

示例代码：在字符串中查找字符

#include <algorithm>
#include <string>
#include <iostream>int main() {std::string text = "Hello, World!";char target = 'W';auto it = std::find(text.begin(), text.end(), target);if (it != text.end()) {std::cout << "找到字符 '" << *it << "'，位置：" << it - text.begin() << std::endl;} else {std::cout << "未找到字符" << std::endl;}// 输出：找到字符 'W'，位置：7return 0;
}

自定义类型的查找

若查找自定义类型的对象，需确保该类型支持 operator== 或使用自定义谓词（结合 std::find_if）。

示例1：自定义结构体（重载operator==)

#include <algorithm>
#include <vector>
#include <iostream>struct Person {std::string name;int age;bool operator==(const Person& other) const {return name == other.name && age == other.age;}
};int main() {std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};Person target = {"Bob", 25};auto it = std::find(people.begin(), people.end(), target);if (it != people.end()) {std::cout << "找到：" << it->name << std::endl; // 输出：找到：Bob}return 0;
}

示例2：使用std::find_if自定义条件

#include <algorithm>
#include <vector>
#include <iostream>struct Product {int id;std::string name;
};int main() {std::vector<Product> products = {{101, "Apple"}, {202, "Banana"}, {303, "Cherry"}};int target_id = 202;auto it = std::find_if(products.begin(), products.end(),[target_id](const Product& p) { return p.id == target_id; });if (it != products.end()) {std::cout << "找到产品：" << it->name << std::endl; // 输出：找到产品：Banana}return 0;
}

常见问题

确保迭代器有效性

● 使用返回的迭代器前，需检查是否有效（是否等于 last），避免访问无效内存。

auto it = std::find(/* ... */);
if (it != container.end()) {// 安全操作
}

性能与时间复杂度

● 时间复杂度：O(n),线性遍历所有元素直到找到目标。
● 优化建议：
○ 若容器已排序，使用 std::binary_search（O(log n)）。
○ 若需频繁查找，改用 std::set 或 std::unordered_set（哈希表，O(1) 平均复杂度）。

结合其他算法

查找最后一个匹配项：std::find_end 或反向迭代器。

std::vector<int> nums = {1, 2, 3, 2, 1};
auto rit = std::find(nums.rbegin(), nums.rend(), 2); // 从后向前查找
if (rit != nums.rend()) {std::cout << "最后一个 2 的位置：" << nums.rend() - rit - 1 << std::endl; // 输出：3
}

处理空范围

若 first == last（空范围），直接返回 last，不会引发错误。

拓展：std::find_if 和 std::find_if_not

std::find_if：按自定义条件查找。

std::vector<int> nums = {1, 3, 5, 7, 9};
auto it = std::find_if(nums.begin(), nums.end(), [](int x) { return x % 2 == 0; });
if (it == nums.end()) {std::cout << "未找到偶数" << std::endl;
}

std::find_if_not：查找不满足条件的元素。

std::vector<int> nums = {2, 4, 6, 7, 8};
auto it = std::find_if_not(nums.begin(), nums.end(), [](int x) { return x % 2 == 0; });
if (it != nums.end()) {std::cout << "第一个奇数是 " << *it << std::endl; // 输出：7
}