《Effective STL》

haoji

template<typename T,
typename HashFunction = hash<T>,
typename CompareFunction = equa_to<T>,
typename Allocator = allocator<T> >
class hash_set;
SGI设计的一个值得注意的方面是使用equal_to作为默认比较函数。这违背标准关联容器的约定——默认比较
函数是less。这个设计结果不仅仅表示简单地改变默认比较函数。SGI的散列容器确定在一个散列容器中的两
个对象是否有相同的值是通过相等测试，而不是等价（参见条款19）。对于散列容器来说，这不是一个不合
理的决定，因为散列关联容器，不像它们在标准中的（通常基于树）兄弟，不需要保持有序。
Dinkumware设计的散列容器采取一些不同的策略。它仍然允许你指定对象类型、散列函数类型、比较函数类
型和分配器类型，但是它把默认的散列和比较函数移进一个单独的类似特性的叫做hash_compare的类，而且
它把hash_compare作为容器模板的HashingInfo实参的默认值。（如果你不熟悉“特性”类的概念，打开一本
好的STL参考，比如Josuttis的《C++ Standard Library》[3]并学习char_traits和iterator_traits模板的动机和实
现。）
例如，这是Dinkumware的hash_set声明（再次为演示而调整过）：
template<typename T, typename CompareFunction>
class hash_compare;
template<typename T,
typename HashingInfo = hash_compare<T, less<T> >
typename Allocator = allocator<T> >
class hash_set;
这种接口设计有趣的地方是HashingInfo的使用。容器的散列和比较函数储存在那里，但HashingInfo类型也容
纳了控制表中桶（bucket）最小数量，以及容器元素对桶的最大允许比率的枚举。当这比率被超过时，表中
桶的数量就增加，而表中的一些元素需要重新散列。（SGI提供具有类似控制表中桶和表中元素对桶比率的
成员函数。）（译注：如果你不知道桶和散列表的原理，那么看看数据结构的书中关于散列表的部分。）
做了一些为了演示的调整之后，hash_compare（HashingInfo的默认值）看起来或多或少像这样：
template<typename T, typename CompareFunction = less<T> >
class hash_compare {
public:

haoji

enum {
bucket_size = 4, // 元素对桶的最大比率
min_buckets = 8 // 桶的最小数量
};
size_t operator()(const T&) const; // 散列函数
bool operator()(const T&, // 比较函数
const T&) const;
... // 忽略一些东西，包括
// CompareFunction的使用
}
重载operator()（在这里是实现散列和比较函数）是比你可以想象的更经常出现的一个策略。对于这一想法的
另一个应用，参见条款23。
Dinkumware设计允许你写你自己的类似hash_compare的类（也许通过从hash_compare本身派生而来），而且
只要你的类定义了bucket_size、min_buckets、两个operator()函数（一个带有一个实参，一个带有两个），加
上我已经省去的一些东西，你就能使用它来控制Dinkumware的hash_set或hash_multiset的配置和行为。
hash_map和hash_multimap的配置控制也相似。
注意不管是SGI还是Dinkumware的设计，你都能把全部决策留给实现，并仅仅写像这样的东西：
hash_set<int> intTable; // 建立一个int的散列表
要让这个可以编译，散列表必须容纳一个整数类型（例如int），因为默认散列函数一般局限于整数类型。
（SGI的默认散列函数稍微灵活一些。条款50将告诉你在哪里可以找到全部细节。）
在后端，SGI和Dinkumware的实现方法非常不同。SGI利用常用的一个元素的单链表的指针数组（桶）组成的
开放散列法。Dinkumware也利用了开放散列法，但是它的设计是基于一种新颖的数据结构——由迭代器（本
质是桶）的数组组成的元素双向链表，迭代器的相邻对表示在每个桶里元素的范围。（细节可以参考Plauger
相关主题的专栏，《Hash Tables》[16]。）
作为这些实现的用户，你可能会对SGI实现在单链表中储存表的元素，而Dinkumware实现使用一个双向链表
的事实感兴趣。差别是值得注意的，因为它影响了用于两个实现的迭代器种类。SGI的散列容器提供了前向
迭代器，因此你得放弃进行反向迭代的能力：在SGI的散列容器中没有rbegin或者rend成员函数。用于
Dinkumware散列容器的迭代器是双向的，所以它们可以提供前向和反向遍历。 在内存使用量方面，SGI的设

