首页 > 学院 > 开发设计 > 正文

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::beginstd::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_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


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表