16.7 拷贝
在16.2节中,我们认为f?ind()是“最简单的有用算法”。当然,这一点可以讨论。很多简单算法都是有用的——甚至其中有些编写起来有些过于简单了。当你可以使用其他人编写和调试好的代码时,为什么要费力编写新的代码?当谈及简单性和有效性时,copy()可以与f?ind()媲美。STL提供了三个版本的拷贝:
拷贝操作
copy(b,e,b2) 将[b:e)拷贝到[b2:b2+(e-b))
unique_copy(b,e,b2) 将[b:e)拷贝到[b2:b2+(e-b)),禁止拷贝相邻的相同元素
copy_if(b,e,b2,p) 将[b:e)拷贝到[b2:b2+(e-b)),但是仅拷贝满足谓词p的元素
16.7.1 基本拷贝算法
基本拷贝算法的定义如下:
给定一对迭代器,copy()将一个序列拷贝到另一个序列,目的序列用一个迭代器指明首元素。例如:
注意,copy()的输入序列类型可以与输出序列类型不同。这是STL算法的一种有用泛化:它们可用于各种序列,而无须对其实现做不必要的假设。我们要记得检查在输出序列中是否有足够的空间以保存拷贝来的元素。检查空间的大小是程序员的责任。STL算法的设计目标是最大的通用性和最佳的性能,它们(默认)没有做范围检查和其他代价昂贵的测试来保护用户。有时候,你可能希望它们做这些检查,但是当你想进行检查时,你可以像上面代码那样自己来完成。
16.7.2 流迭代器
你可能听到过短语“拷贝到输出”和“从输入拷贝”。这种思考方式对某种形式的I/O来说是很好、很有用的,我们确实可以用copy()做这些事情。
记住,一个序列是这样的东西:
它有开始和结尾;
我们可以用++移动到下一个元素;
我们可以用*得到当前元素的值。
我们可以很容易地用这种方式表示输入和输出流。例如:
你可以想象如何来实现它。标准库提供了一个ostream_iterator类型,就可以这样工作;ostream_iterator<T>是一个迭代器,你可以用它写入类型为T的值。
类似地,标准库提供了istream_iterator<T>类型用于读取类型为T的值:
通过ostream_iterator和istream_iterator,我们可以对自己的I/O使用copy()。例如,我们可以实现一个“快速和混乱的”字典,如下所示:
迭代器eos是表示“输入结束”的流迭代器。当一个istream到达输入结束(经常被表示为eof),它的istream_iterator将等于默认的istream_iterator(这里称为eos)。
注意,我们使用一对迭代器来初始化vector。作为一个容器的初始化器,一对迭代器(a, b)表示“将序列[a:b)读取到容器”。自然地,我们使用的一对迭代器是(ii,eos)——输入的开始与结束。这令我们不必使用>>和push_back()。我们强烈建议不要使用下面的替代方案。
那些试图猜测输入的最大规模的人,通常会发现他们低估了输入规模,从而遇到严重的问题——缓冲区溢出,无论对于他们自己还是他们的用户都是很严重的问题。这种溢出也是安全问题的一个来源。
试一试
首先,编译上面的程序令其正确运行,用一个小文件来测试它,例如一个包含几百个单词的文件。然后,尝试我们着重强调不推荐的猜测输入规模的版本,观察当输入缓冲区b溢出时发生什么。注意,最坏的情况是在特定例子中溢出没有导致任何错误,这样你就可能试图将它交付给用户。
在这个小程序中,我们读取单词然后进行排序。这在当时看来是一个明显的解决方案,但是我们为什么要将单词放在“错误的位置”,以至于随后我们不得不进行排序?更糟糕的是,我们发现一个单词在输入中出现几次,我们就会保存和打印它几次。
我们可以用unique_copy()代替copy()来解决后一个问题。unique_copy()不会重复拷贝相同的值。例如,如果使用普通的copy(),输入
the man bit the dog
程序会生成
如果我们使用unique_copy(),程序将会输出
这些换行是从哪里来的?带有分隔符的输出是很常见的,ostream_iterator的构造函数允许你(可选的)指定在每个值之后打印一个字符串:
很明显,对于供人类阅读的输出来说,换行分隔符是很常见的选择,但是也许我们喜欢使用空格作为分隔符呢?可以编写代码如下:
这将会生成输出
16.7.3 使用set保持顺序
有一个更容易的方式来得到上面那样的输出,使用set而不是vector:
当我们将值插入一个set时,重复的值被忽略掉。而且,set中的元素是按顺序保存的,因此不需要进行排序。通过使用正确的工具,大多数任务很容易完成。
16.7.4 copy_if
copy()算法进行无条件拷贝。unique_copy()算法禁止拷贝相同的相邻元素。第三种拷贝算法只拷贝令谓词为真的元素:
使用16.4节中的Larger_than函数对象,我们可以找到一个序列中大于6的所有元素,如下所示:
由于我犯的一个错误,这个算法错失进入1998 ISO标准的机会。这个错误现在已经被补救了,但是你仍然可以找到没有copy_if的C++实现。如果是这样,请使用本节中的定义。