[译]How to (std::)find something efficiently with the STL

本文分3部分: 1. 怎么使用STL进行高效的查找: 借用传统STL算法对元素进行范围搜索 2. 搜索STL容器: 当你有直接读取STL容器里元素的权限时, 怎么进行高效准确的搜索(与简单的范围搜索相比较) 3. STL搜索算法的秘密: 向公众展示不为人知的算法, 这些算法在已经学习过的人眼里确实是很有用的

STL根据查看方式的不同, 一共分为两种: 排序的和不排序的. * 排序集合的遍历, 通常需要对数时长, 而乱序集合的遍历, 需要线性时长 * 排序容器中比较元素大小的函数根据equivalence(comparing with <), 而乱序容器中的函数根据equality(comparing with ==).

本文将展示对于在一个范围内搜索一个给定的值, C++怎么样去阐述下面3个问题: * 它存在否 * 它在哪 * 它应该在什么位置(排序容器)

Is it there?

乱序容器的元素

这个问题可以用std::find来表达(需要和与范围的终点值的比较相结合):

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

“Is it there”这个问题也可以用std::count来表达:

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

std::count()的返回值会被隐式地转换成if条件里的bool值: 如果该范围里有至少一个值为42, 则返回true.

与std::find相比, std::count的优劣: 优势:

  • std::count避免了与范围的end值相比较

弊端:

  • std::count遍历整个集合, 而std::find在第一个与要查找的值相等的位置停下
  • 可以证明, 对于”想要查找某个值”这件事, std::find 表达得更明确 基于以上, std::find用得更多.

Note 若要确认某个值存在而非是与要搜索的值相等, 请使用std::count_if, std::find_if, std::find_if_not

排序容器的元素

使用的算法是std::binary_search, 此函数返回一个bool值, 此bool值表示在集合中是否存在与搜索的值相等的元素.

std::set<int> numbers = // sorted elements
bool is42InThere = std::binary_search(numbers.begin(), numbers.end(), 42);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
    
### Where is it?
(当确定了要搜索的值存在后,) 我们想更进一步, 得到指向那个元素的迭代器.

#### 乱序容器的元素

使用std::find. 返回指向第一个与搜索的值相等的元素的迭代器, 如果找不到, 则返回集合的终点.



std::vector numbers = ... auto searchResult = std::find(numbers.begin(), numbers.end(), 42);

if (searchResult != numbers.end()) { ...


#### 排序容器的元素

对于排序集合, STL并没有像std::find一样直接的算法. std::find并不是为排序容器设计的, 因为它依据的是"=="而不是"&lt;", 消耗的时间为线性时长而不是对数时长.
对于一个给定的容器, 如果容器内元素的"equality"和"equivalence"是相同的, 且你能接受消耗的线性时长, 那么std::find会为你返回正确的结果, 你也能从它简单直接的接口中获益. **但是,** 不能忘记, std::find并不是为排序容器设计的.

这里推荐使用`std::equal_range`. (并非`std::lower_bound`)
函数原型:



template< class ForwardIt, class T > std::pair<forwardit,forwardit> equal_range( ForwardIt first, ForwardIt last, const T& value );

`std::equal_range` 返回与搜索值相等的元素的范围, 这个范围用一对集合内的迭代器表示. 这两个迭代器分别指向 与搜索值相等的范围里第一个元素和最后一个元素的下一个位置.</forwardit,forwardit>

然而, 它的接口有些笨重:
例A:


std::vector v = {3, 7, 3, 11, 3, 3, 2}; sort(v.begin(), v.end());

// equal_range, attempt 1: natively clumsy std::pair<std::vector::iterator, std::vector::iterator> range1 = equal\_range(v.begin(), v.end(), 3); std::for\_each(range1.first, range1.second, doSomething);

用一个`typedef` 或者`using`让它更简洁:
例B:


std::vector v = {3, 7, 3, 11, 3, 3, 2}; sort(v.begin(), v.end());</std::vector

using IteratorPair = std::pair<std::vector::iterator, std::vector::iterator>;</std::vector

// 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);

例B确实简洁了很多, 但是仍有一个根本问题: 没有考虑 抽象等级.
尽管返回的是一个范围, 但这对迭代器强迫我们在操作返回的范围时必须按照"第一""第二"这种方式来写代码. 范围就应该用"首""尾"这种方式来表达. 这不仅给我们在其他地方使用这个返回值时造成很大的麻烦, 而且使代码很别扭.

为了解决这个问题, 我么可以把`std::equal_range` 返回的迭代器对封装进一个有"范围"这种语义的`object`



template

class Range

{

public:

Range(std::pair 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; };

注意: 尽管`std::equal_range` 返回的结果是一个"范围", 但是`std::begin` 和 `std::end` 不能用在这个结果上. 而上面的封装解决了这个问题.
可以像下面这样使用:



std::vector v = {3, 7, 3, 11, 3, 3, 2}; sort(v.begin(), v.end());

// equal_range, attempt 3: natural al last Range<std::vector\> range3 = equal\_range(v.begin(), v.end(), 3); std::for\_each(range3.begin(), range3.end(), doSomething);

不管你使用上面的哪种方式, `std::equal_range` 都会返回一个范围, 要确定它是否为空, 可以通过检查那两个迭代器(是否相等)或者使用`std::distance` 检查它的大小. </std::vector<int>



bool noElementFound = range3.begin() == range3.end(); size_t numberOfElementFound = std::distance(range3.begin(), range3.end())

Where should it be?

这个问题仅仅针对排序的范围, 因为对于乱序的范围, 某个元素可能会存在任何位置.

对于排序的范围, 这个问题可以简化为: 如果它存在, 那么它在哪儿? 如果它不存在, 那么它应该在哪儿?

这个问题可以用算法std::lower_boundstd::upper_bound 来解释.

当你理解了std::equal_range 后, 上面这句话就很容易理解了: std::lower_boundstd::upper_bound 都会返回 std::equal_range 返回的那个迭代器对的第一个和第二个迭代器.

要插入某个值x, 使用std::lower_bound 得到指向 在范围里与x相等的元素之前的位置的迭代器, 使用std::upper_bound 得到指向 在范围里与x相等的元素之后的位置的迭代器.

注意: 如果仅仅是搜索某个元素, 永远不要使用std::lower_bound

std::find 相反, 你不能根据 判断std::lower_bound 返回的迭代器是否与终点的迭代器相等 来判断要搜索的值是否存在于这个集合. 事实上, 如果这个值在集合里不存在, 则std::lower_bound 返回它应该在的位置, 而不是终点的迭代器. 所以, 你不仅需要确认返回的迭代器不是终点的迭代器, 还要确认它指向的元素跟要搜索的值是相等的.

总结

Question to express in C++

NOT SORTED

SORTED

Is it there?

std::find != end

std::binary_search

Where is it?

std::find

std::equal_range

Where should it be?

-

std::lower_bound / std::upper_bound

原文地址: http://www.fluentcpp.com/2017/01/16/how-to-stdfind-something-efficiently-with-the-stl/?hmsr=toutiao.io&utm\_medium=toutiao.io&utm\_source=toutiao.io