《Effective STL》

haoji

这里我用问号来标明那些在概念上已经从v中被删除，但继续存在的元素的值。
如果“不删除的”元素在v中的v.begin()和newEnd之间，“删除的”元素就必须在newEnd和v.end()之间——这
好像很合理。事实上不是这样！“删除的”值完全不必再存在于v中了。remove并没有改变区间中元素的顺
序，所以不会把所有“删除的”元素放在结尾，并安排所有“不删除的”值在开头。虽然标准没有要求，但
一般来说区间中在新逻辑终点以后的元素仍保持它们的原值。调用完remove后，在我知道的所有实现中，v
看起来像这样：
正如你所见，两个曾经存在于v的“99”不再在那儿了，而一个“99”仍然存在。一般来说，调用完remove
后，从区间中删除的值可能是也可能不在区间中继续存在。大多数人觉得这很奇怪，但为什么？你要求
remove除去一些值，所以它做了。你并没有要求它把删除的值放在一个你以后可以获取的特定位置，所以它
没有做。有问题吗？（如果你不想失去任何值，你可能应该调用partition或stable_partition而不是remove，
partition在条款31中描述。）
remove的行为听起来很可恶，但它只不过是算法操作的附带结果。在内部，remove遍历这个区间，把要“删
除的”值覆盖为后面要保留的值。这个覆盖通过对持有被覆盖的值的元素赋值来完成。
你可以想象remove完成了一种压缩，被删除的值表演了在压缩中被填充的洞的角色。对于我们的vector v，它
按照下面的表演：
1. remove检测v[0]，发现它的值不是要被删除的，然后移动到v[1]。同样的情况发生在v[1]和v[2]。
2. 发现v[3]应该被删除，所以它记录下v[3]的值应该被覆盖，然后它移动到v[4]。这类似记录v[3]是一个

haoji

需要填充的“洞”。
3. 发现v[4]的值应该被保持，所以它把v[4]赋给v[3]，记录下v[4]应该被覆盖，然后移动到v[5]。继续类
似的压缩，它用v[4]“填充”v[3]而且记录v[4]现在是一个洞。
4. 发现v[5]应该被删除，所以忽略并它移动到v[6]。仍然记得v[4]是一个等待填充的洞。
5. 发现v[6]是一个应该保留的值，所以把v[6]赋给v[4]。记得v[5]现在是下一个要被填充的洞，然后移到v
[7]。
6. 在某种意义上类似上面的，检查v[7]、v[8]和v[9]。把v[7]赋给v[5]，v[8]赋给v[6]，忽略v[9]，因为v[9]
的值是要被删除的。
7. 返回指定下一个要被覆盖的元素的迭代器，在这个例子中这个元素是v[7]。
你可以预想在v中值的移动情况像这样：
正如条款33所解释的，事实上当remove在删除时覆盖的值是指针时，会有重要的影响。但是对于本条款，知
道remove不从容器中除去任何元素因为它做不到就够了。只有容器成员函数可以除去容器元素，而那是本条
款的整个要点：如果你真的要删除东西的话，你应该在remove后面接上erase。
你要erase的元素很容易识别。它们是从区间的“新逻辑终点”开始持续到区间真的终点的原来区间的元素。
要除去那些元素，你要做的所有事情就是用那两个迭代器调用erase的区间形式（参见条款5）。因为remove本
身很方便地返回了区间新逻辑终点的迭代器，这个调用很直截了当：
vector<int> v; // 正如从前
v.erase(remove(v.begin(), v.end(), 99), v.end()); // 真的删除所有
// 等于99的元素
cout << v.size(); // 现在返回7
把remove的返回值作为erase区间形式第一个实参传递很常见，这是个惯用法。事实上，remove和erase是亲密
联盟，这两个整合到list成员函数remove中。这是STL中唯一名叫remove又能从容器中除去元素的函数：
list<int> li; // 建立一个list
// 放一些值进去

haoji

