Section 11.5. Container-Specific Algorithms


11.5. Container-Specific Algorithms

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.

Exercises Section 11.4.2

Exercise 11.27:

The library defines the following algorithms:

      replace(beg, end, old_val, new_val);      replace_if(beg, end, pred, new_val);      replace_copy(beg, end, dest, old_val, new_val);      replace_copy_if(beg, end, dest, pred, new_val); 

Based only on the names and parameters to these functions, describe the operation that these algorithms perform.

Exercise 11.28:

Assume lst is a container that holds 100 elements. Explain the following program fragment and fix any bugs you think are present.

      vector<int> vec1;      reverse_copy(lst.begin(), lst.end(), vec1.begin()); 


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.

Table 11.4. list-Specific Operations

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.

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.reverse()

Reverses the order of the elements in lst.

lst.sort

Sorts the elements of the 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.

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.


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



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

      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.

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



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.

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.




C++ Primer
C Primer Plus (5th Edition)
ISBN: 0672326965
EAN: 2147483647
Year: 2006
Pages: 223
Authors: Stephen Prata

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net