《Effective STL》

haoji

Center of STL Study
——最优秀的STL学习网站
关联容器
有点像在电影《Oz国历险记（The Wizard of Oz）》（译注：国内又译为《绿野仙踪》。全世界最有名的童话
片之一，荣获1939年奥斯卡最佳电影歌曲和最佳电影配乐。）中的多色马，关联容器是不同颜色的生物。真
的，它们共享了序列容器的很多特性，但它们在很多基本方法上不同。比如，它们自动保持自己有序；它们
通过等价而不是相等来查看它们的内容；set和map拒绝重复实体；map和multimap一般忽略它们包含的每个对
象的一半。是的，关联容器也是容器，但如果你原谅我把vector和string比作Kansas，我们干脆不再在Kansas
了。
在下面的条款里，我解释了等价的临界概念，描述了比较函数的一个重要约束，介绍了用于指针关联容器的
自定义比较函数，从官方和实践方面讨论了键的常量性，在改进关联容器的效率上提供了建议。
在本章的结尾，我考察了STL缺乏的基于散列表的容器，我也审视了两个常见（非标准）的实现。虽然STL的
确没有提供散列表，但你不必自己写或放弃它。高质量的实现很容易得到。

haoji

Center of STL Study
——最优秀的STL学习网站
条款19：了解相等和等价的区别
STL充满了比较对象是否有同样的值。比如，当你用find来定位区间中第一个有特定值的对象的位置，find必
须可以比较两个对象，看看一个的值是否与另一个相等。同样，当你尝试向set中插入一个新元素时，set::
insert必须可以判断那个元素的值是否已经在set中了。
find算法和set的insert成员函数是很多必须判断两个值是否相同的函数的代表。但它们以不同的方式完成，find
对“相同”的定义是相等，基于operator==。set::insert对“相同”的定义是等价，通常基于operator<。因为有
定义不同，所以有可能一个定义规定了两个对象有相同的值而另一个定义判定它们没有。结果，如果你想有
效使用STL，那么你必须明白相等和等价的区别。
操作上来说，相等的概念是基于operator==的。如果表达式“x == y”返回true，x和y有相等的值，否则它们
没有。这很直截了当，但要牢牢记住，因为x和y有相等的值并不意味着所有它们的成员有相等的值。比如，
我们可能有一个内部记录了最后一次访问的Widget类。
class Widget {
public:
...
private:
TimeStamp lastAccessed;
...
};
我们可以有一个用于Widget的忽略这个域的operator==：
bool operator==(const Widget& lhs, const Widget& rhs) {
// 忽略lastAccessed域的代码
}
在这里，两个Widget即使它们的lastAccessed域不同也可以有相等的值。
等价是基于在一个有序区间中对象值的相对位置。等价一般在每种标准关联容器（比如，set、multiset、map

haoji

