《Effective STL》

haoji

然后程序停止了，因为如果STLport的调试模式遇到用法错误就会调用abort。如果你喜欢改为抛出一个异常，
你可以把STLport配置成你的方式。
无可否认，上述错误信息没有它可能的清楚，而且不幸的是，报告的文件和行对应于内部STL断言的位置而
不是调用transform的行， 但这也仍然比越过transform调用的运行，然后试图指出你的数据结构为什么是错误
的要好。通过STLport的调试模式，你需要做的所有事情就是发动你的调试器，把调用堆栈返回到你写的代
码，然后确定你做错了什么。发现厌恶的源代码行一般不是问题。
STLport的调试模式检测多种常见错误，包括把无效的区间传给算法，试图从一个空的容器里读取，使用来自
一只容器的迭代器作为第二个迭代器成员函数的实参，等等。它通过迭代器和它们的容器间彼此跟踪来完成
这个魔术。给定两个迭代器，这样就使检查它们是否来自同一个容器成为可能，而且当一个容器被修改时，
这使适当的迭代器集失效成为可能。
因为STLport在调试模式使用特殊的迭代器实现，vector和string的迭代器就是类对象而不是原始指针。因此，
使用STLport并在调试模式编译是确认没有人草率地处理指针和这些容器类型的迭代器之间区别的一种好方
法。单单这点就足够成为给STLport调试方式一个机会的理由。
Boost网站
在1997年，当关闭通向C++国际标准的道路的钟声响起时，一些人对他们提倡的库特性没有入选而感到失
望。这些人中的一部分本身就是委员会的成员，所以他们开始在第二轮标准化期间为标准库的扩充打下基
础。结果就是Boost，一个任务是“提供免费、同行评议的C++库。重点在于可以和C++标准库配合良好的可
移植库”的网站。在任务后面是一个动机：
一个库变成“现有实践”的程度，某人把它提交给未来标准的可能性就增加了。提交一个库
给Boost.org是建立现有实践的一种方法
换句话说，当一个库可能增加到标准C++库时，Boost把自己作为帮助区分好坏的鉴别机制。这是一个可敬的
服务，而且我们全都应该感激。
让人感激的另一个原因是你可以在Boost中找到的库集合。我并不想在这里全部解释它们，尤其是因为当你读
这些话时，无疑已经增加了许多新的库。不过，对于STL用户，两个库特别有用。第一个是智能指针库，包
含用于引用计数智能指针的模板shared_ptr，与标准库的auto_ptr不同，它可以安全的储存在STL容器里（参见
条款8）。Boost的智能指针库也提供shared_array，一个用于动态分配数组的引用计数智能指针，但条款13论
述了动态分配数组不如vector和string，而且我希望你发现它的论点有说服力。
Boost第二个吸引STL迷的是它有关STL的函数对象和相关工具的群。这些库包含的基本原则是重新设计和重
新实现STL函数对象和适配器后面的思想，这个结果消除了很多对标准仿函数功效的人为约束。作为这样的

haoji

