《Effective STL》

haoji

Center of STL Study
——最优秀的STL学习网站
条款21: 永远让比较函数对相等的值返回false
让我向你展示一些比较酷的东西。建立一个set，比较类型用less_equal，然后插入一个10：
set<int, less_equal<int> > s; // s以“<=”排序
s.insert(10); // 插入10
现在尝试再插入一次10：
s.insert(10);
对于这个insert的调用，set必须先要判断出10是否已经位于其中了。 我们知道它是，但set可是木头木脑的，它
必须执行检查。为了便于弄明白发生了什么，我们将一开始已经在set中的10称为10A，而正试图插入的那个10
叫10B。
set遍历它的内部数据结构以查找哪儿适合插入10B。最终，它总要检查10B是否与10A相同。关联容器对“相
同”的定义是等价（参见条款19），因此set测试10B是否等价于10A。当执行这个测试时，它自然是使用set的
比较函数。在这一例子里，是operator<=，因为我们指定set的比较函数为less_equal，而less_equal意思就是
operator<=。于是，set将计算这个表达式是否为真：
!(10A <= 10B) && !(10B <= 10A) // 测试10A和10B是否等价
哦，10A和10B都是10，因此，10A <= 10B 肯定为真。同样清楚的是，10B <= 10A。于是上述的表达式简化为
!(true) && !(true)
再简化就是
false && false

haoji

结果当然是false。 也就是说，set得出的结论是10A与10B不等价，因此不一样，于是它将10B插入容器中10A的
旁边。在技术上而言，这个做法导致未定义的行为，但是通常的结果是set以拥有了两个为10的值的拷贝而告
终，也就是说它不再是一个set了。通过使用less_equal作为我们的比较类型，我们破坏了容器！此外，任何对
相等的值返回true的比较函数都会做同样的事情。是不是很酷？
OK，也许你对酷的定义和我不一样。就算这样，你仍然需要确保你用在关联容器上的比较函数总是对相等
的值返回false。但是，你需要保持警惕。对这条规则的违反容易达到令人吃惊的后果。
举个例子，条款20描述了该如何写一个比较函数以使得容纳string*指针的容器根据string的值排序，而不是对
指针的值排序。那个比较函数是按升序排序的，但我们现在假设你需要string*指针的容器的降序排序的比较
函数。自然是抓现成的代码来修改了。如果你不细心，可能会这么干，我已经加亮了对条款20中代码作了改
变的部分：
struct StringPtrGreater: // 高亮显示
public binary_function<const string*, // 这段代码和89页的改变
const string*, // 当心，这代码是有瑕疵的！
bool> {
bool operator()(const string *ps1, const string *ps2) const
{
return !(*ps1 < *ps2); // 只是相反了旧的测试；
} // 这是不对的！
};
这里的想法是通过将比较函数内部结果取反来达到反序的结果。很不幸，取反“<”不会给你（你所期望
的）“>”，它给你的是“>=”。而你现在知道，因为它将对相等的值返回true，对关联容器来说，它是一
个无效的比较函数。
你真正需要的比较类型是这个：
struct StringPtrGreater: // 对关联容器来说
public binary_function<const string*, // 这是有效的比较类型
const string*,
bool> {
bool operator()(const string *ps1, const string *ps2) const
{
return *ps2 < *ps1; // 返回*ps2是否

haoji

} // 大于*ps1（也就是
}; // 交换操作数的顺序）
要避免掉入这个陷阱，你所要记住的就是比较函数的返回值表明的是在此函数定义的排序方式下，一个值是
否大于另一个。相等的值绝不该一个大于另一个，所以比较函数总应该对相等的值返回false。
唉。
我知道你在想什么。你正在想，“当然，这对set和map很有意义，因为这些容器不能容纳复本。但是multiset
和multimap怎么样呢？那些容器可以容纳复本，那些容器可能包含副本，因此，如果容器认为两个值相等的
对象不等价，我需要注意些什么？它将会把两个都存储进去的，这正是multi系列容器的所要支持的事情。没
有问题，对吧？”
错。想知道为什么，让我们返回头去看最初的例子，但这次使用的是一个mulitset：
multiset<int, less_equal<int> > s; // s仍然以“<=”排序
s.insert(10); // 插入10A
s.insert(10); // 插入10B
现在，s里有两个10的拷贝，因此我们期望如果我们在它上面做一个equal_range，我们将会得到一对指出包含
这两个拷贝的范围的迭代器。但那是不可能的。equal_range，虽然叫这个名字，但不是指示出相等的值的范
围，而是等价的值的范围。在这个例子中，s的比较函数说10A和10B是不等价的，所以不可能让它们同时出现
在equal_range所指示的范围内。
你明白了吗？除非你的比较函数总是为相等的值返回false，你将会打破所有的标准关联型容器，不管它们是
否允许存储复本。
从技术上说，用于排序关联容器的比较函数必须在它们所比较的对象上定义一个“严格的弱序化(strict weak
ordering)”。（传给sort等算法（参见条款31）的比较函数也有同样的限制）。如果你对严格的弱序化含义的
细节感兴趣，可在很多全面的STL参考书中找到，比如Josuttis的《The C++ Standard Library》[3]（译注：中译
本《C++标准程序库》P176），Austern的《Generic Programming and the STL》[4]，和SGI STL的网站[21]。 我
从未发现这个细节如此重要，但一个对严格的弱序化的要求直接指向了这个条款。那个要求就是任何一个定
义了严格的弱序化的函数都必须在传入相同的值的两个拷贝时返回false。
嗨! 这就是这个条款！

