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

2019-11-11 07:08:24

字體：大中小

來源：轉載

供稿：網友

本文分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

上一篇：how to learn unit test mock framework

下一篇：368. Largest Divisible Subset -Medium