本文分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);
```</int>
### 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并不是为排序容器设计的, 因为它依据的是"=="而不是"<", 消耗的时间为线性时长而不是对数时长.
对于一个给定的容器, 如果容器内元素的"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 Rangestd::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_bound 和std::upper_bound 来解释.
当你理解了std::equal_range 后, 上面这句话就很容易理解了: std::lower_bound 和std::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