《Effective STL》

haoji

注意力集中在参数的类型InputIterator：
template<typename InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last);
当遇到distance调用时，你的编译器需要根据使用的实参类型推断出InputIterator的类型。再来看看我所说的不
太正确的distance调用：
advance(i, distance(i, ci)); // 调整i，指向ci位置
有两个参数传递给distance，i和ci。i的类型是Iter，即deque<int>::iterator的typedef。对编译器来说，这表明调
用distance的InputIterator是deque<int>::iterator。但ci是ConstIter，即deque<int>::const_iterator的typedef。这表明
那个InputIterator是deque<int>::const_iterator。InputIterator不可能同时有两种不同的类型，所以调用distance失
败。一般会造成一些冗长的出错信息，可能会也可能不会说明是编译器无法得出InputIterator是什么类型。
要顺利地调用distance，你需要排除歧义。最简单的办法就是显式的指明distance调用的模板参数类型，从而避
免编译器自己得出它们的类型：
advance(i, distance<ConstIter>(i, ci));
我们现在知道了怎么通过advance和distance获取const_iterator相应的iterator了。但另一个我们现在一直避开却
很值的考虑的实际问题是：这个技巧的效率如何？答案很简单。取决于你所转换的究竟是什么样的迭代器。
对于随机访问的迭代器（比如vector、string和deque的）而言，这是常数时间的操作。对于双向迭代器（也就
是，所有其它容器和包括散列容器的一些实现[4]（参见条款25））而言，这是线性时间的操作。
因为它可能花费线性时间的代价来产生一个和const_iterator等价的iterator，并且因为如果不能访问
const_iterator所属的容器这个操作就无法完成。从这个角度出发，也许你需要重新审视你从const_iterator产生
iterator的设计。事实上那样的考虑帮助激发了条款26，它建议你当处理容器时尽量用iterator代替const和reverse
迭代器。
[1] 两个最常见的基于散列表的STL容器实现来自于Dinkumware和SGI。你可以从P.J.Plauger 1998年11月份的
CUJ专栏《Hash Tables》中找到一个Dinkumware方法的概览。我所知道的唯一的SGI的实现方法的概览来自

haoji

Effective STL的条款25，但它的接口的描述在SGI的STL网站。
[2] 当使用STLport的调试模式时会出现这种情况。你可以从STLport的网站上了解到STLport和它的调试模式。
[3] 我后来发现在这里描述的这种方法可能在使用引用计数的string实现上失败。细节请参考在http://www.
aristeia.com/BookErrata/estl1e-errata.html的jep的 8/22/01关于本书第121页的注释。
[4] Dinkumware的散列容器提供了双向的迭代器。SGI的、STLport的和Metrowerks的散列容器只提供了前向迭
代器。

haoji

Center of STL Study
——最优秀的STL学习网站
条款28：了解如何通过reverse_iterator的base得到iterator
调用reverse_iterator的base成员函数可以产生“对应的”iterator，但这句话有些辞不达意。举个例子，看一下
这段代码，我们首先把从数字1-5放进一个vector中，然后产生一个指向3的reverse_iterator，并且通过
reverse_iterator的base初始化一个iterator：
vector<int> v;
v.reserve(5); // 参见条款14
for(int i = 0；i < 5; ++ i) { // 向vector插入1到5
v.push_back(i);
}
vector<int>::reverse_iterator ri = // 使ri指向3
find(v.rbegin(), v.rend(), 3);
vector<int>::iterator i(ri.base()); // 使i和ri的base一样
执行上述代码后，可以想到产生的结果就像这样：
这张图很好，显示了reverse_iterator和它对应的base iterator之间特有的偏移量，就像rbegin()和rend()与相关的
begin()和end()一样，但并没有说出了所有你需要知道的东西。特别是，它并没有解释怎样在ri上实现你在i上
想要完成的操作。正如条款26解释的，有些容器的成员函数只接受iterator类型的参数，所以如果你想要在ri所
指的位置插入一个新元素，你不能直接这么做，因为vector的insert函数不接受reverse_iterator。如果你想要删
除ri所指位置上的元素也会有同样的问题。erase成员函数会拒绝reverse_iterator，坚持要求iterator。为了完成
删除和一些形式的插入操作，你必须先通过base函数将reverse_iterator转换成iterator，然后用iterator来完成工
作。

