《Effective STL》

haoji

Center of STL Study
——最优秀的STL学习网站
条款35：通过mismatch或lexicographical比较实现简单的忽略大小写字
符串比较
一个STL菜鸟最常问的问题是“我怎么使用STL来进行忽略大小写的字符串比较？”这是一个令人迷惑的简单
问题。忽略大小写字符串比较要么真的简单要么真的困难，依赖于你要多一般地解决这个问题。如果你忽略
国际化问题而且只关注于设计成字符串strcmp那样的类型，这个任务很简单。如果你要有strcmp不具有的按
语言处理字符串中的字符的能力（也就是，容纳文本的字符串是除了英语以外的语言）或程序使用了区域设
置而不是默认的，这个任务很困难。
在本条款中，我会作出这个问题的一个简单版本，因为那足以演示STL怎么完成任务。（这个问题一个比较
难的版本也能用STL解决。准确地说，它解决了你可以在附录A中看到的有关区域设置的问题。）为了让简单
的问题变得更有挑战性，我会处理两次。想要使用忽略大小写比较的程序员通常需要两种不同的调用接口，
一种类似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<unsigned char>(c1));// 这些语句的解释
int Ic2 = tolower(static_cast<unsigned char>(c2));// 看下文
if (Ic1 < Ic2) return -1;
if (lc1 > Ic2) return 1;
return 0;
}
这个函数遵循了strcmp，可以返回一个负数、零或正数，依赖于c1和c2之间的关系。与strcmp不同的是，
ciCharCompare在进行比较前把两个参数转化为小写。这就产生了忽略大小写的字符比较。

haoji