li.remove(99); // 除去所有等于99的元素：
// 真的删除元素，
// 所以它的大小可能改变了
坦白地说，调用这个remove函数是一个STL中的矛盾。在关联容器中类似的函数叫erase，list的remove也可以
叫做erase。但它没有，所以我们都必须习惯它。我们所处于的世界不是所有可能中最好的世界，但却是我们
所处的。（附加一点，条款44指出，对于list，调用remove成员函数比应用erase-remove惯用法更高效。）
一旦你知道了remove不能“真的”从一个容器中删除东西，和erase联合使用就变成理所当然了。你要记住的
唯一其他的东西是remove不是唯一这种情况的算法。另外有两种“类似remove”的算法：remove_if和
unique。
remove和remove_if之间的相似性很直截了当。所以我不会细讲，但unique行为也像remove。它用来从一个区
间删除东西（邻近的重复值）而不用访问持有区间元素的容器。结果，如果你真的要从容器中删除元素，你
也必须成对调用unique和erase，unique在list中也类似于remove。正像list::remove真的删除东西（而且比eraseremove
惯用法高效得多）。list::unique也真的删除邻近的重复值（也比erase-unique高效）。
（译注：《C++标准程序库》111页5.6节有remove的详细解释）

haoji

Center of STL Study
——最优秀的STL学习网站
条款33：提防在指针的容器上使用类似remove的算法
你在管理一堆动态分配的Widgets，每一个都可能通过检验，你把结果指针保存在一个vector中：
class Widget{
public:
...
bool isCertified() const; // 这个Widget是否通过检验
...
};
vector<Widget*> v; // 建立一个vector然后用
... // 动态分配的Widget
v.push_back(new Widget); // 的指针填充
当和v工作一段时间后，你决定除去未通过检验的Widget，因为你不再需要它们了。记住条款43的警告尽量用
算法调用代替显式循环和读过的条款32关于remove和erase之间关系的描述，你自然会想到转向erase-remove惯
用法，虽然这次你使用了remove_if：
v.erase(remove_if(v.begin(), v.end(), // 删除未通过检验的
not1(mem_fun(&Widget::isCertified))), // Widget指针
v.end()); // 关于mem_fun的信息
// 参见条款41
突然你开始担心erase的调用，因为你朦胧的记起条款7关于摧毁容器中的一个指针也不会删除指针指向的东西
的讨论。这是个合理的担心，但在这里，太晚了。当调用erase时，极可能你已经泄漏了资源。担心erase，是
的，但首先，担心一下remove_if。
我们假设在调用remove_if前，v看起来像这样，我已经指出了未通过检验的Widget：

haoji

在调用remove_if后，一般来说v看起来像这样（包含从remove_if返回的迭代器）：
如果你看不懂这个转换，请转向条款32，因为它准确地解释了调用remove——或者，在这个例子里，
remove_if——做了什么。
资源泄漏的理由现在很明朗了。指向Widget B和C的“删除的”指针被vector中后面的“不删除的”指针覆
盖。没有什么指向两个未通过检验的Widget，它们也没有被删除，它们的内存和其他资源泄漏了。
一旦remove_if和erase返回后，情况看起来像这样：

haoji

这造成资源泄漏尤其明显了，现在你也很清楚为什么应该努力避免在动态分配的指针的容器上使用remove和
类似算法（也就是，remove_if和unique）。在很多情况下，你会发现partition算法（参见条款31）是合理的替
代品。
如果你无法避免在那样的容器上使用remove，排除这个问题一种方法是在应用erase-remove惯用法之前先删除
指针并设置它们为空，然后除去容器中的所有空指针：
void delAndNullifyUncertified(Widget*& pWidget) // 如果*pWidget是一个
{ // 未通过检验Widget，
if (!pWidget->isCertified()) { // 删除指针
delete pWidget; // 并且设置它为空
pWidget = 0;
}
}
for_each(v.begin(), v.end(), // 把所有指向未通过检验Widget的
delAndNullifyUncertified); // 指针删除并且设置为空
v.erase(remove(v.begin(), v.end(), // 从v中除去空指针
static_cast<Widget*>(0)), // 0必须映射到一个指针，
v.end()); // 让C++可以
// 正确地推出remove的
// 第三个参数的类型
当然，这假设vector并不容纳任何你想保留的空指针。如果有的话，你可能必须自己写循环来按你的方式删
除指针。在你遍历容器时从容器中删除元素有一些细微的要注意的地方，在考虑那种方法之前确定已经读过
条款9。
如果你把指针的容器替换成执行引用计数的智能指针的容器，删除相关的困难就不存在了，你可以直接使用

