本文分3部分: 1. 怎么使用STL进行高效的查找: 借用传统STL算法对元素进行范围搜索 2. 搜索STL容器: 当你有直接读取STL容器里元素的权限时, 怎么进行高效准确的搜索(与简单的范围搜索相比较) 3. STL搜索算法的秘密: 向公众展示不为人知的算法, 这些算法在已经学习过的人眼里确实是很有用的
STL根据查看方式的不同, 一共分为两种: 排序的和不排序的. * 排序集合的遍历, 通常需要对数时长, 而乱序集合的遍历, 需要线性时长 * 排序容器中比较元素大小的函数根据equivalence(comparing with <), 而乱序容器中的函数根据equality(comparing with ==).
本文将展示对于在一个范围内搜索一个给定的值, C++怎么样去阐述下面3个问题: * 它存在否 * 它在哪 * 它应该在什么位置(排序容器)
这个问题可以用std::find来表达(需要和与范围的终点值的比较相结合):
vector<int> v = ... // v filled with valuesif (std::find(v.begin(), v.end(), 42) != v.end()){ ...“Is it there”这个问题也可以用std::count来表达:
vector<int> v = ... // v filled with valuesif (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::find. 返回指向第一个与搜索的值相等的元素的迭代器, 如果找不到, 则返回集合的终点.
std::vector<int> 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
) 函数原型:
std::equal_range
返回与搜索值相等的元素的范围, 这个范围用一对集合内的迭代器表示. 这两个迭代器分别指向 与搜索值相等的范围里第一个元素和最后一个元素的下一个位置.
然而, 它的接口有些笨重: 例A:
std::vector<int> v = {3, 7, 3, 11, 3, 3, 2};sort(v.begin(), v.end());// equal_range, attempt 1: natively clumsystd::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);用一个typedef
或者using
让它更简洁: 例B:
例B确实简洁了很多, 但是仍有一个根本问题: 没有考虑 抽象等级. 尽管返回的是一个范围, 但这对迭代器强迫我们在操作返回的范围时必须按照”第一”“第二”这种方式来写代码. 范围就应该用”首”“尾”这种方式来表达. 这不仅给我们在其他地方使用这个返回值时造成很大的麻烦, 而且使代码很别扭.
为了解决这个问题, 我么可以把std::equal_range
返回的迭代器对封装进一个有”范围”这种语义的object
注意: 尽管std::equal_range
返回的结果是一个”范围”, 但是std::begin
和 std::end
不能用在这个结果上. 而上面的封装解决了这个问题. 可以像下面这样使用:
不管你使用上面的哪种方式, std::equal_range
都会返回一个范围, 要确定它是否为空, 可以通过检查那两个迭代器(是否相等)或者使用std::distance
检查它的大小.
这个问题仅仅针对排序的范围, 因为对于乱序的范围, 某个元素可能会存在任何位置.
对于排序的范围, 这个问题可以简化为: 如果它存在, 那么它在哪儿? 如果它不存在, 那么它应该在哪儿?
这个问题可以用算法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
新闻热点
疑难解答