《Effective STL》

haoji

bool widgetAPCompare(const auto_ptr<Widget>& lhs,
const auto_ptr<Widget>& rhs) {
return *lhs < *rhs; // 对于这个例子，假设Widget
} // 存在operator<
vector<auto_ptr<Widget> > widgets; // 建立一个vector，然后
// 用Widget的auto_ptr填充它；
// 记住这将不能编译！
sort(widgets.begin(), widgets.end(), // 排序这个vector
widgetAPCompare);
这里的所有东西看起来都很合理，而且从概念上看所有东西也都很合理，但结果却完全不合理。例如，在排
序过程中widgets中的一个或多个auto_ptr可能已经被设为NULL。排序这个vector的行为可能已经改变了它的内
容！值得去了解这是怎么发生的。
它会这样是因为实现sort的方法——一个常见的方法，正如它呈现的——是使用了快速排序算法的某种变
体。我们不关心快速排序的妙处，但排序一个容器的基本思想是，选择容器的某个元素作为“主元”，然后
对大于和小于或等于主元的值进行递归排序。在sort内部，这样的方法多多少少看起来像这样：
template<class RandomAccessIterator, // 这个sort的声明
class Compare> // 直接来自于标准
void sort(RandomAccessIterator first,
RandomAccessIterator last,
Compare comp)
{
// 这个typedef在下面解释
typedef typename iterator_traits<RandomAccessIterator>::value_type
ElementType;
RandomAccessIterator i;
... // 让i指向主元
ElementType pivotValue(*); // 把主元拷贝到一个
// 局部临时变量中；参见
// 下面的讨论
... // 做剩下的排序工作
}
除非你是在阅读STL源代码方面很有经验，否则这看起来可能有些麻烦，但其实并不坏。唯一的难点是引用
了iterator_traits<RandomAccessIterator>::value_type，而只不过是传给sort的迭代器所指向的对象类型的怪异的

haoji

STL方式。（当我们涉及iterator_traits<RandomAccessIterator>::value_type时，我们必须在它前面写上
typename，因为它是一个依赖于模板参数类型的名字，在这里是RandomAccessIterator。更多关于typename用
法的信息，翻到第7页。）
上面代码中棘手的是这一行，
ElementType pivotValue(*i);
因为它把一个元素从保存的区间拷贝到局部临时对象中。在我们的例子里，这个元素是一个
auto_ptr<Widget>，所以这个拷贝操作默默地把被拷贝的auto_ptr——vector中的那个——设为NULL。另外，
当pivotValue出了生存期，它会自动删除指向的Widget。这时sort调用返回了，vector的内容已经改变了，而且
至少一个Widget已经被删除了。也可能有几个vector元素已经被设为NULL，而且几个widget已经被删除，因
为快速排序是一种递归算法，递归的每一层都会拷贝一个主元。
这落入了一个很讨厌的陷阱，这也是为什么标准委员会那么努力地确保你不会掉进去。通过永不建立
auto_ptr的容器来尊重它对你的利益的工作，即使你的STL平台允许那么做。
如果你的目标是智能指针的容器，这不意味着你不走运了。智能指针的容器是很好的，条款50描述了你在哪
里可以找到和STL容器咬合良好的智能指针。只不过auto_ptr不是那样的智能指针。完全不是。
[1] 如果你对auto_ptr标准化的痛苦历程感兴趣，把你的web浏览器指向More Effective C++网站的auto_ptr更新
页[29]。

haoji

Center of STL Study
——最优秀的STL学习网站
条款9：在删除选项中仔细选择
假定你有一个标准STL容器，c，容纳int，
Container<int> c;
而你想把c中所有值为1963的对象都去掉。令人吃惊的是，完成这项任务的方法因不同的容器类型而不同：没
有一种方法是通用的。
如果你有一个连续内存容器（vector、deque或string——参见条款1），最好的方法是erase-remove惯用法（参
见条款32）：
c.erase(remove(c.begin(), c.end(), 1963), // 当c是vector、string
c.end()); // 或deque时，
// erase-remove惯用法
// 是去除特定值的元素
// 的最佳方法
这方法也适合于list，但是，正如条款44解释的，list的成员函数remove更高效：
c.remove(1963); // 当c是list时，
// remove成员函数是去除
// 特定值的元素的最佳方法
当c是标准关联容器（即，set、multiset、map或multimap）时，使用任何叫做remove的东西都是完全错误的。
这样的容器没有叫做remove的成员函数，而且使用remove算法可能覆盖容器值（参见条款32），潜在地破坏
容器。（关于这样的破坏的细节，参考条款22，那个条款也解释了为什么试图在map和multimap上使用remove
肯定不能编译，而试图在set和multiset上使用可能不能编译。）
不，对于关联容器，解决问题的适当方法是调用erase：

