C / C++ / 系统课时

用 find 查找指定元素

用 find 查找指定元素

std::find 用于在一个迭代器区间中顺序查找指定值。它不会直接返回下标或布尔值,而是返回指向首个匹配元素的迭代器;如果没有找到,就返回传入区间的结束迭代器。

学习目标

  • 会用 std::find 在容器区间中查找指定值
  • 能通过返回迭代器与 end() 比较判断是否命中
  • 理解 std::find 的查找范围、返回位置和时间复杂度

find 的基本规则

std::find(first, last, value) 搜索半开区间 [first, last)。算法从 first 开始逐个比较,遇到第一个等于 value 的元素就停止;如果一直到 last 都没有匹配,则返回 last。

因此,判断结果时应先比较返回值与同一容器的 end()。只有确认迭代器没有到达结束位置之后,才能安全地使用 *it 读取元素。

在 vector 中查找元素

下面在 std::vector<int> 中查找 30。找到后使用 std::distance 计算它与 begin() 的距离,从而得到元素位置。

cpp
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    std::vector<int> values{10, 20, 30, 40, 30};
    const int target = 30;

    auto it = std::find(values.begin(), values.end(), target);

    if (it != values.end()) {
        const auto index = std::distance(values.begin(), it);
        std::cout << "found: " << *it << ", index: " << index << '\n';
    } else {
        std::cout << "not found\n";
    }
}

预期输出:

text
found: 30, index: 2

容器中虽然存在两个 30,但 std::find 只返回遇到的第一个匹配元素。它负责的是“找到第一个位置”,不会自动统计数量,也不会继续返回后续匹配结果。

没找到时为什么返回 end

结束迭代器表示区间末尾之后的位置,本身不能被解引用。std::find 使用它作为统一的“未找到”标记,因此调用端不需要额外的特殊返回类型。

下面是错误的片段示例,依赖已经定义的 values 和 target:

cpp
auto it = std::find(values.begin(), values.end(), target);
// 如果 it == values.end(),这里不能解引用
std::cout << *it << '\n';

正确顺序始终是先检查 it != values.end(),确认命中后再访问 *it。这一模式同样适用于许多返回迭代器的 STL 查找算法。

查找成本与适用边界

对普通迭代器区间,std::find 最多需要检查区间中的每个元素,因此时间复杂度为 O(n)O(n)。它适合 vector、list、数组等结构中的一次性线性查找。

如果数据本身提供了更适合的查找机制,应优先利用容器或数据结构的特性。有序区间可以考虑 std::lower_bound;查找 std::set、std::map、std::unordered_set 或 std::unordered_map 中的键时,通常应使用容器自己的 find 成员函数,而不是进行线性扫描。

使用 std::find 时最重要的习惯是:保存返回迭代器,先与区间终点比较,再解引用。这样既能正确区分“找到”和“未找到”,也能避免访问结束迭代器造成的未定义行为。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用 find 查找指定元素

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通