haoji

计比Dinkumware的节俭一点点。
哪个设计最有利于你和你的程序？我不可能知道。只有你能确定，而且本条款并不试图给你足以得出一个合
理结论的信息。取而代之的是，本条款的目标是让你知道虽然STL本身缺乏散列容器，兼容STL的散列容器
（有不同的接口、能力和行为权衡）不难得到。就SGI和STLport的实现而言，你甚至可以免费得到它们，因
为它们可以自由下载。

haoji

Center of STL Study
——最优秀的STL学习网站
迭代器
乍看来，迭代器似乎很直观。但凑近了看，你会发现标准STL容器提供了四种不同的迭代器：iterator、
const_iterator、reverse_iterator和const_reverse_iterator。很快你会注意到在这四种类型中，容器的insert和erase的
某些形式只接受其中一种。那是问题的开始。为什么有四种迭代器？它们之间的关系是什么？它们可以互相
转化吗？在调用算法和STL实用函数时不同类型可以混合使用吗？这些类型是怎么关联到容器和它们的成员
函数的？
本章回答了这些问题，也介绍了一个比通常更值得注意的迭代器类型：istreambuf_iterator。如果你喜欢STL，
但你不喜欢读取字符流时istream_iterator的性能，istreambuf_iterator可能就是你正在寻找的工具。

haoji

Center of STL Study
——最优秀的STL学习网站
条款26：尽量用iterator代替const_iterator，reverse_iterator和
const_reverse_iterator
正如你所知的，每个标准容器类都提供四种迭代器类型。对于container<T>而言，iterator的作用相当于T*，
而const_iterator则相当于const T*（你可能也见过T const*这样的写法：它们意思一样[1]）。增加一个iterator或
者const_iterator可以在一个从容器开头趋向尾部的遍历中让你移动到容器的下一个元素。reverse_iterator与
const_reverse_iterator同样相当于对应的T*和const T*，所不同的是，增加reverse_iterator或者
const_reverse_iterator会在从尾到头的遍历中让你移动到容器的下一个元素。
让我向你演示两个东西。第一，看看vector<T>的insert和erase的样式：
iterator insert(iterator position, const T& x);
iterator erase(iterator position);
iterator erase(iterator rangeBegin, iterator rangeEnd);
每个标准容器都包含了和这差不多的函数，虽然返回类型因容器类型的不同而不同。需要注意的是：这些方
法只接受iterator类型的参数，而不是const_iterator、reverse_iterator或const_reverse_iterator。总是iterator。虽然
容器类支持四种迭代器类型，但其中的一种类型有着其他所没有的特权。那就是iterator，iterator比较特殊
[2]。
我要让你看的第二个东西是这张图，它显示了几种迭代器之间存在的转换关系：
图中显示了从iterator到const_iterator、从iterator到reverse_iterator和从reverse_iterator到const_reverse_iterator可以
进行隐式转换。并且，reverse_iterator可以通过调用其base成员函数转换为iterator。const_reverse_iterator也可以
类似地通过base转换成为const_iterator。一个图中无法显示的事实是：通过base得到的也许并非你所期待的
iterator。我们将会在条款28中详细讨论这一点。

haoji

