如何在C++的STL中巧妙运用std::find实现高效查找

这篇文章展示如何在一个范围内搜索。这里坚持用标准版本的STL，并考虑由2个迭代器表示的范围。

STL可以被分成两部分：对已排序元素进行操作的部分以及对未排序元素进行操作的部分。

这种差异对搜索有两个影响:

• 在已排序的集合中查找非常快，通常在对数时间内，而在未排序的集合中查找通常在线性时间内。

• 在已排序范围上显示的所有方法都按照等价性（与<比较）来比较值，而在未排序范围上显示的方法则按照相等性（与==比较）来比较值。

这篇文章探讨以下3个问题：

• 在那里吗？

• 在哪里？

• 应该在哪里(对于排序范围)？

二、在那里吗？

2.1、在未排序的元素上

这个问题可以用std::find来表示，并结合与范围末尾的比较：

代码语言：C++

自动换行

AI代码解释

vector<int> v = {...}; // v filled with values if (std::find(v.begin(), v.end(), 42) != v.end()) { ... }

当然，也可以用std::count来表示。

代码语言：C++

自动换行

AI代码解释

vector<int> v = {...}; // v filled with values if (std::count(v.begin(), v.end(), 42)) { ... }

返回值在if语句中隐式地转换为bool值：在这里，如果范围内至少有一个元素等于42，则计算结果为true。

与std::find相比，std::count方法有优点也有缺点。

std::count的优点：std::count避免与结束操作符进行比较。

std::count的缺点:

• std::count遍历整个集合，而std::find在搜索到第一个与搜索值相等的元素时就返回。

• std::find更好地表达了正在查找的内容。

因此，std::find更常用。

注意，要检查是否存在满足谓词而不等于值的元素，用std::count_if、std::find_if和std::find_if_not，这应该是必知的。

2.2、已排序元素

关于已排序元素，要用的算法是std::binary_search，直接返回一个bool值，表示搜索值是否在集合中具有等效元素。

代码语言：C++

自动换行

AI代码解释

std::set<int> numbers = {...}; // sorted elements bool is42InThere = std::binary_search(numbers.begin(), numbers.end(), 42);

三、在哪里?

更准确地说，希望获得指向搜索元素出现位置的迭代器。

3.1、在未排序的元素上

用std::find。返回指向第一个和搜索值相等的元素的迭代器，如果没有找到该值，则返回指向集合末尾的迭代器。

代码语言：C++

自动换行

AI代码解释

std::vector<int> numbers = {...}; auto searchResult = std::find(numbers.begin(), numbers.end(), 42); if (searchResult != numbers.end()) { ... }

3.2、已排序元素

对于已排序的集合，STL没有像std::find那样简单的算法。但是std::find并不是真正为排序集合而设计的，因为它用的是相等而不是等价，并且它在线性时间而不是对数时间内操作。

对于给定的集合，如果确定现在和将来元素的类型的相等性与等价性是相同的，并且接受付出线性时间，std::find将是不错的选择，引起它是简单的接口。必须注意，std::find不是专门为排序范围进行操作而设计的。