和multimap）的一部分——排序顺序方面有意义。两个对象x和y如果在关联容器c的排序顺序中没有哪个排在
另一个之前，那么它们关于c使用的排序顺序有等价的值。这听起来很复杂，但实际上，它不。考虑一下，
举一个例子，一个set<Widget> s。两个Widget w1和w2，如果在s的排序顺序中没有哪个在另一个之前，那么关
于s它们有等价的值。set<Widget>的默认比较函数是less<Widget>，而默认的less<Widget>简单地对Widget调用
operator<，所以w1和w2关于operator<有等价的值如果下面表达式为真：
!(w1 < w2) // w1 < w2时它非真
&& // 而且
!(w2<w1) // w2 < w1时它非真
这个有意义：两个值如果没有哪个在另一个之前（关于某个排序标准），那么它们等价（按照那个标准）。
在一般情况下，用于关联容器的比较函数不是operator<或甚至less，它是用户定义的判断式。（关于判断式的
更多信息参见条款39。）每个标准关联容器通过它的key_comp成员函数来访问排序判断式，所以如果下式求
值为真，两个对象x和y关于一个关联容器c的排序标准有等价的值：
!c.key_comp()(x, y) && !c.key_comp()(y, x) // 在c的排序顺序中
// 如果x在y之前它非真，
// 同时在c的排序顺序中
// 如果y在x之前它非真
表达式!c.key_comp()(x, y)看起来很丑陋，但一旦你知道c.key_comp()返回一个函数（或一个函数对象），丑
陋就消散了。!c.key_comp()(x, y)只不过是调用key_comp返回的函数（或函数对象），并把x和y作为实参。然
后对结果取反，c.key_comp()(x, y)仅当在c的排序顺序中x在y之前时返回真，所以!c.key_comp()(x, y)仅当在c的
排序顺序中x不在y之前时为真。
要完全领会相等和等价的含义，考虑一个忽略大小写的set<string>，也就是set的比较函数忽略字符串中字符
大小写的set<string>。这样的比较函数会认为“STL”和“stL”是等价的。条款35演示了怎么实现一个函数，
ciStringCompare，它进行了忽略大小写比较，但set要一个比较函数的类型，不是真的函数。要天平这个鸿
沟，我们写一个operator()调用了ciStringCompare的仿函数类：
struct CIStringCompare: // 用于忽略大小写
public // 字符串比较的类；
binary_function<string, string, bool> { // 关于这个基类的信息
// 参见条款40
bool operator()(const string& lhs,
const string& rhs) const

haoji

{
return ciStringCompare(lhs, rhs); // 关于ciStringCompare
} // 是怎么实现的参见条款35
}
给定CIStringCompare，要建立一个忽略大小写的set<string>就很简单了：
set<string, CIStringCompare> ciss; // ciss = “case-insensitive
// string set”
如果我们向这个set中插入“Persephone”和“persephone”，只有第一个字符串加入了，因为第二个等价于第
一个：
ciss.insert("Persephone"); // 一个新元素添加到set中
ciss.insert("persephone"); // 没有新元素添加到set中
如果我们现在使用set的find成员函数搜索字符串“persephone”，搜索会成功，
if (ciss.find("persephone") != ciss.end())... // 这个测试会成功
但如果我们用非成员的find算法，搜索会失败：
if (find(ciss.begin(), ciss.end(),
"persephone") != ciss.end())... // 这个测试会失败
那是因为“persephone”等价于“Persephone”（关于比较仿函数CIStringCompare），但不等于它（因为string
("persephone") != string("Persephone")）。这个例子演示了为什么你应该跟随条款44的建议优先选择成员函数
（就像set::find）而不是非成员兄弟（就像find）的一个理由。
你可能会奇怪为什么标准关联容器是基于等价而不是相等。毕竟，大多数程序员对相等有感觉而缺乏等价的
感觉。（如果不是这样，那就不需要本条款了。）答案乍看起来很简单，但你看得越近，就会发现越多问
题。
标准关联容器保持有序，所以每个容器必须有一个定义了怎么保持东西有序的比较函数（默认是less）。等价
是根据这个比较函数定义的，所以标准关联容器的用户只需要为他们要使用的任意容器指定一个比较函数

haoji

