區域設置和忽略大小寫的字串比較
「通過mismatch或lexicographical比較 實作簡單的忽略大小寫字串比較」
解釋了怎樣使用mismatch和 lexicographical_comapre實現忽略大小寫的字串比較，但是它也指出一個真正通用的解決方案必須考慮區域設置。本書是關於STL 的，而非國際化的，因此我幾乎沒有提到任何關於區域設置的東西。不過，Matt Austern，《Generic Programming and the STL》[4]的作者，在2000年5月《C++ Report》[11]的專欄裡提到了涉及區域設置的忽略大小寫字串比較。為了完整地講述這個重要的主題，我很高興能在這裡再版他的專欄，而且我感謝Matt和101communications准許我這麼做。
如何進行忽略大小寫的字串比較
Matt Austern
如果你寫的程序曾經用到過string（誰沒有嗎？），有時候可能你需要處理兩個除了大小寫不同其他都相同的字串。即，你需要讓比較——相等、小 於、字子串匹配、排序——都忽略大小寫。而且，的確，關於標準C++庫的最常見問題之一是怎樣使string忽略大小寫。這個問題已經被回答很多次了。很多 答案是錯誤的。
首先，讓我們放棄試圖寫忽略大小寫string類的想法。是的，它在技術上多多少少是可能的。標準庫類型std::string其實只是一個模板
std::basic_string
- 你將不能做I/O，至少不能再沒有很多痛苦的情況下進行。標準庫裡的I/O類，比如std::
basic_istream和std::basic_ostream，與std::basic_string一樣在字串類型和特性上模板化。（再次強調，
std::ostream只是一個std::basic_ostream
>的別名。）特性參數必須匹配。如果你對字串使用std::basic_string ，你就必須對流使用std::basic_ostream 。你不能使用比如cin和cout那樣普通的流對象。 - 忽略大小寫不涉及一個對象，而涉及你怎樣使用一個對象。你可能在一些情況下非常需要把一個string當作關注大小寫而在其他情況下忽略大小寫。（或許取決於用戶控制的選項。）為這兩種應用定義不同的類型是在它們之間放置人造障礙。
- 它並不合適。正如所有的特性類[1]，char_traits是小的、簡單的和無狀態的。我們可以在本專欄的後面看到，正確的忽略大小寫比較不是這樣的東西。
- 它不夠。即使所有basic_string本身的成員函數都忽略大小寫，當你需要使用非成員泛型算法比如std::search和std::find_end時，將仍然沒有幫助。如果你決定，出於效率的考慮，從basic_string對象的容器改為字串表，它也將沒有幫助。
更自然地融合入標準庫設計的更好的解決方案是在當你需要時才進行忽略大小寫的比較。不要為string::find_first_of和 string::rfind那樣的成員函數而煩惱；它們的功能都存在於非成員泛型算法。同時，泛型算法靈活得足以適應忽略大小寫的字符串。例如，如果你需 要以忽略大小寫的順序排序一個字符串的集合，你需要做的就是提供適當的比較函數對象：
std::sort(C.begin(), C.end(), compare_without_case);
本專欄的剩餘部分將致力於怎樣寫那個函數對象。
第一次嘗試
有不止一種方法來按字母順序排列單詞。下次你在書店時，注意作者的名字是怎麼安排的：Mary McCarthy在Bernard Malamud之前，還是之後？（這是習慣的問題，而且這兩種方式我都看到過。）但是，字串比較的最簡單方式是我們都在小學學過的那個：詞典或者「字典 順序」比較，我們從一個一個字符的比較建立了字串比較。
詞典比較可能不適合專業應用（不是唯一的方法；庫可能以不同的方式排序人名和地名），但它適合大部分情況，而且這是字串比較在C++裡的預設意思。字串是字元的序列，如果x和y的類型是std::string，表達式x < y等價於這個表達式
std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()).
在這個表達式中，lexicographical_compare使用operator<比較單個字符，但還有一個版本的
lexicographical_compare讓你選擇自己的比較字符的方法。那個版本帶有五個實參，而不是四個；最後一個實參是一個函數對象，確定兩
個字符哪個應該在另一個之前的二元判定式。然後，為了用lexicographical_compare進行忽略大小寫比較，我們需要把它和忽略大小寫的字符比較函數對象結合起來。
在字元的忽略大小寫的比較後面的一般的想法是把兩個字元都轉化成大寫字母然後比較結果。這裡把那個想法顯而易見的轉換成一個C++函數物件，使用了來自標準C函式庫的一個廣為人知的函數：
struct lt_nocase
: public std::binary_function{
bool operator()(char x, char y) const {
return std::toupper(static_cast(x)) <
std::toupper(static_cast(y));
}
};
「任何複雜問題都有一個簡單、整潔而且錯誤的解決方案。」寫關於C++的書的人都喜歡這個類別，因為它是一個好的、簡單的例子。 我像其他人一樣心虛；我在我的書中多次使用了它。它幾乎是正確的，但是不夠好。問題是微妙的。
這裡有一個你可以開始發現問題的例子：
int main()
{
const char* s1 = "GEW334RZTRAMINER";
const char* s2 = "gew374rztraminer";
printf("s1 = %s, s2 = %sn", s1, s2);
printf("sl < s2: %sn",
std::lexicographical_compare(s1, s1 + 14, s2, s2 + 14, lt_nocase())
? "true" :"false");
}
你應該在你的系統上試試看。在我的系統上（一台運行IRIX 6.5的Silicon Graphics O2），這是輸出：
s1 = GEWÜRZTRAMINER, s2 = gewürztraminer
s1< s2: true
噢，多古怪。如果你做忽略大小寫比較，難道「gewürztraminer」和「GEWÜRZTRAMINER」不同嗎？現在做一個輕微的變化：如果你在printf語句之前插入這行
setlocale(LC_ALL, "de");
，突然輸出改變了：
s1 = GEWÜRZTRAMINER, s2 = gewürztraminer
s1 < s2: false
忽略大小寫的字串比較看起來更複雜。這表面上正確的程序非常依賴於大多數人經常忽略的東西：區域設置。
區域設置
一個char真的無異於一個小的整數。我們可以選擇把一個小的整數解釋成一個字符，但這種解釋並不通用。一些特定的數字應該被解釋為一個字母、一個標點符號還是一個不能打印的控制字元？
沒有一個正確的答案，而且直到關係到C和C++語言核心之前它們沒有任何不同。需要靠一些庫函數產生那些區別：例如，isalpha確定了一個字元 是否是字母，toupper把小寫字母轉換成大寫而對大寫字母或不是字母的字元則什麼都不做。所有那些都取決於本地文化和語言習慣：字母和非字母之間的區 別在英語中是一個意思，在瑞典語則是另一個意思。從小寫到大寫的轉換在羅馬和斯拉夫字母表中表示不同的東西，而在希伯來語中則沒有任何意義。
預設情況下，字元操作函數適用於簡單的英語文字字元集。字元'374'不受toupper影響，因為它不是一個字母；在一些系統上打印時它可能看起來像ü，但那和操作英語文字的C庫程序不相干。在ASCII字元集裡沒有ü字元。這行
setlocale(LC_ALL, "de");
告訴C函式庫開始根據德語習慣操作。（至少它在IRIX上是那樣。區域的名字沒有標準化。）德語中有字元 ü，因此 toupper 把 ü 改為 Ü。
如果這還不使你緊張，那麼馬上就會。雖然toupper可能看起來像帶有一個實參的簡單函數，但它也依賴於一個全局變數——不好，一個隱藏的全局變數。這引發了所有常見的困難：使用toupper的函數潛在地依賴於整個程序中的任何一個其他函數。
如果你把toupper用於忽略大小寫的字串比較，這可能是災難性的。如果你有一個依賴於循序 list 的演算法（比如 binary_search），然後一個新的區域設置引發了它後面的排序順序的改變，那將發生什麼？像這樣的程式碼不可重複使用：只是勉強可用。你不能在函式庫裡使 用它——函式庫可以用於任何種類的程序，不只是從未呼叫setlocale的程序。你可能在一個大的程序裡使用它卻僥倖逃過一劫，但你將有一個維護問題：或許 你能證明沒有其他模組呼叫了setlocale，但你能證明在程序明年的版本裡沒有其他模組呼叫setlocale嗎？
這個問題在C裡沒有好的解決方案。C函式庫只有一個全局的區域設置，沒別的了。在C++裡有一個解決方案。
C++中的區域設置
C++標準庫裡的區域設置不是深深地埋藏在函式庫實現裡的全局資料。它是一個std::locale類型的物件，而且你可以建立它和把它傳給函數，就像其他任何物件一樣。例如，你要建立一個表示通常區域的區域設置物件可以這麼寫
std::locale L = std::locale::classic();
或者你通過這麼寫建立一個德語區域設置
std::locale L("de");（和C函式庫裡的一樣，區域的名字沒有標準化。檢查你的實現文檔來查明提供了哪些有名字的區域設置。）
C++裡的區域設置分成多個方面（facet），每個方面處理一個國際化的不同方向，而函數std::use_facet從區域設置物件[2]中提取一個特定的方面。ctype方面處理字符分類，包括大小寫轉換。最後，如果c1和c2是char類型，這段程式碼將以適合區域設置L並以忽略大小寫的方式比較它們。
const std::ctype& ct = std::use_facet<:ctype> >(L);
bool result = ct.toupper(c1) < ct.toupper(c2);
也有一個特別的縮寫詞：你可以寫
std::toupper(c, L)
意思和
std::use_facet<:ctype>>(L).toupper(c)
相同（如果c是char類型）。不過，最小化調用use_facet的次數是值得的，因為它可能相當昂貴。
正如詞典比較不能適合於所有應用一樣，一個一個字符的大小寫轉換也不總是適合的。（例如，在德語裡，小寫字母「ß」對應著大寫序列「SS」。）但 是，不幸的是，一個一個字元的大小寫轉換是我們擁有的全部。C和C++標準函式庫都沒有提供任何一次用於不止一個字元的字串轉換形式。如果你的目的不能接受 這個限制，那麼就已經在標準庫的範圍之外了。
離題一下：另一個方面
如果你已經熟悉C++裡的區域設置，你可能想果用另一種方式進行字串比較：collate方面的存在正好封裝了排序的細節，而它有一個接口很像C 函式庫函數strcmp的成員函數。甚至有一個方便的特徵：如果L是一個區域設置對象，你可以通過寫L(x，y)而不是通過討厭地調用use_facet然後 調用collate成員函數來比較兩個字串。
「classic」區域設置有一個進行詞典排序的collate方面，和字串的operator<做的一樣，但其他區域設置進行任何種比較 都是合適的。如果你的系統正好有一個對任何你感興趣的語言進行忽略大小寫比較的區域設置，你可以使用它。那個區域設置甚至可能做出比一個一個字元比較更智 能化的事情！
不幸的是，這個建議，可能是真的，並不能幫助像我們這些沒有那樣的系統的人。或許有一天一套這樣的區域設置可以標準化，但現在它們還沒有。如果沒有人為你寫了一種忽略大小寫的比較，你就必須親自寫它。
忽略大小寫字串比較
使用ctype，用忽略大小寫字符比較構造忽略大小寫字串比較是很簡單的。這個版本不是最優的，但至少它是正確的。它基本上使用和以前相同的技術：使用lexicographical_compare比
較兩個字串，而且通過把兩個字元都轉換成大寫來比較它們。不過，這次我們小心地使用區域設置對象而不是全局變量。（另外說一下，把兩個字元都轉化成大寫
不一定總是等於把兩個字元都變成小寫的結果：沒有保證操作是可逆的。例如，在法語裡，通常忽略大寫字元上的重音標記。在法語區域設置中，toupper有
理由是有損轉換；它可以把「é」和「e」都轉換成同樣的大寫字元，「E」。那麼，在這樣的區域設置裡，使用toupper的忽略大小寫比較將說「é」和
「E」是等價字，而tolower將說它們不是。哪個是正確的答案？或許是前者，但它取決於語言，取決於當地習慣，取決於你的應用程序。）
struct lt_str_1
: public std::binary_function<:string> {
struct lt_char {
const std::ctype& ct;
lt_char(const std::ctype& c) : ct(c) {}
bool operator()(char x, char y) const {
return ct.toupper(x) < ct.toupper(y);
}
};
std::locale loc;
const std::ctype& ct;
lt_str_1(const std::locale& L = std::locale::classic())
: loc(L), ct(std::use facet<:ctype>>(loc)) {}
bool operator()(const std::string& x, const std::string& y) const{
return std::lexicographical_compare(x.begin(), x.end(),
y.begin(), y.end(),
lt_char(ct));
}
};
這還不很好；它比應該的慢。問題是討厭的和技術性的：我們在循環內呼叫toupper，而C++標準要求toupper是虛擬函數呼叫。一些最佳化編譯器可能聰明得足以把虛擬函數開銷移到循環之外，但是大多數不是。循環內的虛擬函數呼叫應該避免。
在這裡，避免它不是很簡單。你可能想到正確答案是ctype的另一個成員函數，
const char* ctype::toupper(char* f, char* l) const
這改變了區間[f, l)內的字元大小寫。不幸的是，這不完全是我們的目標的正確接口。使用它來比較兩個字串要求把兩個字串都拷貝到緩衝區，然後把緩衝區轉化成大寫。那些緩衝區從哪裡來？它們不能是固定大小的數組（多大才足夠大？），但動態數組需要昂貴的記憶體分配。
另一個解決方案是每次對一個字元進行大小寫轉換並緩存結果。這不是一個完全通用的解決方案——例如，如果你用的是32位UCS 4字元，它將完全不能工作。不過，如果你用char（大部分系統上是8位），在比較函數物件裡維護一個256字組的大小寫轉換信息不是沒有道理的。
struct lt_str_2:
public std::binary_function<:string> {
struct lt_char {
const char* tab;
lt_char(const char* t) : tab(t) {}
bool operator()(char x, char y) const {
return tab[x - CHAR_MIN] < tab[y - CHAR_MIN];
}
};
char tab[CHAR_MAX - CHAR_MIN + 1];
lt_str_2(const std::locale& L = std::locale::classic()) {
const std::ctype& ct = std::use_facet<:ctype> >(L);
for (int i = CHAR_MIN; i <= CHAR_MAX; ++i)
tab[i - CHAR_MIN] = (char) i;
ct.toupper(tab, tab + (CHAR_MAX - CHAR_MIN + 1));
}
bool operator()(const std::string& x, const std::string& y) const {
return std::lexicographical_compare(x.begin(), x.end(),
y.begin(), y.end(),
lt_char(tab));
}
};
正如你看見的，lt_str_1 和 lt_str_2 不是非常不同。前者有一個直接使用ctype方面的字元比較函數物件，而後者使用一張預先算好的 大寫轉換表的字元比較函數物件。如果你建立lt_str_2函數物件，使用它比較一些短字串，然後放棄它，可能會比較慢。不過，對任何實際的使用來說， lt_str_2將明顯比lt_str_1快。在我的系統上差別不止兩倍：用lt_str_1排序一個23,791個單詞的list花費0.86秒，而用 lt_str_2花費0.4秒。
我們從所有這些裡學到了什麼？
- 忽略大小寫的字串類是錯誤的抽象層面。C++標準庫中的泛型算法是由策略參數化的，而你應該利用這個事實。
- 詞典字串比較建立在字元比較之上。一旦你有了一個忽略大小寫的字元比較函數對象，問題就解決了。（而且你可以把那個函數對象重用於比較其他類型的字元序列，比如vector
，或字串表，或原始的C字串。） - 忽略大小寫的字符比較比看起來難。除了在一個特定區域設置的場景之外，它沒有意義，所以字符比較函數物件需要儲存區域設置信息。如果關係到速度，你應該寫避免重複調用昂貴的方面操作的函數物件。
正確的忽略大小寫比較花費了大量手段，但是你只須把它寫一次。你或許不想考慮locale；大多數人不。（誰想在1990年考慮千禧年臭蟲？）如果你依賴區域設置的程式碼正確了，那麼你忽視區域設置的可能性將大於你寫出消除了這個依賴性的程式碼。
[1] 參見Andrei Alexandrescu在《C++ Report》2000年4月的專欄[19]。
[2] 警告：use_facet是一個函數模板，它的模板參數值出現在返回類型，而不是任何實參。使用一個叫做顯式模板參數特化的語言特性來呼叫它，而一些C++編譯器尚未支援那個特性。如果你使用了一個不支援的編譯器，你的函式庫實做可能提供了變通辦法，所以你可以用某種方式呼叫use_facet。
留言列表