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

2019-11-14 08:55:24

字體：大中小

供稿：網(wǎng)友

本文分3部分: 1. 怎么使用STL進(jìn)行高效的查找: 借用傳統(tǒng)STL算法對(duì)元素進(jìn)行范圍搜索 2. 搜索STL容器: 當(dāng)你有直接讀取STL容器里元素的權(quán)限時(shí), 怎么進(jìn)行高效準(zhǔn)確的搜索(與簡(jiǎn)單的范圍搜索相比較) 3. STL搜索算法的秘密: 向公眾展示不為人知的算法, 這些算法在已經(jīng)學(xué)習(xí)過(guò)的人眼里確實(shí)是很有用的

STL根據(jù)查看方式的不同, 一共分為兩種: 排序的和不排序的. * 排序集合的遍歷, 通常需要對(duì)數(shù)時(shí)長(zhǎng), 而亂序集合的遍歷, 需要線性時(shí)長(zhǎng) * 排序容器中比較元素大小的函數(shù)根據(jù)equivalence(comparing with <), 而亂序容器中的函數(shù)根據(jù)equality(comparing with ==).

本文將展示對(duì)于在一個(gè)范圍內(nèi)搜索一個(gè)給定的值, C++怎么樣去闡述下面3個(gè)問(wèn)題: * 它存在否 * 它在哪 * 它應(yīng)該在什么位置(排序容器)

Is it there?

亂序容器的元素

這個(gè)問(wèn)題可以用std::find來(lái)表達(dá)(需要和與范圍的終點(diǎn)值的比較相結(jié)合):

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

“Is it there”這個(gè)問(wèn)題也可以用std::count來(lái)表達(dá):

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

std::count()的返回值會(huì)被隱式地轉(zhuǎn)換成if條件里的bool值: 如果該范圍里有至少一個(gè)值為42, 則返回true.

與std::find相比, std::count的優(yōu)劣: 優(yōu)勢(shì):

std::count避免了與范圍的end值相比較

弊端:

std::count遍歷整個(gè)集合, 而std::find在第一個(gè)與要查找的值相等的位置停下可以證明, 對(duì)于”想要查找某個(gè)值”這件事, std::find 表達(dá)得更明確基于以上, std::find用得更多.

Note 若要確認(rèn)某個(gè)值存在而非是與要搜索的值相等, 請(qǐng)使用std::count_if, std::find_if, std::find_if_not

排序容器的元素

使用的算法是std::binary_search, 此函數(shù)返回一個(gè)bool值, 此bool值表示在集合中是否存在與搜索的值相等的元素.

std::set<int> numbers = // sorted elementsbool is42InThere = std::binary_search(numbers.begin(), numbers.end(), 42);

Where is it?

(當(dāng)確定了要搜索的值存在后,) 我們想更進(jìn)一步, 得到指向那個(gè)元素的迭代器.

亂序容器的元素

使用std::find. 返回指向第一個(gè)與搜索的值相等的元素的迭代器, 如果找不到, 則返回集合的終點(diǎn).

std::vector<int> numbers = ...auto searchResult = std::find(numbers.begin(), numbers.end(), 42);if (searchResult != numbers.end()){ ...

排序容器的元素

對(duì)于排序集合, STL并沒有像std::find一樣直接的算法. std::find并不是為排序容器設(shè)計(jì)的, 因?yàn)樗罁?jù)的是”==”而不是”<”, 消耗的時(shí)間為線性時(shí)長(zhǎng)而不是對(duì)數(shù)時(shí)長(zhǎng). 對(duì)于一個(gè)給定的容器, 如果容器內(nèi)元素的”equality”和”equivalence”是相同的, 且你能接受消耗的線性時(shí)長(zhǎng), 那么std::find會(huì)為你返回正確的結(jié)果, 你也能從它簡(jiǎn)單直接的接口中獲益. 但是, 不能忘記, std::find并不是為排序容器設(shè)計(jì)的.

這里推薦使用std::equal_range. (并非std::lower_bound) 函數(shù)原型:

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

std::equal_range 返回與搜索值相等的元素的范圍, 這個(gè)范圍用一對(duì)集合內(nèi)的迭代器表示. 這兩個(gè)迭代器分別指向與搜索值相等的范圍里第一個(gè)元素和最后一個(gè)元素的下一個(gè)位置.

然而, 它的接口有些笨重: 例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);

用一個(gè)typedef 或者using讓它更簡(jiǎn)潔: 例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確實(shí)簡(jiǎn)潔了很多, 但是仍有一個(gè)根本問(wèn)題: 沒有考慮抽象等級(jí). 盡管返回的是一個(gè)范圍, 但這對(duì)迭代器強(qiáng)迫我們?cè)诓僮鞣祷氐姆秶鷷r(shí)必須按照”第一”“第二”這種方式來(lái)寫代碼. 范圍就應(yīng)該用”首”“尾”這種方式來(lái)表達(dá). 這不僅給我們?cè)谄渌胤绞褂眠@個(gè)返回值時(shí)造成很大的麻煩, 而且使代碼很別扭.

為了解決這個(gè)問(wèn)題, 我么可以把std::equal_range 返回的迭代器對(duì)封裝進(jìn)一個(gè)有”范圍”這種語(yǔ)義的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 返回的結(jié)果是一個(gè)”范圍”, 但是std::begin 和 std::end 不能用在這個(gè)結(jié)果上. 而上面的封裝解決了這個(gè)問(wèn)題. 可以像下面這樣使用:

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 都會(huì)返回一個(gè)范圍, 要確定它是否為空, 可以通過(guò)檢查那兩個(gè)迭代器(是否相等)或者使用std::distance 檢查它的大小.

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

Where should it be?

這個(gè)問(wèn)題僅僅針對(duì)排序的范圍, 因?yàn)閷?duì)于亂序的范圍, 某個(gè)元素可能會(huì)存在任何位置.

對(duì)于排序的范圍, 這個(gè)問(wèn)題可以簡(jiǎn)化為: 如果它存在, 那么它在哪兒? 如果它不存在, 那么它應(yīng)該在哪兒?

這個(gè)問(wèn)題可以用算法std::lower_bound 和std::upper_bound 來(lái)解釋.

當(dāng)你理解了std::equal_range 后, 上面這句話就很容易理解了: std::lower_bound 和std::upper_bound 都會(huì)返回 std::equal_range 返回的那個(gè)迭代器對(duì)的第一個(gè)和第二個(gè)迭代器.

要插入某個(gè)值x, 使用std::lower_bound 得到指向在范圍里與x相等的元素之前的位置的迭代器, 使用std::upper_bound 得到指向在范圍里與x相等的元素之后的位置的迭代器.

注意: 如果僅僅是搜索某個(gè)元素, 永遠(yuǎn)不要使用std::lower_bound

與std::find 相反, 你不能根據(jù) 判斷std::lower_bound 返回的迭代器是否與終點(diǎn)的迭代器相等來(lái)判斷要搜索的值是否存在于這個(gè)集合. 事實(shí)上, 如果這個(gè)值在集合里不存在, 則std::lower_bound 返回它應(yīng)該在的位置, 而不是終點(diǎn)的迭代器. 所以, 你不僅需要確認(rèn)返回的迭代器不是終點(diǎn)的迭代器, 還要確認(rèn)它指向的元素跟要搜索的值是相等的.

總結(jié)

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

上一篇：MFC：調(diào)用Invalidate()的作用

下一篇：讀取xml文件內(nèi)容到數(shù)據(jù)庫(kù)