（决定排序顺序的那个）。如果关联容器使用相等来决定两个对象是否有相同的值，那么每个关联容器就需
要，除了它用于排序的比较函数，还需要一个用于判断两个值是否相等的比较函数。（默认的，这个比较函
数大概应该是equal_to，但有趣的是equal_to从没有在STL中用做默认比较函数。当在STL中需要相等时，习惯
是简单地直接调用operator==。比如，这是非成员find算法所作的。）
让我们假设我们有一个类似set的STL容器叫做set2CF，“set with two comparison functions”。第一个比较函数
用来决定set的排序顺序，第二个用来决定是否两个对象有相同的值。现在考虑这个set2CF：
set2CF<string, CIStringCompare, equal_to<string> > s;
在这里，s内部排序它的字符串时不考虑大小写，等价标准直觉上是这样：如果两个字符串中一个等于另一
个，那么它们有相同的值。让我们向s中插入哈迪斯强娶的新娘（Persephone）的两个拼写：
s.insert("Persephone");
s.insert("persephone");
着该怎么办？如果我们说"Persephone" != "persephone"然后两个都插入s，它们应该是什么顺序？记住排序函数
不能分别告诉它们。我们可以以任意顺序插入，因此放弃以确定的顺序遍历set内容的能力吗？（不能已确定
的顺序遍历关联容器元素已经折磨着multiset和multimap了，因为标准没有规定等价的值（对于multiset）或键
（对于multimap）的相对顺序。）或者我们坚持s的内容的一个确定顺序并忽略第二次插入的尝试
（“persephone”的那个）? 如果我们那么做，这里会发生什么？
if (s.find("persephone") != s.end())... // 这个测试成功或失败？
大概find使用了等价检查，但如果我们为了维护s中元素的一个确定顺序而忽略了第二个insert的调用，这个
find会失败，即使“persephone”的插入由于它是一个重复的值的原则而被忽略！
总之，通过只使用一个比较函数并使用等价作为两个值“相等”的意义的仲裁者，标准关联容器避开了很多
会由允许两个比较函数而引发的困难。一开始行为可能看起来有些奇怪（特别是当你发现成员和非成员find
可能返回不同结果），但最后，它避免了会由在标准关联容器中混用相等和等价造成的混乱。
有趣的是，一旦你离开有序的关联容器的领域，情况就变了，相等对等价的问题会——已经——重临了。有
两个基于散列表的非标准（但很常见）关联容器的一般设计。一个设计是基于相等，而另一个是基于等价。
我鼓励你转到条款25去学更多这样的容器和设计以决定该用哪个。

haoji

Center of STL Study
——最优秀的STL学习网站
条款20：为指针的关联容器指定比较类型
假定你有一个string*指针的set，你把一些动物的名字插入进set：
set<string*> ssp; // ssp = “set of string ptrs”
ssp.insert(new string("Anteater"));
ssp.insert(new string("Wombat"));
ssp.insert(new string("Lemur"));
ssp.insert(new string("Penguin"));
然后你写了下列代码打印set的内容，希望字符串按字母顺序出现。毕竟，确定set保持它们的内容有序。
for (set<string*>::const_iterator i = ssp.begin(); // 你希望看到
i != ssp.end(); // 这个：“Anteater”
++i) // “Lemur”，“Penguin”，
cout << *i << endl; // “Wombat”
注释描述了你希望看见的，但你根本没看见。取而代之的是，你看见四个十六进制的数。它们是指针的值。
因为set容纳指针，*i不是一个string，它是一个string的指针。让这成为提醒你坚持条款43的指导并避免自己写
循环的一课。如果你已经改为调用copy算法，
copy(ssp.begin(), ssp.end(), // 把ssp中的字符串
ostream_iterator<string>(cout, "\n")); // 拷贝到cout（但这
// 不能编译）
你将不仅打更少的字符，而且你将很快会查明你的错误，因为这个copy的调用将不能编译，ostream_iterator需
要知道被打印的对象的类型，所以当你告诉它是一个string时（通过作为模板参数传递），编译器检测到那和
ssp中储存的对象类型（是string*）之间不匹配，它们会拒绝编译代码。获得了额外的类型安全。
如果你愤怒地把显式循环中的*i改为**i，你可能可以得到你想要的输出，但也可能不。是的，动物名字将被
打印，但它们按字母顺序出现的机会只是24份之1。ssp保持它的内容有序，但是它容纳的是指针，所以它以
指针的值排序，而不以string值。对于四个指针值可能有24种排列（译注：4! = 4 * 3 * 2 * 1 = 24），所以指针被

haoji

储存时有24种可能的顺序。因此你看见字符串按字母排序有24份之1的几率。[1]
为了克服这个问题，你应该回忆起
set<string*> ssp;
是这个的简写：
set<string*, less<string*> > ssp;
好，为了完全准确，它是
set<string*, less<string*>, allocator<string*> > ssp;
的简化，但是分配器在本条款里与我们无关，所以我们将忽略它们。
如果你想要string*指针以字符串值确定顺序被储存在set中，你不能使用默认比较仿函数类less<string*>。你必
须改为写你自己的比较仿函数类，它的对象带有string*指针并按照指向的字符串值来进行排序。就像这样：
struct StringPtrLess:
public binary_function<const string*, // 使用这个基类
const string*, // 的理由参见条款40
bool> {
bool operator()(const string *ps1, const string *ps2) const
{
return *ps1 < *ps2;
}
};
然后你可以使用StringPtrLess作为ssp的比较类型：
typedef set<string*, StringPtrLess> StringPtrSet;
StringPtrSet ssp; // 建立字符串的集合，
// 按照StringPtrLess定义的顺序排序