haoji

c.erase(1963); // 当c是标准关联容器时
// erase成员函数是去除
// 特定值的元素的最佳方法
这不仅是正确的，而且很高效，只花费对数时间。（序列容器的基于删除的技术需要线性时间。）并且，关
联容器的erase成员函数有基于等价而不是相等的优势，条款19解释了这一区别的重要性。
让我们现在稍微修改一下这个问题。不是从c中除去每个有特定值的物体，让我们消除下面判断式（参见条款
39）返回真的每个对象：
bool badValue(int x); // 返回x是否是“bad”
对于序列容器（vector、string、deque和list），我们要做的只是把每个remove替换为remove_if，然后就完成
了：
c.erase(remove_if(c.begin(), c.end(), badValue), // 当c是vector、string
c.end()); // 或deque时这是去掉
// badValue返回真
// 的对象的最佳方法
c.remove_if(badValue); // 当c是list时这是去掉
// badValue返回真
// 的对象的最佳方法
对于标准关联容器，它不是很直截了当。有两种方法处理该问题，一个更容易编码，另一个更高效。“更容
易但效率较低”的解决方案用remove_copy_if把我们需要的值拷贝到一个新容器中，然后把原容器的内容和
新的交换：
AssocContainer<int> c; // c现在是一种
... // 标准关联容器
AssocContainer<int> goodValues; // 用于容纳不删除
// 的值的临时容器
remove_copy_if(c.begin(), c.end(), // 从c拷贝不删除
inserter(goodValues, // 的值到
goodValues.end()), // goodValues
badValue);
c.swap(goodValues); // 交换c和goodValues

haoji

// 的内容
对这种方法的缺点是它拷贝了所有不删除的元素，而这样的拷贝开销可能大于我们感兴趣支付的。
我们可以通过直接从原容器删除元素来避开那笔帐单。不过，因为关联容器没有提供类似remove_if的成员函
数，所以我们必须写一个循环来迭代c中的元素，和原来一样删除元素。
看起来，这个任务很简单，而且实际上，代码也很简单。不幸的是，那些正确工作的代码很少是跃出脑海的
代码。例如，这是很多程序员首先想到的：
AssocContainer<int> c;
...
for (AssocContainer<int>::iterator i = c.begin(); // 清晰，直截了当
i!= c.end(); // 而漏洞百出的用于
++i) { // 删除c中badValue返回真
if (badValue(*i)) c.erase(i); // 的每个元素的代码
} // 不要这么做！
唉，这有未定义的行为。当容器的一个元素被删时，指向那个元素的所有迭代器都失效了。当c.erase(i)返回
时，i已经失效。那对于这个循环是个坏消息，因为在erase返回后，i通过for循环的++i部分自增。
为了避免这个问题，我们必须保证在调用erase之前就得到了c中下一元素的迭代器。最容易的方法是当我们调
用时在i上使用后置递增：
AssocContainer<int> c;
...
for (AssocContainer<int>::iterator i = c.begin(); // for循环的第三部分
i != c.end(); // 是空的；i现在在下面
/*nothing*/ ){ // 自增
if (badValue(*i)) c.erase(i++); // 对于坏的值，把当前的
else ++i; // i传给erase，然后
} // 作为副作用增加i；
// 对于好的值，
// 只增加i
这种调用erase的解决方法可以工作，因为表达式i++的值是i的旧值，但作为副作用，i增加了。因此，我们把i
的旧值（没增加的）传给erase，但在erase开始执行前i已经自增了。那正好是我们想要的。正如我所说的，代

haoji