你应该发现了没有办法从一个const_iterator转换得到一个iterator，也无法从const_reverse_iterator得到
reverse_iterator。这一点非常重要，因为这意味着如果你有一个const_iterator或者const_reverse_iterator，你会发
现让南让它们和容器的一些成员函数合作。那些成员函数要求iterator，而你无法从const迭代器类型反过来得
到iterator。当你需要指出插入位置或删除的元素时，const迭代器几乎没有用。
千万不要傻乎乎的宣称const迭代器一无是处。不，它们可以与算法默契配合，因为算法通常并不关心迭代器
是什么类型，只要是适当的种类就可以了，很多容器的成员方法也接受const迭代器。只有insert和erase的一些
形式有些吹毛求疵。
我写的是如果你要指出插入的位置或删除的元素时，const迭代器“几乎”没有用。这暗示了并不是完全没
用。那是真的。如果你找到了一个方法可以从const_iterator或const_reverse_iterator得到一个iterator，那么它们
就有用。那经常是有可能的。但这种方法并不总是行得通，而且就算可行，完成的方法也很不直观，也很缺
乏效率。这个主题将足够充实一个它自己的条款，所以如果你对这个细节感兴趣的话，请转到条款27。现
在，我们已经有足够的理由相信应该尽量使用iterator取代const或者reverse类型的迭代器：
● insert和erase的一些版本要求iterator。如果你需要调用这些函数，你就必须产生iterator，而不能用const
或reverse iterators。
● 不可能把const_iterator隐式转换成iterator，我们将会在条款27中讨论从一个const_iterator产生一个
iterator的技术并不普遍适用，而且不保证高效。
● 从reverse_iterator转换而来的iterator在转换之后可能需要相应的调整，在条款28中我们会讨论何时需要
调整以及调整的原因。
所有这些东西联合起来就能看出，如果你尽量使用iterator代替const或reverse类型的迭代器，可以使得容器的
使用更简单，更高效而且可以避免潜在的bug。
事实上，你可能会更多地面临在iterator与const_iterator之间的选择.iterator与reverse_iterator之间的选择显而易见
——依赖于从前到后或从后到前的遍历。你可以选择你需要的一种，而且即使你选择了reverse_iterator，当你
要调用需要iterator的容器成员函数时，你仍然可以通过base得到相应的iterator（可能需要一些调整，参见条款
28）。
当在iterator和const_iterator之间作选择的时候，你有更充分的理由选择iterator，即使const_iterator同样可行而
且即使你并不需要调用容器类的任何成员函数。其中的令人讨厌的原因包括iterator与const_iterator之间的比
较。我希望我们都可以赞成这是合理的代码：
typedef deque<int> IntDeque; // typedef可以极大地简化
typedef IntDeque::iterator Iter; // STL容器类和iterator
typedef IntDeque::const_iterator ConstIter; // 的操作。

haoji

Iter i;
ConstIter ci;
... // 同一个容器
if (i == ci) ... // 比较iterator和const_iterator
我们所做的只是同一个容器中两个迭代器之间的比较，这是STL中最基本的动作。唯一的变化是等号的一边
的类型是iterator，而另一边的类型是const_iterator。这应该不是问题，因为iterator应该在比较之前隐式的转换
成const_iterator，真正的比较应该在两个const_iterator之间进行。
对于设计良好的STL实现而言，情况确实如此。但对于其它一些实现，这段代码甚至无法通过编译。原因在
于，这些实现将const_iterator的operator==作为const_iterator的一个成员函数而不是非成员函数。而问题的解
决之道显得非常有趣：只要像这样交换两个iterator的位置：
if (ci == i)... // 当上面比较无法
// 通过编译时的解决方法
不仅是比较是否相等，只要你在同一个表达式中混用iterator和const_iterator（或者reverse_iterator和
const_reverse_iterator），这样的问题就可能会出现。比如，当你试图在两个随机存取迭代器之间进行减法操
作时：
if (i - ci >= 3) ... // 如果i与ci之间至少有三个元素...
如果迭代器的类型不同，你的（正确的）代码可能会被（错误地）拒绝。本例中最简单的解决方法是通过一
个（安全的）映射把iterator转换为const_iterator：
if (static_cast<ConstIter>(i) - ci >= 3) ... // 当上面的代码无法
// 通过编译时的解决方法
避免这类问题的最简单的方法是减少混用不同类型的迭代器的机会，换句话说，又回到了尽量用iterator代替
const_iterator。从常量正确性的角度来看（一个固然有价值的角度），仅仅为了避免一些潜在的STL实现的弊
端（而且，这些弊端都有变通办法）而抛弃const_iterator显得有欠公允。但综合考虑到iterator与一些容器类成
员函数的粘连关系，从实践得出const_iterator没有iterator好用的结论是很难避免的。更何况，有时并不值得卷
入const_iterator的麻烦中去。

haoji

[1]关于这个主题的完整的文章，请参考1999年2月《Embedded Systems Programming》上刊登的《const T vs. T
const》，作者是Dan Saks。
[2]“iterator比较特殊”的原因并不清楚。HP的最早的STL实现包含了带有iterator参数的insert和erase，而这个
设计问题在标准化的过程中并没有重新考虑。但是在以后，这可能会改变，因为程序库工作组发布了#180记
录，说明了“这个问题在下一个标准版本中会作为综合回顾的const问题而被考虑”（C++程序库问题可以从
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html看到）

