第十一章 泛型算法 标准库容器定义的操作非常少。标准库没有给容器添加大量的功能函数,而是选择提供一组算法,这些算法大都不依赖特定的容器类型,是“泛型”的,可作用在不同类型的容器和不同类型的元素上。 考虑下面的例子,可以使用 accumulate 把 string 型的 vector 容器中的元素连接起来: // concatenate elements from v and store in sum string sum = accumulate(v.begin(), v.end(), string("")); 这个函数调用的效果是:从空字符串开始,把 vec 里的每个元素连接成一个字符串。注意:程序显式地创建了一个 string 对象,用该函数调用的第三个实参。传递一个字符串字面值,将会导致编译时错误。因为此时,累加和的类型将是 const char*,而 string 的加法操作符(第 3.2.3 节)所使用的操作数则分别是 string 和 const char* 类型,加法的结果将产生一个 string 对象,而不是 const char* 指针。 对指定数目的元素做写入运算,或者写到目标迭代器的算法,都不检查目标的大小是否足以存储要写入的元素。 copy 带有三个迭代器参数:头两个指定输入范围,第三个则指向目标序列的一个元素。传递给 copy 的目标序列必须至少要与输入范围一样大。假设 ilst 是一个存放 int 型数据的 list 对象,可如下将它 copy 给一个 vector 对象: vector<int> ivec; // empty vector // copy elements from ilst into ivec copy (ilst.begin(), ilst.end(), back_inserter(ivec)); replace 算法就是一个很好的例子。该算法对输入序列做读写操作,将序列中特定的值替换为新的值。该算法带有四个形参:一对指定输入范围的迭代器和两个值。每一个等于第一值的元素替换成第二个值。 // replace any element with value of 0 by 42 replace(ilst.begin(), ilst.end(), 0, 42); 这个调用将所有值为 0 的实例替换成 42。如果不想改变原来的序列,则调用 replace_copy。这个算法接受第三个迭代器实参,指定保存调整后序列的目标位置。 // create empty vector to hold the replacement vector<int> ivec; // use back_inserter to grow destination as needed replace_copy (ilst.begin(), ilst.end(), back_inserter(ivec), 0, 42); 假设我们的输入存储在一个名为 words 的 vector 对象中,第一个子问题是将 words 中重复出现的单词去除掉: // sort words alphabetically so we can find the duplicates sort(words.begin(), words.end()); /* eliminate duplicate words: * unique reorders words so that each word appears once in the * front portion of words and returns an iterator one past the unique range; * erase uses a vector operation to remove the nonunique elements */ vector<string>::iterator end_unique = unique(words.begin(), words.end()); words.erase(end_unique, words.end()); 单词按次序排列后,现在的问题是:让故事中所用到的每个单词都只保留一个副本。unique 算法很适合用于解决这个问题,它带有两个指定元素范围的迭代器参数。该算法删除相邻的重复元素,然后重新排列输入范围内的元素,并且返回一个迭代器,表示无重复的值范围的结束。 After the call to unique, the vector holds 调用 unique 后,vector 中存储内容是: 注意,words 的大小并没有改变,依然保存着 10 个元素;只是这些元素的顺序改变了。调用 unique“删除”了相邻的重复值。给“删除”加上引号是因为 unique 实际上并没有删除任何元素,而是将无重复的元素复制到序列的前端,从而覆盖相邻的重复元素。unique 返回的迭代器指向超出无重复的元素范围末端的下一位置。 现在此 vector 对象已经按单词长度排序,剩下的问题就是统计长度不小于 6 的单词个数。使用 count_if 算法处理这个问题: vector<string>::size_type wc = count_if(words.begin(), words.end(), GT6); bool GT6(const string &s) { return s.size() >= 6; } 尽管这个函数能解决问题,但存在不必要限制——函数内部硬性规定了对长度大小的要求。如果要统计其他长度的单词个数,则必须编写另一个函数。其实很容易写出更通用的比较函数,使它带有两个形参,分别是 string 对象和一个长度大小值即可。但是,传递给 count_if 算法的函数只能带有一个实参,因此本程序不能使用上述更通用的方法。第 14.8.1 节将为这个问题提供更好的解决方案。 了解程序的细节之后,下面是完整的程序: // comparison function to be used to sort by word length bool isShorter(const string &s1, const string &s2) { return s1.size() < s2.size(); } // determine whether a length of a given word is 6 or more bool GT6(const string &s) { return s.size() >= 6; } int main() { vector<string> words; // copy contents of each book into a single vector string next_word; while (cin >> next_word) { // insert next book's contents at end of words words.push_back(next_word); } // sort words alphabetically so we can find the duplicates sort (words.begin(), words.end()); /* eliminate duplicate words: * unique reorders words so that each word appears once in the * front portion of words and returns an iterator one past the unique range; * erase uses a vector operation to remove the nonunique elements */ vector<string>::iterator end_unique = unique(words.begin(), words.end()); words.erase(end_unique, words.end()); // sort words by size, but maintain alphabetic order for words of the same size stable_sort(words.begin(), words.end(), isShorter); vector<string>::size_type wc = count_if (words.begin(), words.end(), GT6); cout << wc << " " << make_plural(wc, "word", "s") << " 6 characters or longer" << endl; return 0; }
反向迭代器:这类迭代器实现向后遍历,而不是向前遍历。所有容器类型都定义了自己的 reverse_iterator 类型,由 rbegin 和 rend 成员函数返回。 第 11.2.2 节已强调标准库所定义的迭代器不依赖于特定的容器。事实上,C++ 语言还提供了另外三种迭代器: 插入迭代器:这类迭代器与容器绑定在一起,实现在容器中插入元素的功能。 iostream 迭代器:这类迭代器可与输入或输出流绑定在一起,用于迭代遍历所关联的 IO 流。 反向迭代器:这类迭代器实现向后遍历,而不是向前遍历。所有容器类型都定义了自己的 reverse_iterator 类型,由 rbegin 和 rend 成员函数返回。 上述迭代器类型都在 iterator 头文件中定义。
上述迭代器类型都在 iterator 头文件中定义。 inserter 适配器提供更普通的插入形式。这种适配器带有两个实参:所关联的容器和指示起始插入位置的迭代器。 // position an iterator into ilst list<int>::iterator it = find (ilst.begin(), ilst.end(), 42); // insert replaced copies of ivec at that point in ilst replace_copy (ivec.begin(), ivec.end(), inserter (ilst, it), 100, 0); 首先用 find 定位 ilst 中的某个元素。使用 inserter 作为实参调用 replace_copy,inserter 将会在 ilst 中由 find 返回的迭代器所指向的元素前面插入新元素。而调用 replace_copy 的效果是从 ivec 中复制元素,并将其中值为 100 的元素替换为 0 值。ilst 的新元素在 it 所标明的元素前面插入。 也许我们会认为可使用 inserter 和容器的 begin 迭代器来模拟 front_inserter 的效果。然而,inserter 的行为与 front_inserter 的有很大差别。在使用 front_inserter 时,元素始终在容器的第一个元素前面插入。而使用 inserter 时,元素则在指定位置前面插入。即使此指定位置初始化为容器中的第一个元素,但是,一旦在该位置前插入一个新元素后,插入位置就不再是容器的首元素了: list<int> ilst, ilst2, ilst3; // empty lists // after this loop ilst contains: 3 2 1 0 for (list<int>::size_type i = 0; i != 4; ++i) ilst.push_front(i); // after copy ilst2 contains: 0 1 2 3 copy (ilst.begin(), ilst.end(), front_inserter(ilst2)); // after copy, ilst3 contains: 3 2 1 0 copy (ilst.begin(), ilst.end(), inserter (ilst3, ilst3.begin())); 在复制并创建 ilst2 的过程中,元素总是在这个 list 对象的所有元素之前插入。而在复制创建 ilst3 的过程中,元素则在 ilst3 中的固定位置插入。刚开始时,这个插入位置是此 list 对象的头部,但插入一个元素后,就不再是首元素了。
流迭代器只定义了最基本的迭代器操作:自增、解引用和赋值。此外,可比较两个 istream 迭代器是否相等(或不等)。而 ostream 迭代器则不提供比较运算(表 11.2)。 Table 11.2. istream_iterator Operations 表 11.2. istream_iterator 的操作
流迭代器的定义 流迭代器都是类模板:任何已定义输入操作符(>> 操作符)的类型都可以定义 istream_iterator。类似地,任何已定义输出操作符(<< 操作符)的类型也可定义 ostream_iterator。 在创建流迭代器时,必须指定迭代器所读写的对象类型: istream_iterator<int> cin_it(cin); // reads ints1 from cin istream_iterator<int> end_of_stream; // end iterator value // writes Sales_items from the ofstream named outfile // each element is followed by a space ofstream outfile; ostream_iterator<Sales_item> output(outfile, " "); ostream_iterator 对象必须与特定的流绑定在一起。在创建 istream_iterator 时,可直接将它绑定到一个流上。另一种方法是在创建时不提供实参,则该迭代器指向超出末端位置。ostream_iterator 不提供超出末端迭代器。 在创建 ostream_iterator 对象时,可提供第二个(可选的)实参,指定将元素写入输出流时使用的分隔符。分隔符必须是 C 风格字符串。因为它是 C 风格字符串,所以必须以空字符结束;否则,其行为将是未定义的。 istream_iterator 对象上的操作 构造与流绑定在一起的 istream_iterator 对象时将对迭代器定位,以便第一次对该迭代器进行解引用时即可从流中读取第一个值。 考虑下面例子,可使用 istream_iterator 对象将标准输入读到 vector 对象中。 istream_iterator<int> in_iter(cin); // read ints from cin istream_iterator<int> eof; // istream "end" iterator // read until end of file, storing what was read in vec while (in_iter != eof) // increment advances the stream to the next value // dereference reads next value from the istream vec.push_back(*in_iter++); 更有趣的是可以这样重写程序: istream_iterator<int> in_iter(cin); // read ints from cin istream_iterator<int> eof; // istream "end" iterator vector<int> vec(in_iter, eof); // construct vec from an iterator range 这里,用一对标记元素范围的迭代器构造 vec 对象。这些迭代器是 istream_iterator 对象,这就意味着这段范围的元素是通过读取所关联的流来获得的。这个构造函数的效果是读 cin,直到到达文件结束或输入的不是 int 型数值为止。读取的元素将用于构造 vec 对象。 ostream_iterator 对象和 ostream_iterator 对象的使用 可使用 ostream_iterator 对象将一个值序列写入流中,其操作的过程与使用迭代器将一组值逐个赋给容器中的元素相同: // write one string per line to the standard output ostream_iterator<string> out_iter(cout, "\n"); // read strings from standard input and the end iterator istream_iterator<string> in_iter(cin), eof; // read until eof and write what was read to the standard output while (in_iter != eof) // write value of in_iter to standard output // and then increment the iterator to get the next value from cin *out_iter++ = *in_iter++; 首先,定义一个 ostream_iterator 对象,用于将 string 类型的数据写到 cout 中,每个 string 对象后跟一个换行符。定义两个 istream_iterator 对象,用于从 cin 中读取 string 对象。while 循环类似前一个例子。但是这一次不是将读取的数据存储在 vector 对象中,而是将读取的数据赋给 out_iter,从而输出到 cout 上。 在类类型上使用 istream_iterator 提供了输入操作符(>>)的任何类型都可以创建 istream_iterator 对象。例如,可如下使用 istream_iterator 对象读取一系列的 Sales_iter 对象,并求和: istream_iterator<Sales_item> item_iter(cin), eof; Sales_item sum; // initially empty Sales_item sum = *item_iter++; // read first transaction into sum and get next record while (item_iter != eof) { if (item_iter->same_isbn(sum)) sum = sum + *item_iter; else { cout << sum << endl; sum = *item_iter; } ++item_iter; // read next transaction } cout << sum << endl; // remember to print last set of records 流迭代器的限制 流迭代器有下面几个重要的限制: 不可能从 ostream_iterator 对象读入,也不可能写到 istream_iterator 对象中。 一旦给 ostream_iterator 对象赋了一个值,写入就提交了。赋值后,没有办法再改变这个值。此外,ostream_iterator 对象中每个不同的值都只能正好输出一次。 ostream_iterator 没有 -> 操作符。 正如大家所知,算法是基于迭代器操作实现的。如同前面所述,流迭代器至少定义了一些迭代器操作。由于流迭代器操作,因此,至少可在一些泛型算法上使用这类迭代器。考虑下面的例子,从标准输入读取一些数,再将读取的不重复的数写到标准输出: istream_iterator<int> cin_it(cin); // reads ints from cin istream_iterator<int> end_of_stream; // end iterator value // initialize vec from the standard input: vector<int> vec(cin_it, end_of_stream); sort(vec.begin(), vec.end()); // writes ints to cout using " " as the delimiter ostream_iterator<int> output(cout, " "); // write only the unique elements in vec to the standard output unique_copy(vec.begin(), vec.end(), output); 如果程序的输入是: 23 109 45 89 6 34 12 90 34 23 56 23 8 89 23 输出则是: 6 8 12 23 34 45 56 89 90 109 假设有一个 vector 容器对象,存储 0-9 这 10 个以升序排列的数字: vector<int> vec; for (vector<int>::size_type i = 0; i != 10; ++i) vec.push_back(i); // elements are 0,1,2,...9 下面的 for 循环将以逆序输出这些元素: // reverse iterator of vector from back to front vector<int>::reverse_iterator r_iter; for (r_iter = vec.rbegin(); // binds r_iter to last element r_iter != vec.rend(); // rend refers 1 before 1st element ++r_iter) // decrements iterator one element cout << *r_iter << endl; // prints 9,8,7,...0 虽然颠倒自增和自减这两个操作符的意义似乎容易使人迷惑,但是它让程序员可以透明地向前或向后处理容器。例如,为了以降序排列 vector,只需向 sort 传递一对反向迭代器: // sorts vec in "normal" order sort(vec.begin(), vec.end()); // sorts in reverse: puts smallest element at the end of vec sort(vec.rbegin(), vec.rend()); 反向迭代器需要使用自减操作符 从一个既支持 -- 也支持 ++ 的迭代器就可以定义反向迭代器,这不用感到吃惊。毕竟,反向迭代器的目的是移动迭代器反向遍历序列。标准容器上的迭代器既支持自增运算,也支持自减运算。但是,流迭代器却不然,由于不能反向遍历流,因此流迭代器不能创建反向迭代器。 如果要输出列表中最后一个单词,可使用反向迭代器: // find last element in a comma-separated list string::reverse_iterator rcomma = find(line.rbegin(), line.rend(), ','); 因为此时传递的是 rbegin() 和 rend(),这个函数调用从 line 的最后一个字符开始往回搜索。当 find 完成时,如果列表中有逗号,那么 rcomma 指向其最后一个逗号,即指向反向搜索找到的第一个逗号。如果没有逗号,则 rcomma 的值为 line.rend()。 在尝试输出所找到的单词时,有趣的事情发生了。直接尝试: // wrong: will generate the word in reverse order cout << string(line.rbegin(), rcomma) << endl; 会产生假的输出。例如,如果输入是: FIRST,MIDDLE,LAST then this statement would print TSAL! 则将输出 TSAL! 图 11.2 阐明了这个问题:使用反向迭代器时,以逆序从后向前处理 string 对象。为了得到正确的输出,必须将反向迭代器 line.rbegin() 和 rcomma 转换为从前向后移动的普通迭代器。其实没必要转换 line.rbegin(),因为我们知道转换的结果必定是 line.end()。只需调用所有反向迭代器类型都提供的成员函数 base 转换 rcomma 即可 图 11.2 显示的对象直观地解释了普通迭代器与反向迭代器之间的关系。例如,正如 line_rbegin() 和 line.end() 一样,rcomma 和 rcomma.base() 也指向不同的元素。为了确保正向和反向处理元素的范围相同,这些区别必要的。从技术上来说,设计普通迭代器与反向迭代器之间的关系是为了适应左闭合范围(第 9.2.1 节)这个性质的,所以,[line.rbegin(), rcomma) 和 [rcomma.base(), line.end()) 标记的是 line 中的相同元素。 反向迭代器用于表示范围,而所表示的范围是不对称的,这个事实可推导出一个重要的结论:使用普通的迭代器对反向迭代器进行初始化或赋值时,所得到的迭代器并不是指向原迭代器所指向的元素。 11.3.4. const 迭代器 细心的读者可能已经注意到,在第 11.1 节使用 find 的程序中,我们将 result 定义为 const_iterator 类型。这样做是因为我们不希望使用这个迭代器来修改容器中的元素。 另一方面,虽然第 11.2.1 节的程序也不打算改变容器内的任何元素,但是它却使用了普通的非 const 迭代器来保存 find_first_of 的返回值。这两种处理存在细微的差别,值得解释一下。 原因是,在第二个例子中,程序将迭代器用作 find_first_of 的实参: find_first_of(it, roster1.end(), roster2.begin(), roster2.end());
该函数调用的输入范围由 it 和调用 roster1.end() 返回的迭代器指定。算法要求用于指定范围的两个迭代器必须具有完全一样的类型。roster1.end() 返回的迭代器依赖于 roster1 的类型。如果该容器是 const 对象,则返回的迭代器是 const_iterator 类型;否则,就是普通的 iterator 类型。在这个程序中,roster1 不是 const 对象,因而 end 返回的只是一个普通的迭代器。 如果我们将 it 定义为 const_iterator,那么 find_first_of 的调用将无法编译。用来指定范围的两个迭代器的类型不相同。it 是 const_iterator 类型的对象,而 rotser1.end() 返回的则是一个 iterator 对象。
Table 11.3. Iterator Categories 表 11.3. 迭代器种类
输入迭代器可用于读取容器中的元素,但是不保证能支持容器的写入操作。输入迭代器必须至少提供下列支持。 相等和不等操作符(==,!=),比较两个迭代器。 前置和后置的自增运算(++),使迭代器向前递进指向下一个元素。 用于读取元素的解引用操作符(*),此操作符只能出现在赋值运算的右操作数上。 箭头操作符(->),这是 (*it).member 的同义语,也就是说,对迭代器进行解引用来获取其所关联的对象的成员。 输入迭代器只能顺序使用;一旦输入迭代器自增了,就无法再用它检查之前的元素。要求在这个层次上提供支持的泛型算法包括 find 和 accumulate。标准库 istream_iterator 类型输入迭代器。 输出迭代器 可视为与输入迭代器功能互补的迭代器;输出迭代器可用于向容器写入元素,但是不保证能支持读取容器内容。输出迭代器要求: 前置和后置的自增运算(++),使迭代器向前递进指向下一个元素。 解引用操作符(*),引操作符只能出现在赋值运算的左操作数上。给解引用的输出迭代器赋值,将对该迭代器所指向的元素做写入操作。 输出迭代器可以要求每个迭代器的值必须正好写入一次。使用输出迭代器时,对于指定的迭代器值应该使用一次 * 运算,而且只能用一次。输出迭代器一般用作算法的第三个实参,标记起始写入的位置。例如,copy 算法使用一个输出迭代器作为它的第三个实参,将输入范围内的元素复制到输出迭代器指定的目标位置。标准库 ostream_iterator 类型输出迭代器。 前向迭代器 用于读写指定的容器。这类迭代器只会以一个方向遍历序列。前向迭代器支持输入迭代器和输出迭代器提供的所有操作,除此之外,还支持对同一个元素的多次读写。可复制前向迭代器来记录序列中的一个位置,以便将来返回此处。需要前向迭代器的泛型算法包括 replace。 双向迭代器 从两个方向读写容器。除了提供前向迭代器的全部操作之外,双向迭代器还提供前置和后置的自减运算(--)。需要使用双向迭代器的泛型算法包括 reverse。所有标准库容器提供的迭代器都至少达到双向迭代器的要求。 需要随机访问迭代器的泛型算法包括 sort 算法。vector、deque 和 string 迭代器是随机访问迭代器,用作访问内置数组元素的指针也是随机访问迭代器。 随机访问迭代器 提供在常量时间内访问容器任意位置的功能。这种迭代器除了支持双向迭代器的所有功能之外,还支持下面的操作: The relational operators <, <=, >, and >= to compare the relative positions of two iterators. 关系操作符 <、<=、> 和 >=,比较两个迭代器的相对位置。 迭代器与整型数值 n 之间的加法和减法操作符 +、+=、- 和 -=,结果是迭代器在容器中向前(或退回)n 个元素。 两个迭代器之间的减法操作符(--),得到两个迭代器间的距离。 下标操作符 iter[n],这是 *(iter + n) 的同义词。 尽管 map 和 set 类型提供双向迭代器,但关联容器只能使用算法的一个子集。问题在于:关联容器的键是 const 对象。因此,关联容器不能使用任何写序列元素的算法。只能使用与关联容器绑在一起的迭代器来提供用于读操作的实参。 向算法传递无效的迭代器类别所引起的错误,无法保证会在编译时被捕获到。 11.4.1. 算法的形参模式 任何其他的算法分类都含有一组形参规范。理解这些形参规范有利于学习新的算法——只要知道形参的含义,就可专注于了解算法实现的操作。大多数算法采用下面四种形式之一: alg (beg, end, other parms); alg (beg, end, dest, other parms); alg (beg, end, beg2, other parms); alg (beg, end, beg2, end2, other parms); 其中,alg 是算法的名字,beg 和 end 指定算法操作的元素范围。我们通常将该范围称为算法的“输入范围”。尽管几乎所有算法都有输入范围,但算法是否使用其他形参取决于它所执行的操作。这里列出了比较常用的其他形参:dest、beg2 和 end2,它们都是迭代器。这些迭代器在使用时,充当类似的角色。除了这些迭代器形参之外,有些算法还带有其他的菲迭代器形参,它们是这些算法特有的。 新对容器元素排序的算法要使用 < 操作符。这些算法的第二个重载版本带有一个额外的形参,表示用于元素排序的不同运算: sort (beg, end); // use < operator to sort the elements sort (beg, end, comp); // use function named comp to sort the elements 检查指定值的算法默认使用 == 操作符。系统为这类算法提供另外命名的(而非重载的)版本,带有谓词函数(第 11.2.3 节)形参。带有谓词函数形参的算法,其名字带有后缀 _if: 检查指定值的算法默认使用 == 操作符。系统为这类算法提供另外命名的(而非重载的)版本,带有谓词函数(第 11.2.3 节)形参。带有谓词函数形参的算法,其名字带有后缀 _if: find(beg, end, val); // find first instance of val in the input range find_if(beg, end, pred); // find first instance for which pred is true 上述两个算法都在输入范围内寻找指定元素的第一个实例。其中,find 算法查找一个指定的值,而 find_if 算法则用于查找一个使谓词函数 pred 返回非零值的元素。 区别是否实现复制的算法版本 无论算法是否检查它的元素值,都可能重新排列输入范围内的元素。在默认情况下,这些算法将重新排列的元素写回其输入范围。标准库也为这些算法提供另外命名的版本,将元素写到指定的输出目标。此版本的算法在名字中添加了 _copy 后缀: reverse(beg, end); reverse_copy(beg, end, dest); reverse 函数的功能就如它的名字所意味的:将输入序列中的元素反射重新排列。其中,第一个函数版本将自己的输入序列中的元素反向重排。而第二个版本,reverse_copy,则复制输入序列的元素,并将它们逆序存储到 dest 开始的序列中。 list 容器上的迭代器是双向的,而不是随机访问类型。由于 list 容器不支持随机访问,因此,在此容器上不能使用需要随机访问迭代器的算法。这些算法包括 sort 及其相关的算法。还有一些其他的泛型算法,如 merge、remove、reverse 和 unique,虽然可以用在 list 上,但却付出了性能上的代价。如果这些算法利用 list 容器实现的特点,则可以更高效地执行。 如果可以结合利用 list 容器的内部结构,则可能编写出更快的算法。与其他顺序容器所支持的操作相比,标准库为 list 容器定义了更精细的操作集合,使它不必只依赖于泛型操作。表 11.4 列出了 list 容器特有的操作,其中不包括要求支持双向或更弱的迭代器类型的泛型算法,这类泛型算法无论是用在 list 容器上,还是用在其他容器上,都具有相同的效果。 Table 11.4. list-Specific Operations 表 11.4. list 容器特有的操作
大多数 list 容器特有的算法类似于其泛型形式中已经见过的相应的算法,但并不相同: l.remove(val); // removes all instances of val from 1 l.remove_if(pred); // removes all instances for which pred is true from 1 l.reverse(); // reverses the order of elements in 1 l.sort(); // use element type < operator to compare elements l.sort(comp); // use comp to compare elements l.unique(); // uses element == to remove adjacent duplicates l.unique(comp); // uses comp to remove duplicate adjacent copies list 容器特有的算法与其泛型算法版本之间有两个至关重要的差别。其中一个差别是 remove 和 unique 的 list 版本修改了其关联的基础容器:真正删除了指定的元素。例如,list::unique 将 list 中第二个和后续重复的元素删除出该容器。
另一个差别是 list 容器提供的 merge 和 splice 运算会破坏它们的实参。使用 merge 的泛型算法版本时,合并的序列将写入目标迭代器指向的对象,而它的两个输入序列保持不变。但是,使用 list 容器的 merge 成员函数时,则会破坏它的实参 list 对象——当实参对象的元素合并到调用 merge 函数的 list 对象时,实参对象的元素被移出并删除。 |
|