haoji

先让我们假设你要在ri指出的位置上把一个新元素插入v。特别的，我们假设你要插入的值是99。记住ri在上
图中遍历的顺序是自右向左，而且插入操作会将新元素插入到ri位置，并且将原先ri位置的元素移到遍历过程
的“下一个”位置，我们认为3应该出现在99的左侧。插入操作之后，v看起来像这样：
当然，我们不能用ri来指定插入的地方，因为它不是一个iterator。我们必须用i来代替。如上所述，当ri指向3
时，i（就是ri.base()）指向4。如果我们用ri来指定插入位置，那么用i指向插入位置，那个假设就是正确的。
结论呢？
● 要实现在一个reverse_iterator ri指出的位置上插入新元素，在ri.base()指向的位置插入就行了。对于
insert操作而言，ri和ri.base()是等价的，而且ri.base()真的是ri对应的iterator。
现在再来考虑删除元素的情况。回顾一下最初的vector（也就是在插入99之前）ri与i的关系：
如果你要删除ri指向的元素，你不能直接使用i了，因为i与ri不是指向同一个元素。因此，你要删除的是i的前
一个元素。
● 要实现在一个reverse_iterator ri指出的位置上删除元素，就应该删除ri.base()的前一个元素。对于删除操
作而言，ri和ri.base()并不等价，而且ri.base()不是ri对应的iterator。
我们还是有必要看看删除操作的代码，因为它还挺令人惊讶的。
vector<int> v;
... // 向v插入1到5，同上
vecot<int>::reverse_iterator ri =
find(v.rbegin(), v.rend(), 3); // 同上，ri指向3
v.erase(--ri.base()); // 尝试删除ri.base()前面的元素；

haoji

// 对于vector，一般来说编译不通过
这个设计并不存在什么问题。表达式--ri.base()确实能够指出我们需要删除的元素。而且，它们能够处理除了
vector和string之外的其他所有容器。它可能也能处理vector和string，但对于大多数vector和string的实现，它无
法通过编译。在这样的实现下，iterator（和const_iterator）会采用内建的指针来实现，所以ri.base()的结果是
一个指针。
C和C++都规定了不能直接修改函数返回的指针，所以在string和vector的迭代器是指针的STL平台上，像--ri.
base()这样的表达式无法通过编译。要移植从一个由reverse_iterator指出的位置删除元素时，你应该尽量避免
修改base的返回值。没问题。如果你不能减少调用base的返回值，只需要先增加reverse_iterator的值，然后再
调用base！
... // 同上
v.erase((++ri).base()); // 删除ri指向的元素；
// 这下编译没问题了！
因为这个方法适用于所有的标准容器，这是删除一个由reverse_iterator指出的元素时首选的技巧。
现在已经很清楚了，reverse_iterator的base成员函数返回一个“对应的”iterator的说法并不准确。对于插入操
作而言，的确如此；但是对于删除操作，并非如此。当需要把reverse_iterator转换成iterator的时候，有一点非
常重要的是你必须知道你准备怎么处理返回的iterator，因为只有这样你才能决定你得到的iterator是否是你需
要的。

haoji

