如何在C++的STL中巧妙运用std::find实现高效查找
- 一、简介
- 二、在那里吗？
- 2.1、在未排序的元素上
- 2.2、已排序元素
- 三、在哪里?
- 3.1、在未排序的元素上
- 3.2、已排序元素
- 四、应该在哪里?
- 五、结论
一、简介
本文章旨在涵盖所有在STL中（甚至稍微超出）关于搜索的知识，尽管在集合中搜索某些东西的需求是一个很容易理解的概念，但是要彻底地涵盖这个主题，还有很多内容要讲。
本文主要介绍在元素范围上执行搜索的经典STL算法，后面会继续讲解当直接访问STL容器时，如何执行有效和正确的搜索，而不是简单的范围；以及介绍的绝大多数开发人员不知道但很有用的算法。
这篇文章展示了如何在一个范围内搜索。这里将坚持使用标准版本的STL，并考虑由2个迭代器表示的范围。
STL可以被分成两部分：对已排序元素进行操作的部分以及对未排序元素进行操作的部分。
这种差异对搜索有两个影响:
- 在已排序的集合中查找非常快，通常在对数时间内，而在未排序的集合中查找通常在线性时间内。
- 在已排序范围上显示的所有方法都按照等价性（与
<比较）来比较值，而在未排序范围上显示的方法则按照相等性（与==比较）来比较值。
这篇文章将深入探讨以下3个问题：
- 在那里吗？
- 在哪里？
- 应该在哪里(对于排序范围)？
二、在那里吗？
2.1、在未排序的元素上
这个问题可以用std::find来表示，并结合与范围末尾的比较：
vector<int> v = {...}; // v filled with values
if (std::find(v.begin(), v.end(), 42) != v.end())
{
...
}
当然，也可以用std::count来表示。
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值，表示搜索值是否在集合中具有等效元素。
std::set<int> numbers = {...}; // sorted elements
bool is42InThere = std::binary_search(numbers.begin(), numbers.end(), 42);
三、在哪里?
更准确地说，希望获得指向搜索元素出现位置的迭代器。
3.1、在未排序的元素上
使用std::find。它将返回指向第一个与搜索值相等的元素的迭代器，如果没有找到该值，则返回指向集合末尾的迭代器。
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不是专门为排序范围进行操作而设计的。
使用的算法是std::equal_range，函数原型：
template< class ForwardIt, class T >
std::pair<ForwardIt,ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value );
std::equal_range 返回与搜索值等价的元素范围。该范围由指向集合内部的 std::pair 迭代器对表示， 该对中的两个迭代器分别表示与搜索值等价的子范围中第一个和最后一个元素。
它的接口使用起来有些笨拙：
std::vector<int> v = {3, 7, 3, 11, 3, 3, 2};
sort(v.begin(), v.end());
// equal_range, attempt 1: natively clumsy
std::pair<std::vector<int>::iterator, std::vector<int>::iterator> range1 = equal_range(v.begin(), v.end(), 3);
std::for_each(range1.first, range1.second, doSomething);
使用类型定义可以使其更轻巧：
std::vector<int> v = {3, 7, 3, 11, 3, 3, 2};
sort(v.begin(), v.end());
using IteratorPair = std::pair<std::vector<int>::iterator, std::vector<int>::iterator>;
// equal_range, attempt 2: with the classical typedef
IteratorPair range2 = equal_range(v.begin(), v.end(), 3);
std::for_each(range2.first, range2.second, doSomething);
上面的示例确实少了笨拙，但仍然有一个基本的问题：抽象的层次没有得到遵守。事实上，当操作由equal_range返回的东西时，pair强迫使用代码的“first”和“second”，而它应该是一个范围。而一个范围应该用“begin”和“end”来表达。
为了解决这个问题，可以使用一个类将std::equal_range返回的一对迭代器包装成一个具有范围语义的对象：
template<typename Container>
class Range
{
public:
Range(std::pair<typename Container::iterator, typename Container::iterator> range)
: m_begin(range.first), m_end(range.second)
{}
typename Container::iterator begin() { return m_begin; }
typename Container::iterator end() { return m_end; }
private:
typename Container::iterator m_begin;
typename Container::iterator m_end;
};
这类存在于诸如Boost.range或range-v3之类的range库中。如果查看它们的实现代码(这里是boost的实现代码，这里是range-v3的实现代码)，会发现它们包含的内容远不止上面的简单包装器，这里只是为了说明要点，而不是用于实际生产代码)。
这有效地将一对迭代器提升到范围的抽象级别。
注意，如果没有包装器，std::begin和std::end不能用于std::equal_range的结果，即使它是一个范围！包装器才能真正解决了这个问题。
使用方式：
std::vector<int> v = {3, 7, 3, 11, 3, 3, 2};
sort(v.begin(), v.end());
// equal_range, attempt 3: natural al last
Range<std::vector<int>> range3 = equal_range(v.begin(), v.end(), 3);
std::for_each(range3.begin(), range3.end(), doSomething);
无论使用上述哪种方法，equal_range都会返回一个范围，所以可以通过比较两个迭代器来检查它是否为空，并使用std::distance来检查它的大小：
bool noElementFound = range3.begin() == range3.end();
size_t numberOfElementFound = std::distance(range3.begin(), range3.end())
四、应该在哪里?
这个问题只对已排序的范围有意义，因为对于未排序的范围，元素可以在范围中的任何位置。对于一个已排序的范围，更精确地说是：“如果它在那里，那么它在哪里，如果它不在那里，那么它应该在哪里?”。有点绕，对不对，没关系，继续往下阅读。
这个问题可以用std::lower_bound和std::upper_bound两种算法表示。
一旦理解了std::equal_range，就很容易理解它们了：std::lower_bound和std::upper_bound分别返回std::equal_range返回的第一个迭代器和第二个迭代器。
因此，
- 要在范围内插入一个值，使其位于与该值相等的元素之前，使用
std::lower_bound获取一个迭代器，指定要插入的位置。 - 要在范围内插入一个值，使其位于与该值相等的元素之后，使用
std::upper_bound获取一个迭代器，指定要插入的位置。
注意，一般不要使用std::lower_boud来搜索元素：不像std::find，不能简单地检查std::lower_bound返回的迭代器是否与end不同，从而知道元素是否在集合中。如果元素不存在，std::lower_bound返回它应该在的位置，而不是集合的末尾。因此，需要检查返回的迭代器是否不在范围的末尾，并检查它指向的元素的值是否与搜索的元素的值相等。
要特别要小心：相等，不相等。如果对类型并不意味着相同的事情，则需要编写等价测试，通常采用!(a < b) && !(b < a)的形式。如果排序比较器不是operator<，而是自定义比较器，则需要使用自定义比较器。如果比较器发生变化，一定要更新代码。建议，只需使用std::equal_range即可。
五、结论
下面的表格总结了在一个范围内搜索时使用的算法：
| C++表达 | 不排序 | 排序 |
|---|---|---|
| 在那里吗？ | std::find != end | std::binary_search |
| 在哪里？ | std::find | std::equal_range |
| 应该在哪里？ | – | std::lower_bound、std::upper_bound |
在下一篇文章中，将了解如何直接在标准容器中搜索，而不是在范围中搜索。