码很简单，只不过不是大多数程序员在第一次尝试时想到的。
现在让我们进一步修改该问题。不仅删除badValue返回真的每个元素，而且每当一个元素被删掉时，我们也
想把一条消息写到日志文件中。
对于关联容器，这说多容易就有多容易，因为只需要对我们刚才开发的循环做一个微不足道的修改就行了：
ofstream logFile; // 要写入的日志文件
AssocContainer<int> c;
...
for (AssocContainer<int>::iterator i = c.begin(); // 循环条件和前面一样
i !=c.end(){
if (badValue(*i)){
logFile << "Erasing " << *i <<'\n'; // 写日志文件
c.erase(i++); // 删除元素
}
else ++i;
}
现在是vector、string和deque给我们带来麻烦。我们不能再使用erase-remove惯用法，因为没有办法让erase或
remove写日志文件。而且，我们不能使用刚刚为关联容器开发的循环，因为它为vector、string和deque产生未
定义的行为！要记得对于那样的容器，调用erase不仅使所有指向被删元素的迭代器失效，也使被删元素之后
的所有迭代器失效。在我们的情况里，那包括所有i之后的迭代器。我们写i++，++i或你能想起的其它任何东
西都没有用，因为没有能导致迭代器有效的。
我们必须对vector、string和deque采用不同的战略。特别是，我们必须利用erase的返回值。那个返回值正是我
们需要的：一旦删除完成，它就是指向紧接在被删元素之后的元素的有效迭代器。换句话说，我们这么写：
for (SeqContainer<int>::iterator i = c.begin();
i != c.end(){
if (badValue(*i)){
logFile << "Erasing " << *i << '\n';
i = c.erase(i); // 通过把erase的返回值
} // 赋给i来保持i有效
else
++i;
}

haoji

这可以很好地工作，但只用于标准序列容器。由于论证一个可能的问题（条款5做了），标准关联容器的erase
的返回类型是void[1]。对于那些容器，你必须使用“后置递增你要传给erase的迭代器”技术。（顺便说说，
在为序列容器编码和为关联容器编码之间的这种差别是为什么写容器无关代码一般缺乏考虑的一个例子——
参见条款2。)
为了避免你奇怪list的适当方法是什么，事实表明对于迭代和删除，你可以像vector/string/deque一样或像关联
容器一样对待list；两种方法都可以为list工作。
如果我们观察在本条款中提到的所有东西，我们得出下列结论：
● 去除一个容器中有特定值的所有对象：
如果容器是vector、string或deque，使用erase-remove惯用法。
如果容器是list，使用list::remove。
如果容器是标准关联容器，使用它的erase成员函数。
● 去除一个容器中满足一个特定判定式的所有对象：
如果容器是vector、string或deque，使用erase-remove_if惯用法。
如果容器是list，使用list::remove_if。
如果容器是标准关联容器，使用remove_copy_if和swap，或写一个循环来遍历容器元素，当你把迭代
器传给erase时记得后置递增它。
● 在循环内做某些事情（除了删除对象之外）：
如果容器是标准序列容器，写一个循环来遍历容器元素，每当调用erase时记得都用它的返回值更新你
的迭代器。
如果容器是标准关联容器，写一个循环来遍历容器元素，当你把迭代器传给erase时记得后置递增它。
如你所见，与仅仅调用erase相比，有效地删除容器元素有更多的东西。解决问题的最好方法取决于你是怎样
鉴别出哪个对象是要被去掉的，储存它们的容器的类型，和当你删除它们的时候你还想要做什么（如果有的
话）。只要你小心而且注意了本条款的建议，你将毫不费力。如果你不小心，你将冒着产生不必要低效的代
码或未定义行为的危险。

haoji

[1] 这仅对带有迭代器实参的erase形式是正确的。关联容器也提供一个带有一个值的实参的erase形式，而那种
形式返回被删掉的元素个数。但这里，我们只关心通过迭代器删除东西。

haoji

Center of STL Study
——最优秀的STL学习网站
条款10：注意分配器的协定和约束
分配器是怪异的。它们最初是为抽象内存模型而开发的，允许库开发者忽略在某些16位操作系统上near和far
指针的区别（即，DOS和它的有害产物），但努力失败了。分配器也被设计成促进全功能内存管理器的发
展，但事实表明那种方法在STL的一些部分会导致效率损失。为了避免效率冲击，C++标准委员会向标准中
添加了词语，把分配器弱化为对象，同时也表达了他们不会让操作损失能力的希望。
还有更多。正如operator new和operator new[]，STL分配器负责分配（和回收）原始内存，但分配器的客户接
口与operator new、operator new[]甚至malloc几乎没有相似之处。最后（而且可能非常惊人），大多数标准容
器从未向它们相关的分配器索要内存。从没有。结果分配器是，嗯，分配器是怪异的。
当然，那不是它们的错，而且无论如何，这不意味着它们没用。但是，在我解释分配器好在哪里之前（那是
条款11的主题），我需要解释它们哪里不好。有许多事情分配器好像能做，但不能，而且在你试图开始使用
之前，知道领域的边界很重要。如果不，你将肯定会受伤。此外，关于分配器的事实如此独特，总结它的行
为既有启发性又有趣。至少我希望是。
分配器的约束的列表从用于指针和引用的残留typedef开始。正如我提到的，分配器最初被设想为抽象内存模
型，在那种情况下，分配器在它们定义的内存模型中提供指针和引用的typedef才有意义。在C++标准里，类
型T的对象的默认分配器（巧妙地称为allocator<T>）提供typedef allocator<T>::pointer和allocator<T>::
reference，而且也希望用户定义的分配器也提供这些typedef。
C++老手立即发现这有问题，因为在C++里没有办法捏造引用。这样做要求有能力重载operator.（“点操作
符”），而那是不允许的。另外，建立行为像引用的对象是使用代理对象的例子，而代理对象会导致很多问
题。（一个这样的问题产生了条款18。对代理对象的综合讨论，转向《More Effective C++》的条款30，你能
知道什么时候它们工作什么时候不。)
就STL里的分配器而言，没有任何代理对象的技术缺点会导致指针和引用typedef失效，实际上标准明确地允
许库实现假设每个分配器的pointer typedef是T*的同义词，每个分配器的reference typedef与T&相同。对，库实
现可以忽视typedef并直接使用原始指针和引用！所以即使你可以设法写出成功地提供新指针和引用类型的分
配器的方法，也好不到哪里去，因为你使用的STL实现将自由地忽视你的typedef。很优雅，不是吗？
当你钦佩标准化的怪癖时，我将再介绍一个。分配器是对象，那表明它们可能有成员功能，内嵌的类型和
typedef（例如pointer和reference）等等，但标准允许STL实现认为所有相同类型的分配器对象都是等价的而且
比较起来总是相等。很唐突，听起来并不可怕，而且对它当然有好的动机。考虑这段代码：

