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

2019-11-14 09:31:19

字体：大中小

来源：转载

供稿：网友

本文分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 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::set<int> numbers = // sorted elementsbool is42InThere = std::binary_search(numbers.begin(), numbers.end(), 42);

Where is it?

(当确定了要搜索的值存在后,) 我们想更进一步, 得到指向那个元素的迭代器.

乱序容器的元素

使用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) 函数原型:

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

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:

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 typedefIteratorPair range2 = equal_range(v.begin(), v.end(), 3);std::for_each(range2.first, range2.second, doSomething);

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

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

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;};

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

std::vector<int> v = {3, 7, 3, 11, 3, 3, 2};sort(v.begin(), v.end());// equal_range, attempt 3: natural al lastRange<std::vector<int>> range3 = equal_range(v.begin(), v.end(), 3);std::for_each(range3.begin(), range3.end(), doSomething);

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

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

上一篇：Java 数组到 HashMap 之算法解释

下一篇：Golang RPC调用例子程序(实现超时机制)