haoji

Center of STL Study
——最优秀的STL学习网站
条款27：用distance和advance把const_iterator转化成iterator
条款26中指出有些容器成员函数只接受iterator作为参数，而不是const_iterator。那么，如果你只有一个
const_iterator，而你要在它所指向的容器位置上插入新元素呢？也就是如何把const_iterator转化为iterator呢？
因为正如条款26所解释的，并不存在从const_iterator到iterator之间的隐式转换，所以你必须成为这次行动的主
角。
我知道你在想什么。你正在想，“每当无路可走的时候，就举起大锤！”。在C++的世界里，你的意思只能
是：映射。这种想法很可耻。真不知道你是哪儿学来的。
让我们面对困扰在你面前的问题。看看当你把一个const_iterator映射为iterator时会发生什么：
typedef deque<int> IntDeque; // 方便的typedef
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;
ConstIter ci; // ci是const_iterator
...
Iter i(ci); // 错误！没有从const_iterator
// 到iterator隐式转换的途径
Iter i(const_cast<Iter>(ci)); // 仍是个错误！不能从const_iterator
// 映射为iterator！
这里只是以deque为例，但是用其它容器类——list、set、multiset、map、multimap甚至条款25描述的散列表容
器[1]——的结果一样。使用映射的行也许在vector或string的代码时能够编译，但这是我们马上要讨论的非常
特殊的情形。
包含映射的代码不能通过编译的原因在于，对于这些容器而言，iterator和const_iterator是完全不同的类。它们
之间并不比string和complex<float>具有更多的血缘关系。在两个毫无关联的类之间进行const_cast映射是荒谬
的，所以reinterpret_cast、static_cast甚至C风格的映射也会导致同样的结果。
唉，不能编译的代码对于vector和string容器来说也许能够通过编译。那是因为通常情况下大多数实现都会采
用真实的指针作为那些容器的迭代器。就这种实现而言，vector<T>::iterator是T*的typedef，而vector<T>::
const_iterator是const T*的typedef，string::iterator是char*的typedef，而string::const_iterator是const char*的

haoji

typedef。在这种实现的情况下，用const_cast把const_iterator映射成iterator当然可以编译而且没有问题，因为
const_iterator与iterator之间的const_cast映射被最终解释成const T*到T*的映射。但是，即使是在这种实现中，
reverse_iterator和const_reverse_iterator也是真正的类，所以你仍然不能直接用const_cast把const_reverse_iterator映
射成reverse_iterator。而且，正如条款50解释的，这些实现通常只会在Release模式时才使用指针表示vector和
string的迭代器[2]。所有这些事实表明，把const迭代器映射为迭代器是病态的，即使是对vector和string来说也
时，因为移植性很值得怀疑。
如果你得到一个const_iterator并且可以访问它所指向的容器，那么有一种安全的、可移植的方法获取它所对
应的iterator[3]，而且，用不着陷入类型系统的转换。下面是解决思路的本质，虽然在它编译前还要稍作修
改：
typedef deque<int> IntDeque; // 和以前一样
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;
IntDeque d;
ConstIter ci;
... // 让ci指向d
Iter i(d.begin()); // 初始化i为d.begin()
advance(i, distance(i, ci)); // 把i移到指向ci位置
// （但请留意下面关于为什么
// 在它编译前要调整的原因）
这种方法看上去非常简单，直截了当，也很让人吃惊吧。要得到与const_iterator指向同一位置的iterator，首先
将iterator指向容器的起始位置，然后把它向前移到和const_iterator距离容器起始位置的偏移量一样的位置即
可！这个任务得到了两个函数模板advance和distance的帮助，它们都在<iterator>中声明。distance返回两个指
向同一个容器的iterator之间的距离；advance则用于将一个iterator移动指定的距离。如果i和ci指向同一个容
器，那么表达式advance(i, distance(i, ci))会将i移动到与ci相同的位置上。
如果这段代码能够通过编译，它就能完成这种转换任务。但似乎事情并不那么顺利。想知道为什么，先来看
看distance的定义：
template<typename InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last);
不要被这个函数的长达56个字符的返回类型卡住，也不用理会difference_type是什么东西。取而代之的是，把