haoji

erase-remove惯用法：
template<typename T> // RCSP = “引用计数
class RCSP { ...}; // 智能指针”
typedef RCSP< Widget> RCSPW; // RCSPW = “RCSP to Widget”
vector<RCSPW > v; // 建立一个vector，用动态
... // 分配Widget的
v.push_back(RCSPW(new Widget)); // 智能指针填充它
...
v.erase(remove_if(v.begin(), v.end(), // erase未通过检验的
not1 (mem_fun(&Widget::isCertified))), // Widget的指针
v.end()); // 没有资源泄漏
要让这些工作，你的智能指针类型就必须可以（比如RCSP<Widget>）隐式转换为相应的内建指针类型（比
如Widget*）。那是因为容器持有智能指针，但被调用的成员函数（比如Widget::isCertified）要的是内建指
针。如果不存在隐式转换，你的编译器会抗议的。
如果在你的程序工具箱中碰巧没有一个引用计数智能指针模板，你应该从Boost库中得到shared_ptr模板。关
于Boost的介绍，请看条款50。
不管你怎么选择处理动态分配指针的容器，通过引用计数智能指针、在调用类似remove的算法前手动删除和
废弃指针或者一些你自己发明的技术，本条款的指导意义依然一样：提防在指针的容器上使用类似remove的
算法。没有注意这个建议的人只能造成资源泄漏。

haoji

Center of STL Study
——最优秀的STL学习网站
条款34：注意哪个算法需要有序区间
不是所有算法可以用于任意区间。比如，remove（参见条款32和33）需要前向迭代器和可以通过这些迭代器
赋值的能力。所以，它不能应用于由输入迭代器划分的区间，也不能是map或multimap，也不能是set和
multiset的一些实现（参见条款22）。同样，很多排序算法（参见条款31）需要随机访问迭代器，所以不可能
在一个list的元素上调用这些算法。
如果你冒犯了这些规则，你的代码将不能编译，可能会出现一个非常冗长和不可理解的错误信息（参见条款
49）。但其他算法的需求则更为狡猾。在这些之中，可能最常见的就是一些算法需要有序值的区间。无论何
时都应该坚持这个需求，因为冒犯它不仅会导致编译器诊断，而且会造成未定义的运行期行为。
既可以和有序又可以和无序区间合作的算法很少，但当操作有序区间的时候它们最有用。你可以理解这些算
法是怎么工作的，因为那会解释为什么有序区间最适合它们。
我知道你们中的一部分会用蛮力记忆，所以这里有一个只能操作有序数据的算法的表：
binary_search lower_bound
upper_bound equal_range
set_union set_intersection
set_difference set_symmetric_difference
merge inplace_merge
includes
另外，下面的算法一般用于有序区间，虽然它们不要求：
unique unique_copy
我们马上会看到“有序”的定义是一个重要的约束，但首先，让我们熟悉一下这些算法。如果你知道了为什
么需要有序区间，就很容易记起哪个算法需要那样的区间。
搜索算法binary_search、lower_bound、upper_bound和equal_range（参见条款45）需要有序区间，因为它们使

haoji