haoji

... // 和前面一样插入
// 同样四个字符串
现在你的循环最后将做你想要它做的（也就是前面你使用*i代替**i所修正的问题）：
for (StringPtrSet::const_iterator i = ssp.begin(); // 打印“Anteater”，
i != ssp.end(); // “Lemur”
++i) // “Penguin”
cout << **i << endl; // “Wombat”
如果你想要改为使用算法，你可以写一个知道怎么在打印string*指针之前对它们解引用的函数，然后和
for_each联用那个函数：
void print(const string *ps) // 把ps指向的
{ // 对象打印到cout
cout << *ps << endl;
}
for_each(ssp.begin(), ssp.end(), print); // 在ssp中的每个
// 元素上调用print
或者你想象并写出了泛型的解引用仿函数类，然后让它和transform与ostream_iterator连用：
// 当本类型的仿函数被传入一个T*时，它们返回一个const T&
struct Dereference {
template <typename T>
const T& operator()(const T *ptr) const
{
return *ptr;
}
};
transform(ssp.begin(), ssp.end(), // 通过解引用“转换”
ostream_iterator<string>(cout, "\n"), // ssp中的每个元素，
Dereference()); // 把结果写入cout

haoji

但是，用算法代替循环不是要点，至少对于本条款来说是这样的。（它是条款43的要点。）要点是无论何时
你建立一个指针的标准关联容器，你必须记住容器会以指针的值排序。这基本上不是你想要的，所以你几乎
总是需要建立自己的仿函数类作为比较类型。
注意到我写的是“比较类型”。你可能奇怪为什么必须特意创造一个仿函数类而不是简单地为set写一个比较
函数。例如，你可能想试试：
bool stringPtrLess(const string* ps1, // 将成为用于
const string* ps2) // 按字符串值
{ // 排序的string*指针
return *ps1 < *ps2; // 的比较函数
}
set<string*, stringPtrLess> ssp; // 假设使用stringPtrLess
// 作为ssp的比较函数；
// 这不能编译
这里的问题是每个set模板的第三个参数都是一种类型。令人遗憾的是，stringPtrLess不是一种类型，它是一个
函数。这就是为什么尝试使用stringPtrLess作为set的比较函数不能编译的原因，set不要一个函数，它要的是能
在内部用实例化建立函数的一种类型。
无论何时你建立指针的关联容器，注意你也得指定容器的比较类型。大多数时候，你的比较类型只是解引用
指针并比较所指向的对象（就像上面的StringPtrLess做的那样）。鉴于这种情况，你手头最好也能有一个用于
那种比较的仿函数模板。像这样：
struct DereferenceLess {
template <typename PtrType>
bool operator()(PtrType pT1, // 参数是值传递的，
PtrType pT2) const // 因为我们希望它们
{ // 是（或行为像）指针
return *pT1 < *pT2;
}
};
这样的模板消除了写像StringPtrLess那样的类的需要，因为我们可以改为使用DereferenceLess：
set<string*, DereferenceLess> ssp; // 行为就像

haoji

// set<string*, StringPtrLess>
噢，还有一件事。本条款是关于指针的关联容器，但它也可以应用于表现为指针的对象的容器，例如，智能
指针和迭代器。如果你有一个智能指针或迭代器的关联容器，那也得为它指定比较类型。幸运的是，指针的
这个解决方案也可以用于类似指针的对象。正如DereferenceLess适合作为T*的关联容器的比较类型一样，它也
可以作为T对象的迭代器和智能指针容器的比较类型。
[1] 实际上，这24种排列很可能不是平等的，所以“24份之1”的陈述有点使人误解。确实，有24个不同的顺
序，而且你可能得到它们中的任何一个。