在一個(gè)集合中找到一個(gè)特別的條目是個(gè)很重要的問(wèn)題，標(biāo)準(zhǔn)C++運(yùn)行庫(kù)提供了許多不同的搜索技術(shù)。
在 C++運(yùn)行庫(kù)中，指明一個(gè)集合的常用方法是通過(guò)iterator指示出區(qū)間。區(qū)間可以被寫(xiě)為[first, last)， 此處，*first是區(qū)間內(nèi)的第一個(gè)元素而last則指向最后一個(gè)元素的下一個(gè)。本文展示了我們?nèi)绾慰紤]一個(gè)通用問(wèn)題：給定一個(gè)區(qū)間和一個(gè)準(zhǔn)則，找到指向第一個(gè)滿足準(zhǔn)則的元素的iterator。因?yàn)槲覀儗^(qū)間表示為不對(duì)稱(chēng)的形式，于是避開(kāi)了一個(gè)特殊情況：搜索失敗可以返回last，沒(méi)有任何 元素的區(qū)間可以寫(xiě)為[i, i)。
線性搜索和它的變種
最簡(jiǎn)單的搜索是線性搜索，或，如Knuth所稱(chēng)呼的，順序搜索：依次查看每個(gè)元素，檢查它是否為我們正在搜索的那個(gè)。如果區(qū)間中有N個(gè)元素，最壞的情況就需要N次比較。
標(biāo)準(zhǔn)運(yùn)行庫(kù)提供了線性搜索的一些版本；兩個(gè)最重要的版本是find() (它接受一個(gè)區(qū)間和值x，并查找等價(jià)于x的元素)和find_if()(接受一個(gè)區(qū)間和判決條件p，并查找滿足p的元素)。線性搜索的其它版本是 find_first_of()(接受兩個(gè)區(qū)間，[first1,last1)和[first2,last2) ，并在[first1, last1)中查找第一個(gè)等價(jià)于[first2, last2)中任何一個(gè)元素的元素)和adjacent_find()(接受單一區(qū)間，并查找第一個(gè)等價(jià)于其后繼元素的元素)。
舉例來(lái)說(shuō)，假如，v是一個(gè)int的vector。你能用下面的代碼查找第一個(gè)0：
vector<int>::iterator i = find(v.begin(), v.end(), 0);
查找第一個(gè)非0值：
vector<int>::iterator i = find_if(v.begin(), v.end(), not1(bind2nd(equal_to<int>(), 0)));
查找第一個(gè)小質(zhì)數(shù)：
A[4] = { 2, 3, 5, 7 };
vector<int>::iterator i = find_first_of(v.begin(), v.end(), A+0, A+4);
找到第一個(gè)重復(fù)對(duì)：
vector<int>::iterator i = adjacent_find(v.begin(), v.end());
沒(méi)有任何獨(dú)立版本以對(duì)區(qū)間進(jìn)行逆向搜索，因?yàn)槟悴恍枰耗隳苡靡粋€(gè)簡(jiǎn)單的iterator adaptor來(lái)達(dá)到相同的效果。比如，在v中找到最后一個(gè)0，可以這么寫(xiě)：
vector<int>::reverse_iterator i = find(v.rbegin(), v.rend(), 0);
線性搜索是一個(gè)簡(jiǎn)單的算法，它的實(shí)現(xiàn)看起來(lái)沒(méi)什么可討論的。許多書(shū)(包括我的)展示了std::find()的一個(gè)簡(jiǎn)單的實(shí)現(xiàn)：
template <class InIter, class T>
InIter find(InIter first, InIter last, const T& val)
{
while (first != last && ! (*first == val)) ++first;
return first;
}
這的確是線性搜索算法的一個(gè)忠實(shí)的實(shí)現(xiàn)，滿足C++標(biāo)準(zhǔn)的需求；第一個(gè)模板參數(shù)的名字，InIter，意味著實(shí)參只需要是非常弱的Input Iterator[注1]。它看起來(lái)可能是如此的簡(jiǎn)單，以致于還不如在代碼中直接手寫(xiě)出來(lái)。雖然如此，還是有一個(gè)令人懊惱的問(wèn)題：這個(gè)實(shí)現(xiàn)沒(méi)有達(dá)到它應(yīng)該的效率。循環(huán)條件很復(fù)雜，需要為取得的每個(gè)元素作兩個(gè)測(cè)試。有條件的分支昂貴的，并且復(fù)雜的循環(huán)條件不會(huì)得到與簡(jiǎn)單的循環(huán)條件同樣程度的優(yōu)化。
問(wèn)題的答案之一，并是被某些標(biāo)準(zhǔn)運(yùn)行庫(kù)的實(shí)作所采用[注2]，是“解開(kāi)”循環(huán)，每次檢查4個(gè)元素。這是比較復(fù)雜的解決方法，因?yàn)閒ind()然后必須處理殘余元素（區(qū)間不會(huì)總是4的倍數(shù)），以及它還需要find()基于Iterator的種類(lèi)進(jìn)行分解－－“解開(kāi)”只能工作于Random Access Iterator指示的區(qū)間，對(duì)一般情況還是需要使用老的實(shí)現(xiàn)。但是，“解開(kāi)”是有效果的：它將對(duì)每個(gè)元素的測(cè)試的數(shù)目從2降到 1.25。它是標(biāo)準(zhǔn)庫(kù)的實(shí)現(xiàn)人員不需要改動(dòng)任何接口就能采用的技術(shù)。
你將會(huì)在講述算法的常見(jiàn)書(shū)籍中看到一個(gè)不同的答案。需要對(duì)每個(gè)元素作兩次測(cè)試的原因是，如果到達(dá)區(qū)間結(jié)束還沒(méi)有找到所要找的元素，我們必須承認(rèn)已經(jīng)失敗。但是如果我們碰巧所要查找的元素總是存在，搜索絕不會(huì)失敗時(shí)，會(huì)怎么樣？在那種情況下，為區(qū)間結(jié)束作的測(cè)試是多余的；會(huì)沒(méi)有任何的理由認(rèn)為搜索算法應(yīng)該首先 掌握區(qū)間結(jié)束的信息（there wouldn’t be any reason for the search algorithm to keep track of the end of the range in the first place）。取代std::find()，我們可以如下實(shí)現(xiàn)線性搜索算法：
template <class InIter, class T>
InIter unguarded_find(InIter first, const T& val)
{
while (!(*first==val)) ++first;
}
Knuth 的線性搜索版本[注3]更接近unguarded_find()而不是std::find()。注意，unguarded_find()不是C++標(biāo)準(zhǔn)的 一部分。它比f(wàn)ind()危險(xiǎn)，通用性上也稍差。你只能在確保有一個(gè)元素等價(jià)于val時(shí)使用它－－這通常意味著你自己已經(jīng)將那個(gè)元素放在里面了，并作為區(qū) 間結(jié)束的哨兵。使用哨兵并不總是成立。(如果你正在搜索的是一個(gè)只讀區(qū)間怎么辦？)但當(dāng)它可用時(shí)，unguarded_find()比標(biāo)準(zhǔn)庫(kù)中的所有東西都更快，更簡(jiǎn)單。
二分搜索
線性搜索很簡(jiǎn)單，并且對(duì)于小區(qū)間，它是最好的方法。然而，如果區(qū)間越來(lái)越長(zhǎng)，它就不再是合理的解決方案了。在最近使用XSLT的時(shí)候，我想起這個(gè)問(wèn)題。我的XSLT腳本包括了一個(gè)類(lèi)似于這樣的一行：
<x:value-of select="/defs/data[@key=$r]"/>
我用來(lái)跑這個(gè)的XSLT引擎肯定是使用的線性搜索。我在一個(gè)list中搜索，并對(duì)list中的每個(gè)條目執(zhí)行了這個(gè)搜索。我的腳本是O(N2)的，它運(yùn)行需要花幾分鐘。
如果你正在搜索一個(gè)完全一般的區(qū)間，不能比線性搜索做得更好了。你必須檢查每一個(gè)元素，否則你漏掉的可能就是你正在尋找的。但如果你要求這個(gè)區(qū)間是以某種方式組織的，你就可以做得更好了。
比如，你可以要求區(qū)間是已排序的。如果有一個(gè)已序區(qū)間，就可以使用線性搜索的一個(gè)改良版本(當(dāng)你到達(dá)一個(gè)比所尋找的元素更大的元素時(shí)，不需要繼續(xù)到區(qū)間結(jié)束就可以知道搜索已經(jīng)失敗了)，但更好的方法是使用二分搜索。通過(guò)查看區(qū)間中央的元素，你就可以說(shuō)出所搜索的元素在前半部分還是后半部分；重復(fù)這個(gè)分解過(guò) 程，你不需要遍歷所有元素就能找到要找的元素。線性搜索需要O(N)的比較，而二分搜索只需要O(log N)。
標(biāo)準(zhǔn)運(yùn)行庫(kù)包含二分搜索的四個(gè)不同版本：lower_bound()，upper_bound()，equal_range()和 binary_search()。他們?nèi)慷加兄嗤男问剑航邮芤粋€(gè)區(qū)間、一個(gè)試圖查找的元素，和可選的比較函數(shù)。區(qū)間必須是根據(jù)此比較函數(shù)進(jìn)行過(guò)排序 的；如果不提供比較函數(shù)，它必須是根據(jù)通常的“<”運(yùn)算排序的。于是，舉例來(lái)說(shuō)，如果你正在一個(gè)升序排序的int數(shù)組中搜索時(shí)，你可以使用默認(rèn)行為。如果在一個(gè)降序排序的int數(shù)組中搜索時(shí)，你可以傳入一個(gè)std::greater<int>作為比較函數(shù)。
在四個(gè)二分搜索函數(shù)中，最沒(méi)用的一個(gè)是名字最一目了然的那個(gè)：binary_search()。它所返回是簡(jiǎn)單的yes或no：存在于區(qū)間中時(shí)返回 true，否則為false。但光這么一個(gè)信息沒(méi)什么用；我從未遇到什么場(chǎng)合來(lái)使用binary_search()。如果你想搜索的元素存在，你可能想知 道它的位置；如果不存在，你可能想知道如果它存在，這個(gè)位置是哪里。
關(guān)于元素的位置，你可以想問(wèn)幾個(gè)不同的問(wèn)題，而這正是二分搜索的幾個(gè)不同版本存在的原因。當(dāng)相同的元素存在好幾個(gè)拷貝時(shí)，它們的區(qū)別就很重要了。舉例來(lái)說(shuō)，假如你有一個(gè)int的數(shù)組，然后使用lower_bound()和upper_bound()都找尋同一個(gè)值：
int A[10] = { 1, 2, 3, 5, 5, 5, 5, 7, 8, 9 };
int* first = std::lower_bound(A+0, A+10, 5);
int* last = std::upper_bound(A+0, A+10, 5);
名字first和last暗示了區(qū)別：lower_bound()返回第一個(gè)你正在尋找的數(shù)值(對(duì)本例，是&A[3])，而upper_bound ()返回最后一個(gè)你正尋找的值的下一個(gè)的iterator(對(duì)本例，是&A[7])。
如果你搜索的值不存在，你將得到如果它存在的話，應(yīng)該位于的位置。和前面一樣，我們可以寫(xiě)：
int* first = std::lower_bound(A+0, A+10, 6);
int* last = std::upper_bound(A+0, A+10, 6);
first和last都將等于&A[7]，因?yàn)檫@是6在不違背排序時(shí)可以插入的唯一位置。
實(shí)踐中，你看不到lower_bound()的調(diào)用后面立即跟一個(gè)upper_bound()。如果你同時(shí)需要這兩個(gè)信息，那正是引入最后一個(gè)二分搜索算法的原因：equal_range()返回一個(gè)pair，第一個(gè)元素是lower_bound()將要返回的值，第二個(gè)元素是upper_bound()的 返回值。
直到此時(shí)，我在討論中故意比較粗略：我說(shuō)了lower_bound()和upper_bound()找一個(gè)值，但沒(méi)有正確說(shuō)明它的含義。如果你寫(xiě)
iterator i = std::lower_bound(first, last, x);
而且搜尋成功，你保證 *i 和 x 相等嗎？不一定！lower_bound()和upper_bound()從不對(duì)等價(jià)性進(jìn)行測(cè)試（WQ注：邏輯相等，使用operator==()）。它們使用你提供的比較函數(shù)：operator<()或其它一些功能象“less than”的比較函數(shù)。這意味著在*i不小于x并且x不小于*i時(shí)，搜索成功（WQ注，即等值性，數(shù)學(xué)相等）。
這個(gè)區(qū)別看起來(lái)象吹毛求疵，但它不是。假如你一些具有很多字段的復(fù)雜記錄，你使用其中的一個(gè)字段作為排序的key值（比如，人的姓）。兩個(gè)記錄可能有相同的key值，于是，即使所有其它子段都是不同的，它們哪一個(gè)也不小于另外一個(gè)。
一旦開(kāi)始想到記錄和key值，二分搜索的另外一個(gè)問(wèn)題就變得很自然了：你能用二分搜索根據(jù)key來(lái)搜索記錄嗎？更具體些，假設(shè)我們定義了一個(gè)struct X：
struct X {
int id;
... // other fields
};
再假設(shè)有一個(gè)vector<X>，根據(jù)元素的id進(jìn)行過(guò)排序。你如何使用二分搜索來(lái)找到一個(gè)指定id（比如148）的X？
一個(gè)方法是創(chuàng)建一個(gè)有著指定的id啞X對(duì)象，并在二分搜索中使用它：
X dummy;
dummy.id = 148;
vector<X>::iterator = lower_bound(v.begin(), v.end(), dummy, X_compare);
目前而言，這是最可靠的方法。如果你關(guān)心最大程度的可移植性，它是你所應(yīng)該使用的方法。另一方面，它不是非常優(yōu)雅。你必須創(chuàng)建一個(gè)完整的X對(duì)象，雖然你需要的只是其中一個(gè)字段；其它字段不得不被初始化為默認(rèn)值或隨機(jī)值。那個(gè)初始化可能是不方便的，昂貴的，或有時(shí)甚至不可能的。
可能直接將id傳給lower_bound()嗎？也許，通過(guò)傳入一個(gè)異質(zhì)比較函數(shù)，它接受一個(gè)X和一個(gè)id？這個(gè)問(wèn)題沒(méi)有一個(gè)簡(jiǎn)單的答案。C++標(biāo)準(zhǔn)沒(méi)有 完全說(shuō)清楚是否允許這樣的異質(zhì)比較函數(shù)；依我之見(jiàn)，對(duì)標(biāo)準(zhǔn)的最自然的讀解是不允許。在現(xiàn)今的實(shí)踐中，異質(zhì)比較函數(shù)在一些實(shí)作上可行，而在另外一些上不行。 另一方面，C++標(biāo)準(zhǔn)化委員會(huì)認(rèn)為這是一個(gè)缺陷，并且在未來(lái)版本的標(biāo)準(zhǔn)將明確是否允許異質(zhì)比較函數(shù)[注4]。
總結(jié)
C++運(yùn)行庫(kù)還提供了其它一些形式的搜索算法。使用find()和lower_bound()，搜索只限于單個(gè)元素，但標(biāo)準(zhǔn)運(yùn)行庫(kù)還提供了serach()，它尋找整個(gè)子區(qū)間。比如，你可以在一個(gè)字符串s中搜索一個(gè)單詞：
std::string the = "the";
std::string::iterator i = std::search(s.begin(), s.end(), the.begin(), the.end());
返回值，i，將指向“the”在s中第一次出現(xiàn)的開(kāi)始處－－或，和往常一樣，如果“the”不存在將返回s.end()。還有一個(gè)變種以從尾部開(kāi)始搜索：
std::find_end(s.begin(), s.end(), the.begin(), the.end());
它返回一個(gè)iterator，指向“the”最后出現(xiàn)處的開(kāi)始，而不是第一個(gè)。(如果你認(rèn)為這很奇怪，search的逆向變種叫find_end()而不是search_end()，那么你并不孤獨(dú)。)
搜索可以被封裝入數(shù)據(jù)結(jié)構(gòu)。最明顯地，標(biāo)準(zhǔn)運(yùn)行庫(kù)的關(guān)聯(lián)容器，set、multiset、map和multimap，被特別設(shè)計(jì)為根據(jù)key進(jìn)行搜索將很高 效[注5]。運(yùn)行庫(kù)的string類(lèi)也提供了許多搜索用的成員函數(shù)：find()、rfind()、find_first_of()、 find_last_of()、find_first_not_of()和find_last_not_of()。我建議避免使用它們。我發(fā)現(xiàn)這些特殊的 成員函數(shù)難以記憶，因?yàn)樗鼈儞碛腥绱硕嗟男问剑⑶医涌谛问脚c運(yùn)行庫(kù)的其它部分不同；無(wú)論如何，他們不會(huì)提供任何不能從find()、find_if ()、search()得到的功能。
但是，如果你仍然認(rèn)為看到了一些重要的省略，你是正確的！我沒(méi)有提到hash表，因?yàn)闃?biāo)準(zhǔn)運(yùn)行庫(kù)中沒(méi)有hash表。我提到了search()的子區(qū)間匹配，但那當(dāng)然只是模式匹配的一個(gè)特例－－標(biāo)準(zhǔn)運(yùn)行庫(kù)中沒(méi)有正則表達(dá)式搜索或任何類(lèi)似的東西。
C++標(biāo)準(zhǔn)化委員會(huì)剛剛開(kāi)始考慮對(duì)標(biāo)準(zhǔn)運(yùn)行庫(kù)擴(kuò)充，而hash表和正則表達(dá)式是未來(lái)版本的標(biāo)準(zhǔn)的優(yōu)先候選者。如果你認(rèn)為標(biāo)準(zhǔn)運(yùn)行庫(kù)缺少了什么，并且你想提交一份提議，那么現(xiàn)在是你應(yīng)該開(kāi)始準(zhǔn)備時(shí)候了。