Center of STL Study
——最优秀的STL学习网站
条款29：需要一个一个字符输入时考虑使用istreambuf_iterator
假设我们要把一个文本文件拷贝到一个字符串对象中。似乎可以用一种很有道理的方法完成：
ifstream inputFile("interestingData.txt");
string fileData((istream_iterator<char>(inputFile)), // 把inputFile读入
istream_iterator<char>()); // fileData；关于为什么
// 它不是很正确请看下文
// 关于这个语法的警告
// 参见条款6
很快你就会发现这种方法无法把文件中的空格拷贝到字符串中。那是因为istream_iterators使用operator>>函数
来进行真的读取，而且operator>>函数在默认情况下忽略空格。
假如你想保留空格，你要的做就是覆盖默认情况。只要清除输入流的skipws标志就行了：
ifstream inputFile("interestingData.txt");
inputFile.unset(ios::skipws); // 关闭inputFile的
// 忽略空格标志
string fileData((istream_iterator<char>(inputFile)), istream_iterator<char>());
现在inputFile中的所有字符都拷贝到fileData中了。
唉，你会发现它们的拷贝速度不像你想象的那么快。istream_iterators所依靠的operator>>函数进行的是格式化
输入，这意味着每次你调用的时候它们都必须做大量工作。它们必须建立和销毁岗哨（sentry）对象（为每个
operator>>调用进行建立和清除活动的特殊的iostream对象），它们必须检查可能影响它们行为的流标志（比
如skipws），它们必须进行全面的读取错误检查，而且如果它们遇到问题，它们必须检查流的异常掩码来决
定是否该抛出一个异常。如果进行格式化输入，那些都是重要的活动，但如果你需要的只是从输入流中抓取
下一个字符，那就过度了。
一个更高效的方法是使用STL最好的秘密武器之一：istreambuf_iterators。你可以像istream_iterator一样使用
istreambuf_iterator，但istream_iterator<char>对象使用operator>>来从输入流中读取单个字符。
istreambuf_iterator<char>对象进入流的缓冲区并直接读取下一个字符。（更明确地说，一个

haoji

istreambuf_iterator<char> 对象从一个istream s中读取会调用s.rdbuf()->sgetc()来读s的下一个字符。）把我们的文
件读取代码改为使用istreambuf_iterator相当简单，大多数Visual Basic程序员都可以在两次尝试内做对：
ifstream inputFile("interestingData.txt");
string fileData((istreambuf_iterator<char>(inputFile)),
istreambuf_iterator<char>());
注意这里不需要“unset”skipws标志，istreambuf_iterator不忽略任何字符。它们只抓取流缓冲区的下一个字
符。
相对于istream_iterator，它们抓取得更快——在我进行的简单测试中能快40%，如果你的结果不同也不用惊
奇。如果随时间流逝，速度优势不断增加也不必奇怪，因为istreambuf_iterator存在于STL的一个不常访问的角
落，所以实现还没有花很多时间来优化。比如，在我用过的一个实现中，istreambuf_iterator在我的主要测试
中只比istream_iterator快了大约5%。那样的实现显然还有很多余地来优化它们的istreambuf_iterator实现。如果
你需要一个一个地读取流中的字符，你不需要格式化输入的威力，你关心的是它们花多少时间来读取流，和
明显的性能提高相比，为每个迭代器多键入三个字符的代价是微弱的。对于无格式的一个一个字符输入，你
总是应该考虑使用istreambuf_iterator。
当你了解它之后，你也应该考虑把ostreambuf_iterator用于相应的无格式一个一个字符输出的作。它们没有了
ostream_iterator的开销（和灵活性），所以它们通常也做得更好。

haoji

Center of STL Study
——最优秀的STL学习网站
算法
我注意到从第一章开始，容器就占据了STL喝彩声中最大的一份。在某种意义上，这是可以理解的。容器有
着非凡的造诣，它们使大批C++程序员每天的基本生活变得简单。尽管如此，STL算法的权利也很重要，一
样有能力减轻程序员的负担。事实上，有超过100个算法，很容易证明比起容器，它们提供给程序员更精巧
的工具集（起码一样强）。也许它们的数量是一部分问题。搞清八种截然不同的容器类型明显比记住70个算
法的名字并且弄明白哪个做了什么要容易。
在本章，我有两个主要的目标。第一，我要通过向你演示一些比较少见的算法怎么使你的生活变得简单来向
你介绍它们。放心，我不会用一堆需要记忆的名字来惩罚你。我在这一章演示算法是因为它们能解决常见问
题，比如进行忽略大小写的字符串比较，在容器中高效地查找n个最想要的对象，统计区间中所有对象的特
性，还实现了copy_if（一个来自最初的HP STL的算法，但在标准化过程中去掉了）的行为。
我的第二个目标是向你演示怎么避免算法的常见用法问题。例如，你不能调用remove或它的兄弟remove_if和
unique，除非你真的知道这些算法做（和不做）什么。特别是当你删除的区间容纳的是指针时。同样，很多
算法只和有序区间配合，所以你需要知道它们是什么和为什么它们会有这个限制。最后，最常见的算法相关
错误之一是让一个算法把它的结果写向一个不存在的位置，所以我解释了这个谬论是怎么发生的和怎么确认
你没有受此折磨。
本章的结束后，你可能不会把算法和容器放在同样的高度，但我希望你会比以前更关注它们。

