條款45：注意count、find、binary_search、lower_bound、upper_bound和equal_range的區(qū)別

你要尋找什么，而且你有一個(gè)容器或者你有一個(gè)由迭代器劃分出來(lái)的區(qū)間——你要找的東西就在里面。你要怎么完成搜索呢？你箭袋中的箭有這些：count、count_if、find、find_if、binary_search、lower_bound、upper_bound和equal_range。面對(duì)著它們，你要怎么做出選擇？

簡(jiǎn)單。你尋找的是能又快又簡(jiǎn)單的東西。越快越簡(jiǎn)單的越好。

暫時(shí)，我假設(shè)你有一對(duì)指定了搜索區(qū)間的迭代器。然后，我會(huì)考慮到你有的是一個(gè)容器而不是一個(gè)區(qū)間的情況。

要選擇搜索策略，必須依賴于你的迭代器是否定義了一個(gè)有序區(qū)間。如果是，你就可以通過(guò)binary_search、lower_bound、upper_bound和equal_range來(lái)加速（通常是對(duì)數(shù)時(shí)間——參見(jiàn)條款34）搜索。如果迭代器并沒(méi)有劃分一個(gè)有序區(qū)間，你就只能用線性時(shí)間的算法count、count_if、find和find_if。在下文中，我會(huì)忽略掉count和find是否有_if的不同，就像我會(huì)忽略掉binary_search、lower_bound、upper_bound和equal_range是否帶有判斷式的不同。你是依賴默認(rèn)的搜索謂詞還是指定一個(gè)自己的，對(duì)選擇搜索算法的考慮是一樣的。

如果你有一個(gè)無(wú)序區(qū)間，你的選擇是count或著find。它們分別可以回答略微不同的問(wèn)題，所以值得仔細(xì)去區(qū)分它們。count回答的問(wèn)題是：“是否存在這個(gè)值，如果有，那么存在幾份拷貝？”而find回答的問(wèn)題是：“是否存在，如果有，那么它在哪兒？”

假設(shè)你想知道的東西是，是否有一個(gè)特定的Widget值w在list中。如果用count，代碼看起來(lái)像這樣：

list<Widget> lw;			// Widget的list
Widget w;				// 特定的Widget值
...
if (count(lw.begin(), lw.end(), w)) {
...			// w在lw中
} else {
...			// 不在
}

這里示范了一種慣用法：把count用來(lái)作為是否存在的檢查。count返回零或者一個(gè)正數(shù)，所以我們把非零轉(zhuǎn)化為true而把零轉(zhuǎn)化為false。如果這樣能使我們要做的更加顯而易見(jiàn)：

if (count(lw.begin(), lw.end(), w) != 0) ...

而且有些程序員這樣寫(xiě)，但是使用隱式轉(zhuǎn)換則更常見(jiàn)，就像最初的例子。

和最初的代碼比較，使用find略微更難懂些，因?yàn)槟惚仨殭z查find的返回值和list的end迭代器是否相等：

if (find(lw.begin(), lw.end(), w) != lw.end()) {
...				// 找到了
} else {
...				// 沒(méi)找到
}

如果是為了檢查是否存在，count這個(gè)慣用法編碼起來(lái)比較簡(jiǎn)單。但是，當(dāng)搜索成功時(shí)，它的效率比較低，因?yàn)楫?dāng)找到匹配的值后find就停止了，而count必須繼續(xù)搜索，直到區(qū)間的結(jié)尾以尋找其他匹配的值。對(duì)大多數(shù)程序員來(lái)說(shuō)，find在效率上的優(yōu)勢(shì)足以證明略微增加復(fù)雜度是合適的。

通常，只知道區(qū)間內(nèi)是否有某個(gè)值是不夠的。取而代之的是，你想獲得區(qū)間中的第一個(gè)等于該值的對(duì)象。比如，你可能想打印出這個(gè)對(duì)象，你可能想在它前面插入什么，或者你可能想要?jiǎng)h除它（但當(dāng)?shù)鷷r(shí)刪除的引導(dǎo)參見(jiàn)條款9）。當(dāng)你需要知道的不止是某個(gè)值是否存在，而且要知道哪個(gè)對(duì)象（或哪些對(duì)象）擁有該值，你就得用find：

