Team LiB
Previous Section Next Section

11.5. Container-Specific Algorithms

11.5. 容器特有的算法

The iterators on list are bidirectional, not random access. Because the list container does not support random access, we cannot use the algorithms that require random-access iterators. These algorithms include the sort-related algorithms. There are other algorithms, defined generically, such as merge, remove, reverse, and unique, that can be used on lists but at a cost in performance. These algorithms can be implemented more efficiently if they can take advantage of how lists are implemented.

list 容器上的迭代器是双向的，而不是随机访问类型。由于 list 容器不支持随机访问，因此，在此容器上不能使用需要随机访问迭代器的算法。这些算法包括 sort 及其相关的算法。还有一些其他的泛型算法，如 merge、remove、reverse 和 unique，虽然可以用在 list 上，但却付出了性能上的代价。如果这些算法利用 list 容器实现的特点，则可以更高效地执行。

It is possible to write much faster algorithms if the internal structure of the list can be exploited. Rather than relying solely on generic operations, the library defines a more elaborate set of operations for list than are supported for the other sequential containers. These list-specific operations are described in Table 11.4 on the next page. Generic algorithms not listed in the table that take bidirectional or weaker iterators execute equally efficiently on lists as on other containers.

如果可以结合利用 list 容器的内部结构，则可能编写出更快的算法。与其他顺序容器所支持的操作相比，标准库为 list 容器定义了更精细的操作集合，使它不必只依赖于泛型操作。表 11.4 列出了 list 容器特有的操作，其中不包括要求支持双向或更弱的迭代器类型的泛型算法，这类泛型算法无论是用在 list 容器上，还是用在其他容器上，都具有相同的效果。

Table 11.4. list-Specific Operations
表 11.4. list 容器特有的操作

lst.merge(lst2) lst.merge(lst2, comp)
 

Merges elements from lst2 onto lst. Both lists must be sorted. Elements are removed from lst2. After the merge, lst2 is empty. Returns void. The first version uses the < operator; the second version uses the specified comparison.

将 lst2 的元素合并到 lst 中。这两个 list 容器对象都必须排序。lst2 中的元素将被删除。合并后，lst2 为空。返回 void 类型。第一个版本使用 < 操作符，而第二个版本则使用 comp 指定的比较运算

lst.remove(val) lst.remove_if(unaryPred)
 

Removes, by calling lst.erase, each element that equals a specified value or for which the specified predicate returns a nonzero value. Returns void.

调用 lst.erase 删除所有等于指定值或使指定的谓词函数返回非零值的元素。返回 void 类型

lst.reverse()

Reverses the order of the elements in lst.

反向排列 lst 中的元素

lst.sort

Sorts the elements of the lst.

对 lst 中的元素排序

lst.splice(iter, lst2)

lst.splice(iter, lst2, iter2)

lst.splice(iter, beg, end)
 

Moves element(s) from lst2 into lst just before the element (in lst) referred to by the iterator iter. Removes element(s) that are moved from lst2. The first version moves all elements from lst2 into lst; after the splice, lst2 is empty. lst and lst2 may not be the same list. The second version moves only the element referred to by iter2, which must refer to an element in lst2. In this case, lst2 and lst could be the same list. That is, splice can be used to move an element within a single list. The third version moves the elements in the range denoted by the iterators beg and end. As usual, beg and end must refer to a valid range. The iterators can refer to a range in any list, including lst. If the iterators refer to lst, the operation is undefined if iter refers to an element in the range.

将 lst2 的元素移到 lst 中迭代器 iter 指向的元素前面。在 lst2 中删除移出的元素。第一个版本将 lst2 的所有元素移到 lst 中；合并后，lst2 为空。lst 和 lst2 不能是同一个 list 对象。第二个版本只移动 iter2 所指向的元素，这个元素必须是 lst2 中的元素。在这种情况中，lst 和 lst2 可以是同一个 list 对象。也就是说，可在一个 list 对象中使用 splice 运算移动一个元素。第三个版本移动迭代器 beg 和 end 标记的范围内的元素。beg 和 end 照例必须指定一个有效的范围。这两个迭代器可标记任意 list 对象内的范围，包括 lst。当它们指定 lst 的一段范围时，如果 iter 也指向这个范围的一个元素，则该运算未定义。

lst.unique() lst.unique(binaryPred)

  
 

Deletes, by calling erase, consecutive copies of the same value. The first version uses == to determine if elements are equal; the second uses the specified predicate.

调用 erase 删除同一个值的团结副本。第一个版本使用 == 操作符判断元素是否相等；第二个版本则使用指定的谓词函数实现判断

The list member versions should be used in preference to the generic algorithms when applied to a list object.

对于 list 对象，应该优先使用 list 容器特有的成员版本，而不是泛型算法。

Most of the list-specific algorithms are similarbut not identicalto their counterparts that we have already seen in their generic forms:

大多数 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

There are two crucially important differences between the list-specific operations and their generic counterparts. One difference is that the list versions of remove and unique change the underlying container; the indicated elements are actually removed. For example, second and subsequent duplicate elements are removed from the list by list::unique.

list 容器特有的算法与其泛型算法版本之间有两个至关重要的差别。其中一个差别是 remove 和 unique 的 list 版本修改了其关联的基础容器：真正删除了指定的元素。例如，list::unique 将 list 中第二个和后续重复的元素删除出该容器。

Unlike the corresponding generic algorithms, the list-specific operations do add and remove elements.

与对应的泛型算法不同，list 容器特有的操作能添加和删除元素。

The other difference is that the list operations, merge and splice, are destructive on their arguments. When we use the generic version of merge, the merged sequence is written to a destination iterator, and the two input sequences are left unchanged. In the case of the merge function that is a member of list, the argument list is destroyedelements are moved from the argument and removed as they are merged into the list object on which merge was called.

另一个差别是 list 容器提供的 merge 和 splice 运算会破坏它们的实参。使用 merge 的泛型算法版本时，合并的序列将写入目标迭代器指向的对象，而它的两个输入序列保持不变。但是，使用 list 容器的 merge 成员函数时，则会破坏它的实参 list 对象——当实参对象的元素合并到调用 merge 函数的 list 对象时，实参对象的元素被移出并删除。

Exercises Section 11.5

Exercise 11.29:

Reimplement the program that eliminated duplicate words that we wrote in Section 11.2.3 (p. 400) to use a list instead of a vector.

用 list 容器取代 vector 重新实现liminated duplicate words that we wrote in 第 11.2.3 节编写的排除重复单词的程序。
Team LiB
Previous Section Next Section