用二分法查找来搜索值。像C库中的bsearch，这些算法保证了对数时间的查找，但作为交换的是，你必须给
它们已经排过序的值。
实际上，这些算法保证对数时间查找不是很正确。仅当传给它们的是随机访问迭代器时它们才能保证有那样
的性能。如果给它们威力比较小的迭代器（比如双向迭代器），它们仍然进行对数次比较，但运行是线性时
间的。那是因为，缺乏进行“迭代器算术（arithmetic）”的能力。它们在搜索的区间中需要花费线性时间来
从一个地方移动到另一个地方。
算法set_union、set_intersection、set_difference和set_symmetric_difference的四人组提供了线性时间设置它们名字
所提出的操作的性能。为什么它们需要有序区间？因为如果不是的话，它们不能以线性时间完成它们的工
作。如果你开始发觉一个趋势——需要有序区间的算法为了比它们用于可能无序区间提供更好的性能而这么
做，你是对的。保持协调，这个趋势会继续。
merge和inplace_merge执行了有效的单遍合并排序算法：它们读取两个有序区间，然后产生一个包含了两个源
区间所有元素的新有序区间。它们以线性时间执行，如果它们不知道源区间已经有序就不能完成。
最后一个需要有序区间的算法是includes。它用来检测是否一个区间的所有对象也在另一个区间中。因为
includes可能假设它的两个区间都已经有序，所以它保证了线性时间性能。没有那个保证，一般来说它会变
慢。
不像我们刚才讨论过的算法，unique和unique_copy甚至在无序区间上也提供了定义良好的行为。但看看标准
是怎么描述unique的行为的（斜体字是雷区）：
从每个相等元素的连续组中去除第一个以外所有的元素。
换句话说，如果你要unique从一个区间去除所有重复值（也就是，让区间中所有值“唯一”），你必须先确
保所有重复值一个接着一个。猜到什么了？那是排序完成的东西之一。实际上，unique一般用于从区间中去
除所有重复值，所以你几乎总是要确保你传递给unique（或unique_copy）的区间是有序的。（Unix开发者会
发现STL的unique和Unix的uniq之间有惊人的相似，我想这个相似决不是巧合。）
顺便说说，unique从一个区间除去元素的方式和remove一样，也就是说它只是区分出不除去的元素。如果你
不知道那是什么意思，请立刻转向条款32和33。强调理解remove和类似remove的算法（包括unique）行为的重
要性永远没有过分的时候。光有基本的理解还不够。如果你不知道它们做了什么，你会陷入困境。
这让我必须说说关于有序区间的意思的难懂的条文。因为STL允许你指定用于排序的比较函数，不同的区间
可能以不同的方式排序。比如，给定两个int的区间，一个可能以默认方式排序（也就是升序），而另一个使
用greater<int>排序，因此是降序。给定Widget的两个区间，一个可能以价格排序而另一个可能以年龄排序。
因为有很多不同的方式来排序，所以保证给STL所使用的排序相关信息一致是很重要的。如果你传一个区间
给一个也带有比较函数的算法，确保你传递的比较函数行为和你用于排序这个区间的一样。

haoji

这里有一个你并不想那么做的例子：
vector<int> v; // 建立一个vector，
... // 把一些数据放进去
sort(v.begin(), v.end(), greater<int>()); // 降序排列
... // 使用这个vector
// （没有改变它）
bool a5Exists = // 在这个vector中搜索5
binary_search(v.begin(), v.end(), 5); // 假设它是升序排列！
默认情况下，binary_search假设它搜索的区间是以“<”排序（也就是，值是升序），但在本例中，这个
vector是降序。当你在值的排列顺序和算法所期望的不同的区间上调用binary_search (或lower_bound等）会导
致未定义的结果时，你不该惊奇。
要让代码行为正确，你必须告诉binary_search要使用和sort同样的比较函数：
bool a5Exists = // 搜索5
binary_search(v.begin(), v.end(), 5. greater<int>()); // 把greater作为
// 比较函数
所有需要有序区间的算法（也就是除了unique和unique_copy外本条款的所有算法）通过等价来判断两个值是
否“相同”，就像标准关联容器（它们本身是有序的）。相反，unique和unique_copy判断两个对象“相
同”的默认方式是通过相等，但是你可以通过传给这些算法一个定义了“相同”的意义的判断式来覆盖这个
默认情况。等价和相等之间区别的详细讨论，参考条款19。
11个需要有序区间的算法为了比其他可能性提供更好的性能而这么做。只要你记住只传给它们有序区间，只
要你保证用于算法的比较函数和用于排序的一致，你就会酷爱没有麻烦的查找、设置和合并操作，加上你会
发现unique和unique_copy除去了所有的重复值，正如你要它们完成的一样。