list<Widget>::iterator i = find(lw.begin(), lw.end(), w);
if (i != lw.end()) {
...				// 找到了，i指向第一個(gè)
} else {
...				// 沒(méi)有找到
}

對(duì)于有序區(qū)間，你有其他的選擇，而且你應(yīng)該明確的使用它們。count和find是線性時(shí)間的，但有序區(qū)間的搜索算法（binary_search、lower_bound、upper_bound和equal_range）是對(duì)數(shù)時(shí)間的。

從無(wú)序區(qū)間遷移到有序區(qū)間導(dǎo)致了另一個(gè)遷移：從使用相等來(lái)判斷兩個(gè)值是否相同到使用等價(jià)來(lái)判斷。條款19由一個(gè)詳細(xì)地講述了相等和等價(jià)的區(qū)別，所以我在這里不會(huì)重復(fù)。取而代之的是，我會(huì)簡(jiǎn)單地說(shuō)明count和find算法都用相等來(lái)搜索，而binary_search、lower_bound、upper_bound和equal_range則用等價(jià)。

要測(cè)試在有序區(qū)間中是否存在一個(gè)值，使用binary_search。不像標(biāo)準(zhǔn)C庫(kù)中的（因此也是標(biāo)準(zhǔn)C++庫(kù)中的）bsearch，binary_search只返回一個(gè)bool：這個(gè)值是否找到了。binary_search回答這個(gè)問(wèn)題：“它在嗎？”它的回答只能是是或者否。如果你需要比這樣更多的信息，你需要一個(gè)不同的算法。

這里有一個(gè)binary_search應(yīng)用于有序vector的例子（你可以從條款23中知道有序vector的優(yōu)點(diǎn)）：

vector<Widget> vw;			// 建立vector，放入
...				// 數(shù)據(jù)，
sort(vw.begin(), vw.end());		// 把數(shù)據(jù)排序
Widget w;				// 要找的值
...
if (binary_search(vw.begin(), vw.end(), w)) {
...			// w在vw中
} else {
...			// 不在
}

如果你有一個(gè)有序區(qū)間而且你的問(wèn)題是：“它在嗎，如果是，那么在哪兒？”你就需要equal_range，但你可能想要用lower_bound。我會(huì)很快討論equal_range，但首先，讓我們看看怎么用lower_bound來(lái)在區(qū)間中定位某個(gè)值。

當(dāng)你用lower_bound來(lái)尋找一個(gè)值的時(shí)候，它返回一個(gè)迭代器，這個(gè)迭代器指向這個(gè)值的第一個(gè)拷貝（如果找到的話）或者到可以插入這個(gè)值的位置（如果沒(méi)找到）。因此lower_bound回答這個(gè)問(wèn)題：“它在嗎？如果是，第一個(gè)拷貝在哪里？如果不是，它將在哪里？”和find一樣，你必須測(cè)試lower_bound的結(jié)果，來(lái)看看它是否指向你要尋找的值。但又不像find，你不能只是檢測(cè)lower_bound的返回值是否等于end迭代器。取而代之的是，你必須檢測(cè)lower_bound所標(biāo)示出的對(duì)象是不是你需要的值。

很多程序員這么用lower_bound：

vector<Widget>::iterator i = lower_bound(vw.begin(), vw.end(), w);
if (i != vw.end() && *i == w) {	// 保證i指向一個(gè)對(duì)象；
// 也就保證了這個(gè)對(duì)象有正確的值。
// 這是個(gè)bug！
...			// 找到這個(gè)值，i指向
// 第一個(gè)等于該值的對(duì)象
} else {
...			// 沒(méi)找到
}

大部分情況下這是行得通的，但不是真的完全正確。再看一遍檢測(cè)需要的值是否找到的代碼：

if (i != vw.end() && *i == w) ...