haoji

Center of STL Study
——最优秀的STL学习网站
条款30：确保目标区间足够大
STL容器在被添加时（通过insert、push_front、push_back等）自动扩展它们自己来容纳新对象。这工作的很
好，有些程序员因为这个信仰而被麻痹，认为他们不必担心要为容器中的对象腾出空间，因为容器自己可以
照顾好这些。如果是那样就好了！当程序员想向容器中插入对象但并没有告诉STL他们所想的时，问题出现
了。这是一个常见的可以自我表现的方法：
int transmogrify(int x); // 这个函数从x
// 产生一些新值
vector<int> values;
... // 把数据放入values
vector<int> results; // 把transmogrify应用于
transform(values.begin(), values.end(), // values中的每个对象
results.end(), // 把这个返回的values
transmogrify); // 附加到results
// 这段代码有bug！
在本例中，transform被告知它的目的区间是从results.end()开始的，所以那就是开始写在values的每个元素上调
用transmogrify的结果的地方。就像所有使用目标区间的算法，transform通过对目标区间的元素赋值的方法写
入结果，transform会把transmogrify应用于values[0]并把结果赋给*results.end()。然后它会把transmogrify应用于
value[1]并把结果赋给*(results.end()+1)。那只能带来灾难，因为在*results.end()没有对象，*(results.end()+1)也
没有！调用transform是错误的，因为它会给不存在的对象赋值。（条款50解释了STL的一个调试实现怎么在运
行期检测这个问题。）犯了这种错误的程序员几乎总是以为他们调用算法的结果能插入目标容器。如果那是
你想要发生的，你就必须说出来。STL是一个库，不是一个精神。在本例中，说“请把transform的结果放入
叫做results容器的结尾”的方式是调用back_inserter来产生指定目标区间起点的迭代器：
vector<int> results; // 把transmogrify应用于
transform(values.begin(), values.end(), // values中的每个对象，
back_inserter(results), // 在results的结尾
transmogrify); // 插入返回的values
在内部，back_inserter返回的迭代器会调用push_back，所以你可以在任何提供push_back的容器上使用
back_inserter（也就是任何标准序列容器：vector、string、deque和list）。如果你想让一个算法在容器的前端插

haoji

入东西，你可以使用front_inserter。在内部，front_inserter利用了push_front，所以front_insert只和提供那个成
员函数的容器配合（也就是deque和list）：
... // 同上
list<int> results; // results现在是list
transform(values.begin(), values.end(), // 在results前端
front_inserter(results), // 以反序
transmogrify); // 插入transform的结果
因为front_inserter用push_front把每个对象添加到results，results中的对象顺序会和values中对应的对象顺序相
反。这也是为什么front_inserter没有back_inserter那么常用的原因之一。另一个原因是vector不提供push_front，
所以front_inserter不能用于vector。
如果你要transform把输出结果放在results前端，但你也要输出和values中对应的对象顺序相同，只要以相反的
顺序迭代values：
list<int> results; // 同上
transform(values.rbegin(), values.rend(), // 在results前端
front_inserter(results), // 插入transform的结果
transmogrify); // 保持相对的对象顺序
front_inserter让你强制算法在容器前端插入它们的结果，back_inserter让你告诉它们把结果放在容器后端，有
点惊人的是inserter允许你强制算法把它们的结果插入容器中的任意位置：
vector<int> values; // 同上
...
vector<int> results; // 同上，除了现在
... // 在调用transform前
// results已经有一些数据
transform(values.begin(), values.end(), // 把transmogrify的
inserter(results, results.begin() + results.size()/2), // 结果插入
transmogrify); // results的中间
不管你是否使用了back_inserter、front_inserter或inserter，每次对目的区间的插入只完成一个对象。条款5解释
了对于连续内存容器（vector、string和deque）来说这可能很昂贵，但条款5的建议解决方法（使用区间成员函
数）不能应用于使用算法来完成插入的情况。在本例中，transform会对目的区间每次写入一个值，你无法改