通過mismatch或lexicographical比較

實作簡單的忽略大小寫字串比較

一個STL菜鳥最常問的問題是「我怎麼使用STL來進行忽略大小寫的字符串比較？」這是一個令人迷惑的簡單問題。忽略大小寫字串比較要麼真的簡單要麼真的困難，依賴於你要多一般地解決這個問題。如果你忽略國際化問題而且只關注於設計成字串strcmp那樣的類型，這個任務很簡單。如果你要有 strcmp不具有的按語言處理字串中的字元的能力（也就是，容納文字的字串是除了英語以外的語言 ）或程序使用了區域設置而不是預設這個任務很困難。

（這個問題一個比較難的版本也能用STL解決。另文說明 ）為了讓簡單的問題變得更有挑戰性，我會處理兩次。想要使用忽略大小寫比較的程式設計師通常需要兩種不同的呼叫介面，一種類似 strcmp（返回一個負數、零或正數），另一種類似operator（返回true或 false）。因此我會展示怎麼使用STL算法實現兩種呼叫介面。

但是首先，我們需要一種方法來確定兩個字元除了大小寫之外是否相等。當需要考慮國際化問題時，這是一複雜的問題。下面的字符比較顯然是一個過分簡單的解決方案，但它類似strcmp進行的字串比較，因為我只考慮類似strcmp的字串比較，不考慮國際化問題，這個函數就夠了：

int ciCharCompare(char c1, char c2)				// 忽略大小寫比較字符
{												// c1和c2，如果c1 < c2返回-1，
												// 如果c1==c2返回0，如果c1 > c2返回1
	int Ic1 = tolower(static_cast(c1)); 				// 這些語句的解釋
	int Ic2 = tolower(static_cast(c2));				// 看下文

	if (Ic1 < Ic2) return -1;
	if (lc1 > Ic2) return 1;
	return 0;
}

這個函數遵循了strcmp，可以返回一個負數、零或正數，依賴於c1和c2之間的關係。與strcmp不同的是，ciCharCompare在進行比較前把兩個參數轉化為小寫。這就產生了忽略大小寫的字元比較。

正如（也是）裡的很多函數，tolower 的參數和返回值類型是int ，但除非這個 int是EOF，它的值必須能表現為一個unsigned char。在C和C++中，char可能是或可能不是有符號的（依賴於實作），當char有符號(Signed)時，唯一確認它的值可以表現為unsigned char的方式是在呼叫tolower之前轉換一下。這就解釋了上面程式碼中的轉換。（在char已經是無符號(Unsigned)的實現中，這個轉換沒有作用。）這也解釋了保存tolower返回值的是int而不是char。

給定了ciCharCompare，就很容易寫出我們的第一個忽略大小寫的兩個字串比較函數，提供了一個類似strcmp的函式介面。 ciStringCompare這個函數，返回一個負數、零或正數，依賴於要比較的字串的關係。它基於mismatch算法，因為mismatch確定了兩個區間中第一個對應的不相同的值的位置。

在我們可以調用mismatch之前，我們必須先滿足它的前提。特別是，我們必須確定一個字串是否比另一個短，短的字串作為第一個區間傳遞。因此我們可以把真正的工作放在一個叫做ciStringCompareImpl的函數，然後讓ciStringCompare簡單地確保傳進去的實參順序正確，如果實參交換了就調整返回值：

int ciStringCompareImpl(const string& s1,		// 實作看下文
			const string& s2);

int ciStringCompare(const string& s1, const string& s2)
{

	if (s1.size() <= s2.size()) return ciStringCompareImpl(s1, s2);
	else return -ciStringCompareImpl(s2, s1);

}

在ciStringCompareImpl中，大部分工作由mismatch來完成。它返回一對迭代器，表示了區間中第一個對應的字符不相同的位置：

int ciStringCompareImpl(const string& si, const strings s2)
{

    typedef pair								// PSCI = 「pair of
		    string::const_iterator> PSCI;      
											  // string::const_iterator」
    PSCI p = mismatch(							// 下文解釋了
                   s1.begin(), 
                   s1.end(),							   // 為什麼我們需要not2
                   s2.begin(),			           
		   not2(ptr_fun(ciCharCompare)));	

    if (p.first== s1.end()) {						  // 如果為真，s1等於
        if (p.second == 
            s2.end()) return 0;						   // s2或s1比s2短
	else return -1;
    }

    return ciCharCompare(*p.first, *p.second);	
											// 兩個字串的關係
}										       // 和不匹配的字元一樣