這是一個(gè)相等的測(cè)試，但lower_bound搜索用的是等價(jià)。大部分情況下，等價(jià)測(cè)試和相等測(cè)試產(chǎn)生的結(jié)果相同，但就像條款19論證的，相等和等價(jià)的結(jié)果不同的情況并不難見(jiàn)到。在這種情況下，上面的代碼就是錯(cuò)的。

要完全完成，你就必須檢測(cè)lower_bound返回的迭代器指向的對(duì)象的值是否和你要尋找的值等價(jià)。你可以手動(dòng)完成（條款19演示了你該怎么做，當(dāng)它值得一做時(shí)條款24提供了一個(gè)例子），但可以更狡猾地完成，因?yàn)槟惚仨毚_認(rèn)使用了和lower_bound使用的相同的比較函數(shù)。一般而言，那可以是一個(gè)任意的函數(shù)（或函數(shù)對(duì)象）。如果你傳遞一個(gè)比較函數(shù)給lower_bound，你必須確認(rèn)和你的手寫(xiě)的等價(jià)檢測(cè)代碼使用了相同的比較函數(shù)。這意味著如果你改變了你傳遞給lower_bound的比較函數(shù)，你也得對(duì)你的等價(jià)檢測(cè)部分作出修改。保持比較函數(shù)同步不是火箭發(fā)射，但卻是另一個(gè)要記住的東西，而且我想你已經(jīng)有很多需要你記的東西了。

這兒有一個(gè)簡(jiǎn)單的方法：使用equal_range。equal_range返回一對(duì)迭代器，第一個(gè)等于lower_bound返回的迭代器，第二個(gè)等于upper_bound返回的（也就是，等價(jià)于要搜索值區(qū)間的末迭代器的下一個(gè)）。因此，equal_range，返回了一對(duì)劃分出了和你要搜索的值等價(jià)的區(qū)間的迭代器。一個(gè)名字很好的算法，不是嗎？（當(dāng)然，也許叫equivalent_range會(huì)更好，但叫equal_range也非常好。）

對(duì)于equal_range的返回值，有兩個(gè)重要的地方。第一，如果這兩個(gè)迭代器相同，就意味著對(duì)象的區(qū)間是空的；這個(gè)只沒(méi)有找到。這個(gè)結(jié)果是用equal_range來(lái)回答“它在嗎？”這個(gè)問(wèn)題的答案。你可以這么用：

vector<Widget> vw;
...
sort(vw.begin(), vw.end());
typedef vector<Widget>::iterator VWIter;	// 方便的typedef
typedef pair<VWIter, VWIter> VWIterPair;
VWIterPair p = equal_range(vw.begin(), vw.end(), w);
if (p.first != p.second) {			// 如果equal_range不返回
// 空的區(qū)間...
...				// 說(shuō)明找到了，p.first指向
// 第一個(gè)而p.second
// 指向最后一個(gè)的下一個(gè)
} else {
...				// 沒(méi)找到，p.first和
// p.second都指向搜索值
}					// 的插入位置

這段代碼只用等價(jià)，所以總是正確的。

第二個(gè)要注意的是equal_range返回的東西是兩個(gè)迭代器，對(duì)它們作distance就等于區(qū)間中對(duì)象的數(shù)目，也就是，等價(jià)于要尋找的值的對(duì)象。結(jié)果，equal_range不光完成了搜索有序區(qū)間的任務(wù)，而且完成了計(jì)數(shù)。比如說(shuō)，要在vw中找到等價(jià)于w的Widget，然后打印出來(lái)有多少這樣的Widget存在，你可以這么做：

VWIterPair p = equal_range(vw.begin(), vw.end(), w);
cout << "There are " << distance(p.first, p.second)
<< " elements in vw equivalent to w.";

到目前為止，我們所討論的都是假設(shè)我們要在一個(gè)區(qū)間內(nèi)搜索一個(gè)值，但是有時(shí)候我們更感興趣于在區(qū)間中尋找一個(gè)位置。比如，假設(shè)我們有一個(gè)Timestamp類和一個(gè)Timestamp的vector，它按照老的timestamp放在前面的方法排序：

