10.6. Container-Specific Algorithms
Unlike the other containers, list and forward_list define several algorithms as members. In particular, the list types define their own versions of sort, merge, remove, reverse, and unique. The generic version of sort requires random-access iterators. As a result, sort cannot be used with list and forward_list because these types offer bidirectional and forward iterators, respectively.
The generic versions of the other algorithms that the list types define can be used with lists, but at a cost in performance. These algorithms swap elements in the input sequence. A list can “swap” its elements by changing the links among its elements rather than swapping the values of those elements. As a result, the list-specific versions of these algorithms can achieve much better performance than the corresponding generic versions.
These list-specific operations are described in Table 10.6. Generic algorithms not listed in the table that take appropriate iterators execute equally efficiently on lists and forward_listss as on other containers.
Table 10.6. Algorithms That are Members of list and forward_list
INFO
These operations return void.
| Code | Description |
|---|---|
lst.merge(lst2) lst.merge(lst2, comp) | Merges elements from lst2 onto lst. Both lst and lst2 must be sorted. Elements are removed from lst2. After the merge, lst2 is empty. The first version uses the < operator; the second version uses the given comparison operation. |
lst.remove(val) lst.remove_if(pred) | Calls erase to remove each element that is == to the given value or for which the given unary predicate succeeds. |
lst.reverse() | Reverses the order of the elements in lst. |
lst.sort() lst.sort(comp) | Sorts the elements of lst using < or the given comparison operation. |
lst.unique() lst.unique(comp) | Calls erase to remove consecutive copies of the same value. The first version uses ==; the second uses the given binary predicate. |
TIP
Best Practices
The list member versions should be used in preference to the generic algorithms for lists and forward_lists.
The splice Members
AdvancedThe list types also define a splice algorithm, which is described in Table 10.7. This algorithm is particular to list data structures. Hence a generic version of this algorithm is not needed.
Table 10.7. Arguments to the list and forward_list splice Members
lst.splice(args) or flst.splice_after(args)
args | Description |
|---|---|
(p, lst2) | p is an iterator to an element in lst or an iterator just before an element in flst. Moves all the element(s) from lst2 into lst just before p or into flst just after p. Removes the element(s) from lst2. lst2 must have the same type as lst or flst and may not be the same list. |
(p, lst2, p2) | p2 is a valid iterator into lst2. Moves the element denoted by p2 into lst or moves the element just after p2 into flst. lst2 can be the same list as lst or flst. |
(p, lst2, b, e) | b and e must denote a valid range in lst2. Moves the elements in the given range from lst2. lst2 and lst (or flst) can be the same list but p must not denote an element in the given range. |
The List-Specific Operations Do Change the Containers
Most of the list-specific algorithms are similar—but not identical—to their generic counterparts. However, a crucially important difference between the list-specific and the generic versions is that the list versions change the underlying container. For example, the list version of remove removes the indicated elements. The list version of unique removes the second and subsequent duplicate elements.
Similarly, merge and splice are destructive on their arguments. For example, the generic version of merge writes the merged sequence to a given destination iterator; the two input sequences are unchanged. The list merge function destroys the given list—elements are removed from the argument list as they are merged into the object on which merge was called. After a merge, the elements from both lists continue to exist, but they are all elements of the same list.