一个约束的例子，你将发现如果你试图把bind2nd和mem_fun或mem_fun_ref一起用（参见条款41）来把一个对
象绑定到一个成员函数的参数，而且那个成员函数通过引用获取它的参数，你的代码不可能编译。如果你试
图把not1或not2和ptr_fun一起用而且一个函数声明了通过引用的参数，你将发现一样的结果。在两中情况里
的原因是在模板实例化的过程中，大多数STL平台产生到引用的引用，而到引用的引用在C++里不合法。
（标准委员会正在酝酿标准里的一个改变来解决这个问题。）这里有一个被认为是“到引用的引用的问
题”的例子：
class Widget {
public:
...
int readStream(istream& stream); // readStream用
... // 引用获取参数
};
vector<Widget*> vw;
...
for_each( // 大多数STL平台
vw.begin(), vw.end(), // 试图在这个调用中
bind2nd(mem_fun(&Widget::readStream), cin) // 产生一个
// 到引用的引用；
// 那样的代码
// 不能编译
Boost的函数对象避免了这个和其它问题，此外它们相当地扩大了函数对象的表现力。
如果你对STL函数对象的潜力感兴趣而且你想要更进一步探索它，赶快马上转到Boost。如果你痛恨函数对象
而且认为它们的存在只是为了安慰少数转为C++程序员的Lisp拥护者，那也赶快转向Boost。Boost的函数对象
库很重要，但它们只是你能在那个网站发现的一小部分而已。

haoji

[7] Bjarne Stroustrup，《The C++ Programming Language》（第三版），Addison-Wesley，1997，ISBN 0-201-
88954-4。我在条款12提到的“资源获取即初始化”惯用法在这本书的第14.4.1节讨论，我在条款36引用
的代码在第530页。
[8] Herb Sutter，《Exceptional C++ : 47 Engineering Puzzles, progromming Problems, and Solutions》，Addison-
Wesley，2000，ISBN 0-201-61562-2。对我Effective系列的一个值得推崇的补充，即使当时Herb没有让我
为它写序，我也会赞美它。
[9] Herb Sutter，《More Exceptional C++: 40 More Engineering Puzzles, Programming Problems, and
Solutions》，Addison-Wesley，预计在2001年出版，暂定ISBN 0-201-70434-X。基于我看过的草稿，他看
起来完全和它的前辈[8]一样好。
[10] Dov Bulka和David Mayhew，《Efficient C++: Performance Programming Techniques》，Addison-Wesley，
2000，ISBN 0-201-37950-3。唯一一本专注于C++效率的书，因此也是最好的。
[11] Matt Austern，“How to Do Case-Insensitive String Comparison”，《C++ Report》，2000年5月。这篇文
章很重要，他被复制为本书的附录A。
[12] Herb Sutter，“When Is a Container Not a Container?”，《C++ Report》，1999年5月。可以在http://www.
gotw.ca/publications/mill09.htm找到。修订和更新为《More Exceptional C++》[9]的条款6。
[13] Herb Sutter，“Standard Library News: sets and maps”，《C++ Report》，1999年10月。可以在http://
www.gotw.ca/publications/mill11.htm找到。修订和更新为《More Exceptional C++》[9]的条款8。
[14] Nicolai M. Josuttis，“Predicates vs. Function Objects”，《C++ Report》，2000年6月。
[15] Matt Austern，“Why You Shouldn't Use set -- and What to Use Instead”，《C++ Report》，2000年4月。
[16] P. J. Plauger，“Hash Tables”，《C/C++ Users Journal》，1998年11月。描述了Dinkumware散列容器的
方法（在条款25讨论）以及它与其他竞争者的设计区别。
[17] Jack Reeves，“STL Gotcha's”，《C++ Report》, 1997年1月。可以在http://www.bleading-edge.com/
Publications/C++Report/v9701/abstract.htm找到。
[18] Jack Reeves，“Using Standard string in the Real World, Part 2”，《C++ Report》，1999年1月。可以在
http://www.bleading-edge.com/Publications/C++Report/v9901/abstract.htm找到。
[19] Andrei Alexandreseu，“Traits: The else-if-then of Types”，《C++ Report》，2000年4月。可以在http://
www.creport.com/html/from-pages/view-recent_articles_c.cfm?ArticleID=402找到。
[20] Herb Sutter，“Optimizations That Aren't (In a Multithreaded World)”，《C/C++ Users Journal》，1999年
6月。可以在http://www.gotw.ca/publications/optimizations.htm找到。修订和更新为《More Exceptional C+
+》[9]的条款16。
[21] SGI STL网站，http://www.sgi.com/tech/stl/。条款50总结了这个重要网站的材料。关于STL容器线程安全
（它是条款12的动机）的页在http://www.sgi.com/tech/stl/thread_safety.html。
[22] Boost网站，http://www.boost.org/。条款50总结了这个重要网站的材料。

haoji

区域设置和忽略大小写的字符串比较
条款35解释了怎样使用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<char, std::char_traits<char>, std::allocator<char> >的别名。所有的比较都
使用了特性参数，所以，通过提供一个正确地重定义了相等和小于的特性参数的方法，你可以实例化
basic_string，使<和==操作符是忽略大小写的。你可以这么做，但没必要那么麻烦。
● 你将不能做I/O，至少不能再没有很多痛苦的情况下进行。标准库里的I/O类，比如std::basic_istream和
std::basic_ostream，与std::basic_string一样在字符类型和特性上模板化。（再次强调，std:stream只是一
个std::basic_ostream<char, char_traits<char> >的别名。）特性参数必须匹配。如果你对字符串使用std::
basic_string<char, my_traits_class>，你就必须对流使用std::basic_ostream<char, my_traits_class>。你不能
使用比如cin和cout那样普通的流对象。
● 忽略大小写不涉及一个对象，而涉及你怎样使用一个对象。你可能在一些情况下非常需要把一个
string当作关注大小写而在其他情况下忽略大小写。（或许取决于用户控制的选项。）为这两种应用
定义不同的类型是在它们之间放置人造障碍。
● 它并不合适。正如所有的特性类[1]，char_traits是小的、简单的和无状态的。我们可以在本专栏的后面
看到，正确的忽略大小写比较不是这样的东西。
● 它不够。即使所有basic_string本身的成员函数都忽略大小写，当你需要使用非成员泛型算法比如std::
search和std::find_end时，将仍然没有帮助。如果你决定，出于效率的考虑，从basic_string对象的容器
改为字符串表，它也将没有帮助。
更自然地融合入标准库设计的更好的解决方案是在当你需要时才进行忽略大小写的比较。不要为string::

haoji

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<char, char, bool> {
bool operator()(char x, char y) const {
return std::toupper(static_cast<unsigned char>(x)) <
std::toupper(static_cast<unsigned char>(y));
}
};

haoji

“任何复杂问题都有一个简单、整洁而且错误的解决方案。”写关于C++的书的人都喜欢这个类，因为它是
一个好的、简单的例子。 我像其他人一样心虚；我在我的书中多次使用了它。它几乎是正确的，但是不够
好。问题是微妙的。
这里有一个你可以开始发现问题的例子：
int main()
{
const char* s1 = "GEW\334RZTRAMINER";
const char* s2 = "gew\374rztraminer";
printf("s1 = %s, s2 = %s\n", s1, s2);
printf("sl < s2: %s\n",
std::lexicographical_compare(s1, s1 + 14, s2, s2 + 14, lt_nocase())
? "true" :"false");
}
你应该在你的系统上试试看。在我的系统上（一台运行IRIX 6.5的Silicon Graphics O2），这是输出：
s1 = GEWRZTRAMINER, s2 = gewürztraminer
s1< s2: true
噢，多古怪。如果你做忽略大小写比较，难道“gewürztraminer”和“GEWRZTRAMINER”不同吗？现在
做一个轻微的变化：如果你在printf语句之前插入这行
setlocale(LC_ALL, "de");
，突然输出改变了：
s1 = GEWRZTRAMINER, s2 = gewürztraminer
s1 < s2: false
忽略大小写的字符串比较比看起来更复杂。这表面上正确的程序非常依赖于大多数人经常忽略的东西：区域
设置。
区域设置

haoji

一个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();

haoji

或者你通过这么写建立一个德语区域设置
std::locale L("de");
（和C库里的一样，区域的名字没有标准化。检查你的实现文档来查明提供了哪些有名字的区域设置。）
C++里的区域设置分成多个方面（facet），每个方面处理一个国际化的不同方向，而函数std::use_facet从区域
设置对象[2]中提取一个特定的方面。ctype方面处理字符分类，包括大小写转换。最后，如果c1和c2是char类
型，这段代码将以适合区域设置L并以忽略大小写的方式比较它们。
const std::ctype<char>& ct = std::use_facet<std::ctype<char> >(L);
bool result = ct.toupper(c1) < ct.toupper(c2);
也有一个特别的缩写词：你可以写
std::toupper(c, L)
意思和
std::use_facet<std::ctype<char> >(L).toupper(c)
相同（如果c是char类型）。不过，最小化调用use_facet的次数是值得的，因为它可能相当昂贵。
正如词典比较不能适合于所有应用一样，一个一个字符的大小写转换也不总是适合的。（例如，在德语里，
小写字母“”对应着大写序列“SS”。）但是，不幸的是，一个一个字符的大小写转换是我们拥有的全
部。C和C++标准库都没有提供任何一次用于不止一个字符的字符串转换形式。如果你的目的不能接受这个
限制，那么就已经在标准库的范围之外了。
离题一下：另一个方面
如果你已经熟悉C++里的区域设置，你可能想果用另一种方式进行字符串比较：collate方面的存在正好封装
了排序的细节，而它有一个接口很像C库函数strcmp的成员函数。甚至有一个方便的特征：如果L是一个区域
设置对象，你可以通过写L(x，y)而不是通过讨厌地调用use_facet然后调用collate成员函数来比较两个字符串。

haoji

“classic”区域设置有一个进行词典排序的collate方面，和字符串的operator<做的一样，但其他区域设置进行
任何种比较都是合适的。如果你的系统正好有一个对任何你感兴趣的语言进行忽略大小写比较的区域设置，
你可以使用它。那个区域设置甚至可能做出比一个一个字符比较更智能化的事情！
不幸的是，这个建议，可能是真的，并不能帮助像我们这些没有那样的系统的人。或许有一天一套这样的区
域设置可以标准化，但现在它们还没有。如果没有人为你写了一种忽略大小写的比较，你就必须亲自写它。
忽略大小写字符串比较
使用ctype，用忽略大小写字符比较构造忽略大小写字符串比较是很简单的。这个版本不是最优的，但至少它
是正确的。它基本上使用和以前相同的技术：使用lexicographical_compare比较两个字符串，而且通过把两个
字符都转换成大写来比较它们。不过，这次我们小心地使用区域设置对象而不是全局变量。（另外说一下，
把两个字符都转化成大写不一定总是等于把两个字符都变成小写的结果：没有保证操作是可逆的。例如，在
法语里，通常忽略大写字符上的重音标记。在法语区域设置中，toupper有理由是有损转换；它可以
把“é”和“e”都转换成同样的大写字符，“E”。那么，在这样的区域设置里，使用toupper的忽略大小写
比较将说“é”和“E”是等价字符，而tolower将说它们不是。哪个是正确的答案？或许是前者，但它取决
于语言，取决于当地习惯，取决于你的应用程序。）
struct lt_str_1
: public std::binary_function<std::string, std::string, bool> {
struct lt_char {
const std::ctype<char>& ct;
lt_char(const std::ctype<char>& c) : ct(c) {}
bool operator()(char x, char y) const {
return ct.toupper(x) < ct.toupper(y);
}
};
std::locale loc;
const std::ctype<char>& ct;
lt_str_1(const std::locale& L = std::locale::classic())
: loc(L), ct(std::use facet<std::ctype<char> >(loc)) {}
bool operator()(const std::string& x, const std::string& y) const{
return std::lexicographical_compare(x.begin(), x.end(),

haoji

y.begin(), y.end(),
lt_char(ct));
}
};
这还不很好；它比应该的慢。问题是讨厌的和技术性的：我们在循环内调用toupper，而C++标准要求toupper
是虚函数调用。一些优化器可能聪明得足以把虚函数开销移到循环之外，但是大多数不是。循环内的虚函数
调用应该避免。
在这里，避免它不是很简单。你可能想到正确答案是ctype的另一个成员函数，
const char* ctype<char>::toupper(char* f, char* l) const
这改变了区间[f, l)内的字符大小写。不幸的是，这不完全是我们的目标的正确接口。使用它来比较两个字符
串要求把两个字符串都拷贝到缓冲区，然后把缓冲区转化成大写。那些缓冲区从哪里来？它们不能是固定大
小的数组（多大才足够大？），但动态数组需要昂贵的内存分配。
另一个解决方案是每次对一个字符进行大小写转换并缓存结果。这不是一个完全通用的解决方案——例如，
如果你用的是32位UCS 4字符，它将完全不能工作。不过，如果你用char（大部分系统上是8位），在比较函
数对象里维护一个256字节的大小写转换信息不是没有道理的。
struct lt_str_2:
public std::binary_function<std::string, std::string, bool> {
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<char>& ct = std::use_facet<std::ctype<char> >(L);