正如<cctype>（也是<ctype.h>）里的很多函数，tolower的参数和返回值类型是int，但除非这个int是EOF，它
的值必须能表现为一个unsigned char。在C和C++中，char可能或可能不是有符号的（依赖于实现），当char
有符号时，唯一确认它的值可以表现为unsigned char的方式是在调用tolower之前转换一下。这就解释了上面
代码中的转换。（在char已经是无符号的实现中，这个转换没有作用。）这也解释了保存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<string::const_iterator, // PSCI = “pair of
string::const_iterator> PSCI; // string::const_iterator”
PSCI p = mismatch( // 下文解释了
s1.begin(), s1.end(), // 为什么我们
s2.begin(), // 需要not2；参见
not2(ptr_fun(ciCharCompare))); // 条款41解释了为什么
// 我们需要ptr_fun
if (p.first== s1.end()) { // 如果为真，s1等于
if (p.second == s2.end()) return 0; // s2或s1比s2短
else return -1;

haoji

}
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<unsigned char>(c1)) < // 条款46解释了为什么
tolower(static_cast<unsigned char>(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对所有任

haoji

何类型的值的区间都起作用。同时，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*指针（参
见条款16），然后对指针使用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的方法是认识到其他方法更好。

haoji

Center of STL Study
——最优秀的STL学习网站
条款36：了解copy_if的正确实现
STL有很多有趣的地方，其中一个是虽然有11个名字带“copy”的算法：
copy copy_backward
replace_copy reverse_copy
replace_copy_if unique_copy
remove_copy rotate_copy
remove_copy_if partial_sort_copy
unintialized_copy
但没有一个是copy_if。这意味着你可以replace_copy_if，你可以remove_copy_if，你可以copy_backward或者
reverse_copy，但如果你只是简单地想要拷贝一个区间中满足某个判断式的元素，你只能自己做。
比如，假设你有一个函数来决定一个Widget是否有缺陷的：
bool isDefective(const Widget& w);
而且你希望把一个vector中所有有缺陷的Widget写到cerr。如果存在copy_if，你可以简单地这么做：
vector<Widget> widgets;
...
copy_if(widgets.begin(), widgets.end(), // 这无法编译：
ostream_iterator<Widget>(cerr, "\n"), // STL中并没有copy_if
isDefective);
具有讽刺意味的事，copy_if是最初的惠普STL的一部分，惠普STL形成了STL的基础，而STL现在是标准C++库
的一部分。有些怪癖会使历史变得有趣，在从HP STL中为标准筛选出一些大小易于管理的东西时，copy_if成
了其中一个在剪接室中被遗弃的东西。
在《The C++ Programming Language》[7]，Stroustrup强调写copy_if是微不足道的，他是对的，但那不意味着

haoji

实现正确的琐事很简单。比如，这里有一个合理的看待copy_if，很多人（包括我）曾经知道的实现：
template<typename InputIterator, // 一个不很正确的
typename OutputIterator, // copy_if实现
typename Predicate>
OutputIterator copy_if(InputIterator begin,
InputIterator end,
OutputIterator destBegin, Predicate p)
{
return remove_copy_if(begin, end, destBegin, not1(p));
}
这个方法是基于这个观点——虽然STL并没有让你说“拷贝每个判断式为true的东西”，但它的确让你说
了“拷贝除了判断式不为true以外的每个东西”。要实现copy_if，似乎我们需要做的就只是加一个not1在我们
希望传给copy_if的判断式前面，然后把这个结果判断式传给remove_copy_if，结果就是上面的代码。
如果上面的理由有效，我们就可以用这种方法写出有缺陷的Widget：
copy_if(widgets.begin(), widgets.end(), // well-intentioned code
ostream_iterator<Widget>(cerr, "\n"), // that will not compile
isDefective);
你的STL平台将会敌视这段代码，因为它试图对isDefective应用not1（这个应用出现在copy_if内部）。正如条
款41试图将清楚的，not1不能直接应用于一个函数指针，函数指针必须先传给ptr_fun。要调用这个copy_if实
现，你必须传递的不仅是一个函数对象，而且是一个可适配的函数对象。这够简单了，但是想要成为STL算
法用户的人应该不必这样。标准STL算法从来不要求它们的仿函数是可适配的，copy_if也不应该要求。上面
的实现是好的，但不够好。
这是copy_if正确的微不足道的实现：
template<typename InputIterator, // 一个copy_if的
typename OutputIterator, // 正确实现
typename Predicate>
OutputIterator copy_if(InputIterator begin,
InputIterator end,
OutputIterator destBegin,
Predicate p) {

haoji

while (begin != end) {
if (p(*begin))*destBegin++ = *begin;
++begin;
}
return destBegin;
}
告诉你copy_if多有用，加上新STL程序员趋向于希望无论如何它应该存在的事实，所以好的做法是把copy_if
——正确的那个！——放在你局部的STL相关工具库中，而且只要合适就使用。

haoji

Center of STL Study
——最优秀的STL学习网站
条款37：用accumulate或for_each来统计区间
有时候你需要把整个区间提炼成一个单独的数，或，更一般地，一个单独的对象。对于一般需要的信息，有
特殊目的的算法来完成这个任务，比如，count告诉你区间中有多少等于某个值的元素，而count_if告诉你有
多少元素满足一个判断式。区间中的最小和最大值可以通过min_element和max_element获得。
但有时，你需要用一些自定义的方式统计（summarize）区间，而且在那些情况中，你需要比count、
count_if、min_element或max_element更灵活的东西。比如，你可能想要对一个容器中的字符串长度求和。你
可能想要数的区间的乘积。你可能想要point区间的平均坐标。在那些情况中，你需要统计一个区间，但你需
要有定义你需要统计的东西的能力。没问题。STL为你准备了那样的算法，它叫作accumulate。你可能不熟悉
accumulate，因为，不像大部分算法，它不存在于<algorithm>。取而代之的是，它和其他三个“数值算
法”都在<numeric>中。（那三个其它的算法是inner_product、adjacent_difference和partial_sum。）
就像很多算法，accumulate存在两种形式。带有一对迭代器和初始值的形式可以返回初始值加由迭代器划分
出的区间中值的和：
list<double> ld; // 建立一个list，放
... // 一些double进去
double sum = accumulate(ld.begin(), Id.end(), 0.0); // 计算它们的和，
// 从0.0开始
在本例中，注意初始值指定为0.0，不是简单的0。这很重要。0.0的类型是double，所以accumulate内部使用了
一个double类型的变量来存储计算的和。如果这么写这个调用：
double sum = accumulate(ld.begin(), Id.end(), 0); // 计算它们的和，
// 从0开始；
// 这不正确！
如果初始值是int 0，所以accumulate内部就会使用一个int来保存它计算的值。那个int最后变成accumulate的返
回值，而且它用来初始化和变量。这代码可以编译和运行，但和的值可能不对。不是保存真的double的list的
和，它可能保存了所有的double加起来的结果，但每次加法后把结果转换为一个int。
accumulate只需要输入迭代器，所以你甚至可以使用istream_iterator和istreambuf_iterator（参见条款29）：

haoji

cout << "The sum of the ints on the standard input is" // 打印cin中
<< accumulate(istream_iterator<int>(cin), // 那些int的和
istream_iterator<int>(),
0);
进行数值算法是accumulate的默认行为。但当使用accumulate的另一种形式，带有一个初始和值与一个任意的
统计函数，这变得一般很多。
比如，考虑怎么使用accumulate来计算容器中的字符串的长度和。要计算这个和，accumulate需要知道两个东
西。第一，同上，它必须知道和的开始。在我们的例子中，它是0。第二，它必须知道每次看到一个新的字
符串时怎么更新这个和。要完成这个任务，我们写一个函数，它带有目前的和与新的字符串，而且返回更新
的和：
string::size_type // string::size_type的内容
stringLengthSum(string::size_type sumSoFar, // 请看下文
const string& s)
{
return sumSoFar + s.size();
}
这个函数的函数体非常简单，但你可能发现自己陷于string::size_type的出现。不要那样。每个标准STL容器都
有一个typedef叫做size_type，那是容器计量东西的类型。比如，这是容器的size函数的返回类型。对于所有的
标准容器，size_type必须是size_t，但理论上非标准STL兼容的容器可能让size_type使用一个不同的类型（虽然
我花了很多时间来想为什么它们要那么做）。对于标准容器，你可以把Container::size_type看作size_t写法的一
个奇异方式。
stringLengthSum是accmulate使用的统计函数的代表。它带有到目前为止区间的统计值和区间的下一个元素，
它返回新的统计值。一般来说，那意味着函数会带不同类型的参数。那就是这里所做的。到目前为止的统计
值（已经看到的字符串的长度和）是string::size_type类型，而要检查的元素的类型是string。典型地在这个例
子中，这里的返回类型和函数的第一个参数相同，因为它是更新了的统计值（加上了最后计算的元素）。
我们可以让accumulate这么使用stringLengthSum：
set<string> ss; // 建立字符串的容器，
... // 进行一些操作
string::size_type lengthSum = // 把lengthSum设为对

haoji

accumulate(ss.begin(), ss.end(), // ss中的每个元素调用
0, stringLengthSum); // stringLengthSum的结果，使用0
// 作为初始统计值
很好，不是吗？计算数值区间的积甚至更简单，因为我们不用写自己的求和函数。我们可以使用标准
multiplies仿函数类：
vector<float> vf; // 建立float的容器
... // 进行一些操作
float product = // 把product设为对vf
accumulate(vf.begin(), vf.end(), // 中的每个元素调用
1.0f, multiplies<float>()); // multiplies<float>的结果，用1.0f
// 作为初始统计值
这里唯一需要小心的东西是记得把1（作为float，不是int！）作为初始统计值，而不是0。如果我们使用0作为
开始值，结果会总是0，因为0乘以任何东西也是0，不是吗？
我们的最后一个例子有一些晦涩。它完成寻找point的区间的平均值，point看起来像这样：
struct Point {
Point(double initX, double initY): x(initX), y(initY) {}
double x, y;
};
求和函数应该是一个叫做PointAverage的仿函数类的对象，但在我们察看PointAverage之前，让我们看看它在
调用accumulate中的使用方法：
list<Point> lp;
...
Point avg = // 对Ip中的point求平均值
accumulate(lp.begin(), lp.end(),
Point(0, 0), PointAverage());
简单而直接，我们最喜欢的方式。在这个例子中，初始和值是在原点的point对象，我们需要记得的是当计算
区间的平均值时不要考虑那个点。