class Timestamp { ... };
bool operator<(const Timestamp& lhs,		// 返回在時(shí)間上lhs
const Timestamp& rhs);		// 是否在rhs前面
vector<Timestamp> vt;			// 建立vector，填充數(shù)據(jù)，
...					// 排序，使老的時(shí)間
sort(vt.begin(), vt.end());			// 在新的前面

現(xiàn)在假設(shè)我們有一個(gè)特殊的timestamp——ageLimit，而且我們從vt中刪除所有比ageLimit老的timestamp。在這種情況下，我們不需要在vt中搜索和ageLimit等價(jià)的Timestamp，因?yàn)榭赡懿淮嬖谌魏蔚葍r(jià)于這個(gè)精確值的元素。 取而代之的是，我們需要在vt中找到一個(gè)位置：第一個(gè)不比ageLimit更老的元素。這是再簡(jiǎn)單不過(guò)的了，因?yàn)閘ower_bound會(huì)給我們答案的：

Timestamp ageLimit;
...
vt.erase(vt.begin(), lower_bound(vt.begin(),	// 從vt中排除所有
vt.end(),				// 排在ageLimit的值
ageLimit));			// 前面的對(duì)象

如果我們的需求稍微改變了一點(diǎn)，我們要排除所有至少和ageLimit一樣老的timestamp，也就是我們需要找到第一個(gè)比ageLimit年輕的timestamp的位置。這是一個(gè)為upper_bound特制的任務(wù)：

vt.erase(vt.begin(), upper_bound(vt.begin(),	// 從vt中除去所有
vt.end(),				// 排在ageLimit的值前面
ageLimit));			// 或者等價(jià)的對(duì)象

如果你要把東西插入一個(gè)有序區(qū)間，而且對(duì)象的插入位置是在有序的等價(jià)關(guān)系下它應(yīng)該在的地方時(shí)，upper_bound也很有用。比如，你可能有一個(gè)有序的Person對(duì)象的list，對(duì)象按照name排序：

class Person {
public:
...
const string& name() const;
...
};
struct PersonNameLess:
public binary_function<Person, Person, bool> {	// 參見(jiàn)條款40
bool operator()(const Person& lhs, const Person& rhs) const
{
return lhs.name() < rhs.name();
}
};
list<Person> lp;
...
lp.sort(PersonNameLess());			// 使用PersonNameLess排序lp

要保持list仍然是我們希望的順序（按照name，插入后等價(jià)的名字仍然按順序排列），我們可以用upper_bound來(lái)指定插入位置：

Person newPerson;
...
lp.insert(upper_bound(lp.begin(),		// 在lp中排在newPerson
lp.end(),				// 之前或者等價(jià)
newPerson,			// 的最后一個(gè)
PersonNameLess()),			// 對(duì)象后面
newPerson);			// 插入newPerson

這工作的很好而且很方便，但很重要的是不要被誤導(dǎo)——錯(cuò)誤地認(rèn)為upper_bound的這種用法讓我們魔術(shù)般地在一個(gè)list里在對(duì)數(shù)時(shí)間內(nèi)找到了插入位置。我們并沒(méi)有——條款34解釋了因?yàn)槲覀冇昧薼ist，查找花費(fèi)線性時(shí)間，但是它只用了對(duì)數(shù)次的比較。

一直到這里，我都只考慮我們有一對(duì)定義了搜索區(qū)間的迭代器的情況。通常我們有一個(gè)容器，而不是一個(gè)區(qū)間。在這種情況下，我們必須區(qū)別序列和關(guān)聯(lián)容器。對(duì)于標(biāo)準(zhǔn)的序列容器（vector、string、deque和list），你應(yīng)該遵循我在本條款提出的建議，使用容器的begin和end迭代器來(lái)劃分出區(qū)間。