幸運的是，註釋把所有東西都弄清楚了。基本上，一旦你知道了字串中第一個不同字元的位置，就可以很容易決定哪個字串, 如果有的話，在另一個前面。唯一可能感到奇怪的是傳給mismatch的判斷式，也就是not2(ptr_fun(ciCharCompare))。當字元匹配時這個判斷式返回true，因為當判斷式返回false時
mismatch會停止。我們不能為此使用ciCharCompare，因為它返回-1、 1或0，而當字元匹配時它返回0，就像strcmp。如果我們把 ciCharCompare作為判斷式傳給mismatch，C++會把ciCharCompare的返回類型轉換為bool，而當然bool中零的等價物是false，正好和我們想要的相反！同樣的，當 ciCharCompare返回1或-1，那會被解釋成true，因為，就像C，所有非零整數值都看作 true。這再次和我們想要的相反。要修正這個語義倒置，我們在ciCharCompare前面放上not2和ptr_fun，而且我們都會一直很快樂地生活。

我們的第二個方法ciStringCompare是產生一個合適的STL判斷式：可以在關聯容器中用作比較函數的函數。這個實現很短也很好，因為我們需要做的是把ciCharCompare修改為一個有判斷式介面的字元比較函數，然後把進行字串比較的工作交給STL中名字第二長的算法—— lexicographical_compare：

bool ciCharLess(char c1, char c2)			     // 返回在忽略大小寫
{										     // 的情況下c1是否在c2前面；
    tolower(static_cast(c1)) < tolower(static_cast(c2));	
}								


bool ciStringCompare(const string& s1, const string& s2)
{
    return lexicographical_compare(
                          s1.begin(), s1.end(),				// 關於這個
		          s2.begin(), s2.end(),			       // 算法使用的
                          ciCharLess);					   // 討論在下文
}

不，我不會讓你再有懸念了。名字最長的算法是set_symmetric_difference。

如果你熟悉lexicographical_compare的行為，上面的代碼在清楚不過了。如果你不明瞭的話，就可能像隔著一塊混凝土一樣。幸運的是，要把混凝土換成玻璃並不難。

lexicographical_compare是strcmp的泛型版本。strcmp只對字符數組起作用，但 lexicographical_compare對所有任何類型的值的區間都起作用。同時，strcmp總是比較兩個字元看它們的關係是相等、小於或大於另一個。lexicographical_compare可以傳入一個決定兩個值是否滿足一個使用者定義標準的二元判斷式。

在上面的調用中，lexicographical_compare用來尋找s1和s2第一個不同的位置，基於呼叫 ciCharLess 的結果。如果，使用那個位置的字元ciCharLess返回true，lexicographical_compare也是；如果，在第一個字元不同的位置，從第一個字串來的字元先於對應的來自第二個字串的字元，第一個字串就先於第二個。就像strcmp，lexicographical_compare認為兩個相等值的區間是相等的，因此它對於這樣的兩個區間返回false：第一個區間不在第二個之前。也像strcmp，如果第一個區間在發現不同的對應值之前就結束了，lexicographical_compare返回true：一個先於任何區間的前綴是一個前綴。

談了很多關於mismatch和lexicographical_compare。雖然我專注於可移植性，但如果我沒有提到忽略大小寫字串比較函數作為對標準C函式庫的非標準擴展而廣泛存在，我可能是怠忽職守的。它們一般有stricmp或strcmpi這樣的名字，而且它們一般和我們開發的函數一樣沒有提供更多對國際化的支援。如果你想犧牲一些移植性，你知道你的字串沒有包含嵌入的null，而且你不關心國際化，你可以找到完全不用 STL，實作一個忽略大小寫字串比較最簡單的方式。取而代之的是，它把兩個字串都轉換為const char*指標，然後對指標使用stricmp或 strcmpi：

int ciStringCompare(const string& s1, const string& s2)
{
	return stricmp(s1.c_str(), s2.c_str());		   // 你的系統上的函數名可能不是stricmp  
}								   


有的人可能稱此為技巧（hack），但stricmp/strcmpi被最佳化為只做一件事情，對長字串運行起來一般比通用的
算法mismatch 和lexicographical_compare快得多。如果那對你很重要，你可能不在乎你用非標準C函數完成
標準STL算法。有時候使用STL去認識到其他優越的方法是最為有效的方式。