haoji

template<typename T> // 一个用户定义的分配器
class SpecialAllocator {...}; // 模板
typedef SpecialAllocator<Widget> SAW; // SAW = “SpecialAllocator
// for Widgets”
list<Widget, SAW> L1;
list<Widget, SAW> L2;
...
L1.splice(L1.begin(), L2); // 把L2的节点移到
// L1前端
记住当list元素从一个list被接合到另一个时，没有拷贝什么。取而代之的是，调整了一些指针，曾经在一个list
中的节点发现他们自己现在在另一个list中。这使接合操作既迅速又异常安全。在上面的例子里，接合前在L2
里的节点接合后出现在L1中。
当L1被销毁时，当然，它必须销毁它的所有节点（以及回收它们的内存），而因为它现在包含最初是L2一部
分的节点，L1的分配器必须回收最初由L2的分配器分配的节点。现在清楚为什么标准允许STL实现认为相同
类型的分配器等价。所以由一个分配器对象（比如L2）分配的内存可以安全地被另一个分配器对象（比如
L1）回收。如果没有这样的认为，接合操作将更难实现。显然它们不能像现在一样高效。（接合操作的存在
也影响了STL的其他部分。另一个例子参见条款4。）
那当然好，但你想得越多，越会意识到STL实现可以认为相同类型的分配器等价是多严厉的约束。那意味着
可移植的分配器对象——在不同的STL实现下都功能正确的分配器——不能有状态。让我们明确这一点：它
意味着可移植的分配器不能有任何非静态数据成员，至少没有会影响它们行为的。一个都没有。没有。那表
示，例如，你不能有从一个堆分配的SpecialAllocator<int>和从另一个堆分配的另一个SpecialAllocator<int>。这
样的分配器不等价，而试图使用那两个分配器的现存STL实现可能导致错误的运行期数据结构。
注意这是一个运行期问题。有状态的分配器可以很好地编译。它们只是不按你期待的方式运行。确保一个给
定类型的所有分配器都等价是你的责任。如果你违反这个限制，不要期待编译器发出警告。
为了对标准委员会公平，我应该指出，在“允许STL实现认为相同类型的分配器等价”的文字之后，紧接着
有下列陈述：
鼓励实现提供...支持非相等实例的库。在那样的实现中，...当分配器实例非相等时，容器和算
法的语义是由实现定义的。
这是个可爱的句子，但是作为一个考虑开发带状态自定义分配器的STL用户，它几乎没向你提供什么。你可
以利用这句话除非（1）你知道你使用的STL实现支持不等价的分配器，（2）你愿意钻研它们的文档来确定