這種情況對(duì)標(biāo)準(zhǔn)關(guān)聯(lián)容器（set、multiset、map和multimap）來(lái)說(shuō)是不同的，因?yàn)樗鼈兲峁┝怂阉鞯某蓡T函數(shù)，它們往往是比用STL算法更好的選擇。條款44詳細(xì)說(shuō)明了為什么它們是更好的選擇，簡(jiǎn)要地說(shuō)，是因?yàn)樗鼈兏煨袨楦匀弧Ｐ疫\(yùn)的是，成員函數(shù)通常和相應(yīng)的算法有同樣的名字，所以前面的討論推薦你使用的算法count、find、equal_range、lower_bound或upper_bound，在搜索關(guān)聯(lián)容器時(shí)你都可以簡(jiǎn)單的用同名的成員函數(shù)來(lái)代替。

調(diào)用binary_search的策略不同，因?yàn)檫@個(gè)算法沒(méi)有提供對(duì)應(yīng)的成員函數(shù)。要測(cè)試在set或map中是否存在某個(gè)值，使用count的慣用方法來(lái)對(duì)成員進(jìn)行檢測(cè)：

set<Widget> s;		// 建立set，放入數(shù)據(jù)
...
Widget w;			// w仍然是保存要搜索的值
...
if (s.count(w)) {
...		// 存在和w等價(jià)的值
} else {
...		// 不存在這樣的值
}

要測(cè)試某個(gè)值在multiset或multimap中是否存在，find往往比count好，因?yàn)橐坏┱业降扔谄谕档膯蝹€(gè)對(duì)象，find就可以停下了，而count，在最遭的情況下，必須檢測(cè)容器里的每一個(gè)對(duì)象。（對(duì)于set和map，這不是問(wèn)題，因?yàn)閟et不允許重復(fù)的值，而map不允許重復(fù)的鍵。）

但是，count給關(guān)聯(lián)容器計(jì)數(shù)是可靠的。特別，它比調(diào)用equal_range然后應(yīng)用distance到結(jié)果迭代器更好。首先，它更清晰：count 意味著“計(jì)數(shù)”。第二，它更簡(jiǎn)單；不用建立一對(duì)迭代器然后把它的組成（譯注：就是first和second）傳給distance。第三，它可能更快一點(diǎn)。

要給出所有我們?cè)诒緱l款中所考慮到的，我們的從哪兒著手？下面的表格道出了一切。

上表總結(jié)了要怎么操作有序區(qū)間，equal_range的出現(xiàn)頻率可能令人吃驚。當(dāng)搜索時(shí)，這個(gè)頻率因?yàn)榈葍r(jià)檢測(cè)的重要性而上升了。對(duì)于lower_bound和upper_bound，它很容易在相等檢測(cè)中退卻，但對(duì)于equal_range，只檢測(cè)等價(jià)是很自然的。在第二行有序區(qū)間，equal_range打敗了find還因?yàn)橐粋€(gè)理由：equal_range花費(fèi)對(duì)數(shù)時(shí)間，而find花費(fèi)線性時(shí)間。

對(duì)于multiset和multimap，當(dāng)你在搜索第一個(gè)等于特定值的對(duì)象的那一行，這個(gè)表列出了find和lower_bound兩個(gè)算法作為候選。 已對(duì)于這個(gè)任務(wù)find是通常的選擇，而且你可能已經(jīng)注意到在set和map那一列里，這項(xiàng)只有find。但是對(duì)于multi容器，如果不只有一個(gè)值存在，find并不保證能識(shí)別出容器里的等于給定值的第一個(gè)元素；它只識(shí)別這些元素中的一個(gè)。如果你真的需要找到等于給定值的第一個(gè)元素，你應(yīng)該使用lower_bound，而且你必須手動(dòng)的對(duì)第二部分做等價(jià)檢測(cè)，條款19的內(nèi)容可以幫你確認(rèn)你已經(jīng)找到了你要找的值。（你可以用equal_range來(lái)避免作手動(dòng)等價(jià)檢測(cè)，但是調(diào)用equal_range的花費(fèi)比調(diào)用lower_bound多得多。）

在count、find、binary_search、lower_bound、upper_bound和equal_range中做出選擇很簡(jiǎn)單。當(dāng)你調(diào)用時(shí)，選擇算法還是成員函數(shù)可以給你需要的行為和性能，而且是最少的工作。按照這個(gè)建議做（或參考那個(gè)表格），你就不會(huì)再有困惑。