haoji

Center of STL Study
——最优秀的STL学习网站
条款22：避免原地修改set和multiset的键
本条款的动机很容易理解。正如所有标准关联容器，set和multiset保持它们的元素有序，这些容器的正确行为
依赖于它们保持有序。 如果你改了关联容器里的一个元素的值（例如，把10变为1000），新值可能不在正确
的位置，而且那将破坏容器的有序性。很简单，是吗？
这对于map和multimap特别简单，因为试图改变这些容器里的一个键值的程序将不能编译：
map<int, string> m;
...
m.begin()->first = 10; // 错误！map键不能改变
multimap<int, string> mm;
...
mm.begin()->first = 20; // 错误！multimap键也不能改变
那是因为map<K, V>或multimap<K, V>类型的对象中元素的类型是pair<const K, V>。因为键的类型const K，
它不能改变。（嗯，如果你使用一个const_cast，正如我们将在下面看到的，你或许能改变它。不管相信与
否，有时那是你想要做的。）
但注意本条款的标题没有提及map或multimap。那有一个原因。正如上面例子演示的，原地修改键对map和
multimap来说是不可能的（除非你使用映射），但是它对set和multiset却是可能的。对于set<T>或multiset<T>
类型的对象来说，储存在容器里的元素类型只不过是T，并非const T。因此，set或multiset里的元素可能在你
想要的任何时候改变。不需要映射。（实际上，事情不完全那么简单，但我们不久将看到。没理由超过自
己。我们先得会爬，然后才能在碎玻璃上爬。）
让我们从明白为什么set或multiset里的元素不是常数开始。假设我们有一个雇员的类：
class Employee {
public:
...
const string& name() const; // 获取雇员名
void setName(const string& name); // 设置雇员名
const string& getTitle() const; // 获取雇员头衔

haoji

void setTitle(string& title); // 设置雇员头衔
int idNumber() const; // 获取雇员ID号
...
}
如你所见，我们可以得到雇员各种各样的信息。不过，让我们做合理的假设，每个雇员有唯一的ID号，就是
idNumber函数返回的数字。 然后，建立一个雇员的set，很显然应该只以ID号来排序set：
struct IDNumberLess{
public binary_function<Employee, Employee, bool> { // 参见条款40
bool operator()(const Employees lhs,
const Employee& rhs) const
{
return lhs.idNumber() < rhs.idNumber();
}
};
typedef set<Employee, IDNumberLess> EmpIDSet;
EmpIDSet se; // se是雇员的set，
// 按照ID号排序
实际上，雇员的ID号是set中元素的键。其余的雇员数据只是虚有其表。在这里，没有理由不能把一个特定雇
员的头衔改成某个有趣的东西。像这样：
Employee selectedID; // 容纳被选择的雇员
... // ID号的变量
EmpIDSet::iterator i = se.find(selectedID);
if (i != se.end()){
i->setTitle("Corporate Deity"); // 给雇员新头衔
}
因为在这里我们只是改变雇员的一个与set排序的方式无关的方面（一个雇员的非键部分），所以这段代码不
会破坏set。那是它合法的原因。但它的合法排除了set/multiset的元素是const的可能。而且那是它们为什么不
是的原因。
你可能想知道，为什么相同的逻辑不能应用于map和multimap的键？难道建立一个从雇员到，比如说，他们
居住的国家的map，map的比较函数是IDNumberLess，正如前一个例子，没有意义吗？而且如果给定了这样

haoji

一个map，难道没有理由在不影响雇员ID号的情况下改变一个雇员的职位，正如前一个例子?
坦率地说，我认为它可以。不过，由于同样的坦率，我怎么认为是不重要的。重要的是标准委员会怎么认
为，而它认为的是map/multimap键应该是const而set/multiset的值不是。
因为set或multiset里的值不是const，所以试图改变它们可以编译。本条款的目的是提醒你如果你改变set或
multiset里的元素， 你必须确保不改变一个键部分——影响容器有序性的元素部分。如果你做了，你会破坏容
器，再使用那个容器将产生未定义的结果， 而且那是你的错误。另一方面，这个限制只应用于被包含对象的
键部分。对被包含元素的所有其他部分来说，是开放的：随便改变！
除了碎玻璃以外。记得我早先提及的碎玻璃吗？我们现在在那里了。抓一些绷带跟我来。
即使set和multiset的元素不是const，实现仍然有很多方式可以阻止它们被修改。例如，实现可以让用于
set<T>::iterator的operator*返回一个常数T&。即，它可以让set的迭代器解引用的结果是set元素的常量引用。在
这样的实现下，将没有办法修改set或multiset的元素，因为所有访问那些元素的方法都将在让你访问之前加一
个const。
这样的实现合法吗？可以证明是。也可以证明不是。标准在这里有矛盾，而根据Murphy定律（译注：
Murphy定律就是“If there are two or more ways to do something, and one of those ways can result in a catastrophe,
then someone will do it.”（当有两条或更多的路让你抉择，如果其中一条会导致失败，那么你一定会选到
它。）随着时间流逝，这一“定律”逐渐进入习语范畴，其内涵被赋予无穷的创意，也出现了众多的变体，
其中最著名的一条也被称为Finagle定律，具体内容为：“If anything can go wrong, it will.”（如果一个东西可能
会出错，那它一定会出错。）这一定律被认为是对“Murphy定律”最好的模仿和阐述。），不同实现会以不
同的方式解释它们。结果是发现这些代码，我早先声明可以编译的，却经常在某些STL实现上不能编译：
EmpIDSet se; // 同前，se是一个以ID号
// 排序的雇员set
Employee selectedID; // 同前，selectedID是一个带有
// 被选择ID号的雇员
...
EmpIDSet::iterator i = se.find(selectedID);
if (i != se.end()){
i->setTitle("Corporate Deity"); // 有些STL实现会
} // 拒绝这行
因为标准的模棱两可和它已经造成的解释区别，试图修改set或multiset中的元素的代码不可移植。
所以我们站在哪边？值得鼓舞的是，事情并不复杂：

haoji

● 如果不关心移植性，你想要改变set或multiset中元素的值，而且你的STL实现让你侥幸成功，继续做。
只是要确定不要改变元素的键部分，即，会影响容器有序性的元素部分。
● 如果你在乎移植性，就认为set和multiset中的元素不能被修改，至少不能在没有映射的情况下。
啊，映射。我们已经看过有时候完全有理由改变set或multiset元素的非键部分，所以我觉得我得被迫向你演示
怎样做。也就是怎样做才能既正确又可移植。它不难，但是它用到了太多程序员忽略的一个细节：你必须映
射到一个引用。作为一个例子，再次看看我们刚看的不能在一些实现下编译的setTitle调用：
EmpIDSet::iterator i = se.find(selectedID);
if (i != se.end()) {
i->setTitle("Corporate Deity"); // 有些STL实现会
} // 拒绝这样，因为*i是const
为了让它可以编译并且行为正确，我们必须映射掉*i的常量性。这是那么做的正确方法：
if (i != se.end()) { // 映射掉
const_cast<Employee&>(*i).setTitle("Corporate Deity"); // *i的
} // 常量性
这可以得到i指向的对象，告诉你的编译器把映射的结果当作一个（非常数）Employee的引用，然后在那个引
用上调用setTitle。除了解释为什么这可以工作，我将解释为什么一种可替代的方法不表现人们经常期望的样
子。
很多人想到的是这段代码：
if (i != se.end()){ // 把*i
static_cast<Employee>(*i).setTitle("Corporate Deity"); // 映射到
} // 一个Employee
它也等价于如下内容：
if (i != se.end()) { // 同上，
((Employee)(*i)).setTitle("Corporate Deity"); // 但使用C
} // 映射语法

haoji

这两个都能编译，而且因为它们等价，所以它们错的原因也相同。在运行期，它们不能修改*i！在这两个情
况里，映射的结果是一个*i副本的临时匿名对象，而setTitle是在匿名的物体上调用，不在*i上！*i没被修改，
因为setTitle从未在那个对象上调用，它在那个对象的副本上调用。两个句法形式等价于这个：
if (i != se.end()){
Employee tempCopy(*i); // 把*i拷贝到tempCopy
tempCopy.setTitle("Corporate Deity"); // 修改tempCopy
}
现在应该清楚映射到引用的重要性了吧。通过映射到引用，我们避免了建立一个新对象。取而代之的是，映
射的结果是一个现有对象的引用，i指向的对象。当我们在有这个引用指定的对象上调用setTitle时，我们是在
*i上调用setTitle，而且那正是我们想要的。
我刚才写的适用于set和multiset，但当我们转向map和multimap时，细节变粗了。注意map<K, V>或
multimap<K, V>包含pair<const K, V>类型的元素。那个const表明pair的第一个组件被定义为常量，而那意味着
试图修改它是未定义的行为（即使映射掉它的常量性）。理论上，一个STL实现可能把这样的值写到一个只
读的内存位置（比如，一旦写了就通过系统调用进行写保护的虚拟内存页），而且试图映射掉它的常量性，
最多，没有效果。我从未听说一个实现那么做，但如果你是一个坚持遵循标准拟定的规则的人，你绝不会试
图映射掉map或multimap键的常量性。
你肯定听过映射是危险的，而且我希望本书能清楚到让我相信你可以尽量避免它们的程度。进行映射将临时
剥去类型系统的安全性， 而且当你把安全网抛至脑后时，我们已经讨论的缺陷例证了所能发生的。
大多数映射可以避免，那包括我们刚刚考虑的。如果你要总是可以工作而且总是安全地改变set、multiset、
map或multimap里的元素，按五个简单的步骤去做：
1. 定位你想要改变的容器元素。如果你不确定最好的方法，条款45提供了关于怎样进行适当搜寻的指
导。
2. 拷贝一份要被修改的元素。对map或multimap而言，确定不要把副本的第一个元素声明为const。毕
竟，你想要改变它！
3. 修改副本，使它有你想要在容器里的值。
4. 从容器里删除元素，通常通过调用erase（参见条款9）。
5. 把新值插入容器。如果新元素在容器的排序顺序中的位置正好相同或相邻于删除的元素，使用insert
的“提示”形式把插入的效率从对数时间改进到分摊的常数时间。使用你从第一步获得的迭代器作为
提示。
这是同一个累人的雇员例子，这次以安全、可移植的方式写：

haoji

EmpIDSet se; // 同前，se是一个以ID号
// 排序的雇员set
Employee selectedID; // 同前，selectedID是一个带有
// 需要ID号的雇员
...
EmpIDSet::iterator i =
se.find(selectedID); // 第一步：找到要改变的元素
if (i!=se.end()){
Employee e(*i); // 第二步：拷贝这个元素
se.erase(i++); // 第三步：删除这个元素；
// 自增这个迭代器以
// 保持它有效（参见条款9）
e.setTitle("Corporate Deity"); // 第四步：修改这个副本
se.insert(i, e); // 第五步：插入新值；提示它的位置
// 和原先元素的一样
}
你将原谅我以这种方法放它，但要记得关键的事情是对于set和multiset，如果你进行任何容器元素的原地修
改，你有责任确保容器保持有序。

haoji

Center of STL Study
——最优秀的STL学习网站
条款23：考虑用有序vector代替关联容器
当需要一个提供快速查找的数据结构时，很多STL程序员立刻会想到标准关联容器：set、multiset、map和
multimap。直到现在这很好，但不是永远都好。如果查找速度真得很重要，的确也值得考虑使用非标准的散
列容器（参见条款25）。如果使用了合适的散列函数，则可以认为散列容器提供了常数时间的查找。（如果
选择了不好的散列函数或表的太小，散列表的查找性能可能明显下降，但在实际中这相对少见。）对于多数
应用，被认为是常数时间查找的散列容器要好于保证了对数时间查找的set、map和它们的multi同事。
即使你需要的就只是对数时间查找的保证，标准关联容器仍然可能不是你的最佳选择。和直觉相反，对于标
准关联容器，所提供的性能也经常劣于本该比较次的vector。如果你要有效使用STL，你需要明白什么时候和
怎么让一个vector可以提供比标准关联容器更快的查找。
标准关联容器的典型实现是平衡二叉查找树。一个平衡二叉查找树是一个对插入、删除和查找的混合操作优
化的数据结构。换句话说，它被设计为应用于进行一些插入，然后一些查找，然后可能再进行一些插入，然
后也许一些删除，然后再来一些查找，然后更多的插入或删除，然后更多的查找等。这个事件序列的关键特
征是插入、删除和查找都是混合在一起的。一般来说，没有办法预测对树的下一个操作是什么。
在很多应用中，使用数据结构并没有那么混乱。它们对数据结构的使用可以总结为这样的三个截然不同的阶
段：
1. 建立。通过插入很多元素建立一个新的数据结构。在这个阶段，几乎所有的操作都是插入和删除。几
乎没有或根本没有查找。
2. 查找。在数据结构中查找指定的信息片。在这个阶段，几乎所有的操作都是查找。几乎没有或根本没
有插入和删除。
3. 重组。修改数据结构的内容，也许通过删除所有现有数据和在原地插入新数据。从动作上说，这个阶
段等价于阶段1。一旦这个阶段完成，应用程序返回阶段2。
对于这么使用它们的数据结构的应用来说，一个vector可能比一个关联容器能提供更高的性能（时间和空间
上都是）。但不是任意的vector都会，只有有序vector。因为只有有序容器才能正确地使用查找算法——
binary_search、lower_bound、equal_range等（参见条款34）。但为什么一个（有序的）vector的二分法查找比
一个二叉树的二分法查找提供了更好的性能？因为有些东西是过时的但却是真的，其中的一个是大小问题。
其他东西不那么过时也不那么真，其中的一个是引用局部性问题。
考虑第一个大小问题。假设我们需要一个容器来容纳Widget对象，而且，因为查找速度对我们很重要，我们