What is a Name?
The following two algorithms can be somewhat confusing the first time they are encountered. Both claim to remove certain values from a sequence. But, in fact, neither one reduces the size of the sequence. Both operate by moving the values that are to be retained to the front of the sequence, and returning an iterator that describes where this sequence ends. Elements after this iterator are simply the original sequence values, left unchanged. This is necessary because the generic algorithm has no knowledge of the container it is working on. It only has a generic iterator. This is part of the price we pay for generic algorithms. In most cases the user will want to use this iterator result as an argument to the erase() member function for the container, removing the values from the iterator to the end of the sequence.
Let us illustrate this with a simple example. Suppose we want to remove the even numbers from the sequence 1 2 3 4 5 6 7 8 9 10, something we could do with the remove_if() algorithm. The algorithm remove_if() would leave us with the following sequence:
1 3 5 7 9 | 6 7 8 9 10
The vertical bar here represents the position of the iterator returned by the remove_if() algorithm. Notice that the five elements before the bar represent the result we want, while the five values after the bar are simply the original contents of those locations. Using this iterator value along with the end-of-sequence iterator as arguments to erase(), we can eliminate the unwanted values, and obtained the desired result.
Both the algorithms described here have an alternative copy version. The copy version of the algorithms leaves the original unchanged, and places the preserved elements into an output sequence.
Obtaining the Source
The algorithm remove() eliminates unwanted values from a sequence. As with the find() algorithm, these can either be values that match a specific constant, or values that satisfy a given predicate. The declaration of the argument types is as follows:
ForwardIterator remove
(ForwardIterator first, ForwardIterator last, const T &);
ForwardIterator remove_if
(ForwardIterator first, ForwardIterator last, Predicate);
The algorithm remove() copies values to the front of the sequence, overwriting the location of the removed elements. All elements not removed remain in their relative order. Once all values have been examined, the remainder of the sequence is left unchanged. The iterator returned as the result of the operation provides the end of the new sequence. For example, eliminating the element 2 from the sequence 1 2 4 3 2 results in the sequence 1 4 3 3 2, with the iterator returned as the result pointing at the second 3. This value can be used as argument to erase() in order to eliminate the remaining elements (the 3 and the 2), as illustrated in the example program.
A copy version of the algorithms copies values to an output sequence, rather than making transformations in place.
OutputIterator remove_copy
(InputIterator first, InputIterator last,
OutputIterator result, const T &);
OutputIterator remove_copy_if
(InputIterator first, InputIterator last,
OutputIterator result, Predicate);
The use of remove() is shown in the following program.
void remove_example ()
// illustrate the use of the remove algorithm
{
// create a list of numbers
int data[] = {1, 2, 4, 3, 1, 4, 2};
list<int> aList;
copy (data, data+7, inserter(aList, aList.begin()));
// remove 2's, copy into new list
list<int> newList;
remove_copy (aList.begin(), aList.end(),
back_inserter(newList), 2);
// remove 2's in place
list<int>::iterator where;
where = remove (aList.begin(), aList.end(), 2);
aList.erase(where, aList.end());
// remove all even values
where = remove_if (aList.begin(), aList.end(), isEven);
aList.erase(where, aList.end());
}
The algorithm unique() moves through a linear sequence, eliminating all but the first element from every consecutive group of equal elements. The argument sequence is described by forward iterators.
ForwardIterator unique (ForwardIterator first,
ForwardIterator last [, BinaryPredicate ] );
As the algorithm moves through the collection, elements are moved to the front of the sequence, overwriting the existing elements. Once all unique values have been identified, the remainder of the sequence is left unchanged. For example, a sequence such as 1 3 3 2 2 2 4 will be changed into 1 3 2 4 | 2 2 4. We have used a vertical bar to indicate the location returned by the iterator result value. This location marks the end of the unique sequence, and the beginning of the left-over elements. With most containers the value returned by the algorithm can be used as an argument in a subsequent call on erase() to remove the undesired elements from the collection. This is illustrated in the example program.
A copy version of the algorithm moves the unique values to an output iterator, rather than making modifications in place. In transforming a list or multiset, an insert iterator can be used to change the copy operations of the output iterator into insertions.
OutputIterator unique_copy
(InputIterator first, InputIterator last,
OutputIterator result [, BinaryPredicate ] );
These are illustrated in the sample program:
void unique_example ()
// illustrate use of the unique algorithm
{
// first make a list of values
int data[] = {1, 3, 3, 2, 2, 4};
list<int> aList;
set<int> aSet;
copy (data, data+6, inserter(aList, aList.begin()));
// copy unique elements into a set
unique_copy (aList.begin(), aList.end(),
inserter(aSet, aSet.begin()));
// copy unique elements in place
list<int>::iterator where;
where = unique(aList.begin(), aList.end());
// remove trailing values
aList.erase(where, aList.end());
}