| Thinking in C++ Vol 2 - Practical Programming |
|
Prev |
Home |
Next |
Because of the genericity of the STL, the concept of removal
is a bit constrained. Since elements can only be removed via iterators, and
iterators can point to arrays, vectors, lists, and so on, it is
not safe or reasonable to try to destroy the elements that are being removed
and to change the size of the input range [first, last). (An array, for
example, cannot have its size changed.) So instead, what the STL remove
functions do is rearrange the sequence so that the removed elements are at
the end of the sequence, and the un-removed elements are at the beginning of
the sequence (in the same order that they were before, minus the removed
elements that is, this is a stable operation). Then the function will
return an iterator to the new last element of the sequence, which is the end
of the sequence without the removed elements and the beginning of the sequence
of the removed elements. In other words, if new_last is the iterator
that is returned from the remove function, [first, new_last) is the
sequence without any of the removed elements, and [new_last, last) is
the sequence of removed elements.
If you are simply using your sequence, including the removed
elements, with more STL algorithms, you can just use new_last as the new
past-the-end iterator. However, if you re using a resizable container c (not
an array) and you want to eliminate the removed elements from the container,
you can use erase( ) to do so, for example:
c.erase(remove(c.begin(), c.end(), value), c.end());
You can also use the resize( ) member function
that belongs to all standard sequences (more on this in the next chapter).
The return value of remove( ) is the new_last
iterator, so erase( ) deletes all the removed elements from c.
The iterators in [new_last, last) are
dereferenceable, but the element values are unspecified and should not be used.
ForwardIterator remove(ForwardIterator first,
ForwardIterator last, const T& value);
ForwardIterator remove_if(ForwardIterator first,
ForwardIterator last, Predicate pred);
OutputIterator remove_copy(InputIterator first,
InputIterator last, OutputIterator result, const T&
value);
OutputIterator remove_copy_if(InputIterator first,
InputIterator last, OutputIterator result, Predicate
pred);
Each of the remove forms moves through the range [first,
last), finding values that match a removal criterion and copying the
unremoved elements over the removed elements (thus effectively removing them).
The original order of the unremoved elements is maintained. The return value is
an iterator pointing past the end of the range that contains none of the
removed elements. The values that this iterator points to are unspecified.
The if versions pass each element to pred( )
to determine whether it should be removed. (If pred( ) returns true,
the element is removed.) The copy versions do not modify the original
sequence, but instead copy the unremoved values into a range beginning at result
and return an iterator indicating the past-the-end value of this new range.
ForwardIterator unique(ForwardIterator first,
ForwardIterator last);
ForwardIterator unique(ForwardIterator first,
ForwardIterator last, BinaryPredicate binary_pred);
OutputIterator unique_copy(InputIterator first,
InputIterator last, OutputIterator result);
OutputIterator unique_copy(InputIterator first,
InputIterator last, OutputIterator result,
BinaryPredicate binary_pred);
Each of the unique functions moves through the range [first,
last), finding adjacent values that are equivalent (that is, duplicates)
and removing the duplicate elements by copying over them. The original order
of the unremoved elements is maintained. The return value is an iterator
pointing past the end of the range that has the adjacent duplicates removed.
Because only duplicates that are adjacent are removed, it s
likely that you ll want to call sort( ) before calling a unique
algorithm, since that will guarantee that all the duplicates are removed.
For each iterator value i in the input range, the
versions containing binary_pred call:
and if the result is true, *i is considered a
duplicate.
The copy versions do not modify the original sequence, but
instead copy the unremoved values into a range beginning at result and
return an iterator indicating the past-the-end value of this new range.
Example
This example gives a visual demonstration of the way the
remove and unique functions work.
//: C06:Removing.cpp
// The removing algorithms.
//{L} Generators
#include <algorithm>
#include <cctype>
#include <string>
#include "Generators.h"
#include "PrintSequence.h"
using namespace std;
struct IsUpper {
bool operator()(char c) { return isupper(c); }
};
int main() {
string v;
v.resize(25);
generate(v.begin(), v.end(), CharGen());
print(v.begin(), v.end(), "v original",
"");
// Create a set of the characters in v:
string us(v.begin(), v.end());
sort(us.begin(), us.end());
string::iterator it = us.begin(), cit = v.end(),
uend = unique(us.begin(), us.end());
// Step through and remove everything:
while(it != uend) {
cit = remove(v.begin(), cit, *it);
print(v.begin(), v.end(), "Complete v",
"");
print(v.begin(), cit, "Pseudo v ", "
");
cout << "Removed element:\t"
<< *it
<< "\nPsuedo Last Element:\t"
<< *cit << endl << endl;
++it;
}
generate(v.begin(), v.end(), CharGen());
print(v.begin(), v.end(), "v",
"");
cit = remove_if(v.begin(), v.end(), IsUpper());
print(v.begin(), cit, "v after remove_if
IsUpper", " ");
// Copying versions are not shown for remove()
// and remove_if().
sort(v.begin(), cit);
print(v.begin(), cit, "sorted", "
");
string v2;
v2.resize(cit - v.begin());
unique_copy(v.begin(), cit, v2.begin());
print(v2.begin(), v2.end(), "unique_copy",
" ");
// Same behavior:
cit = unique(v.begin(), cit, equal_to<char>());
print(v.begin(), cit, "unique
equal_to<char>", " ");
} ///:~
The string v is a container of characters
filled with randomly generated characters. Each character is used in a remove
statement, but the entire string v is displayed each time so you can see
what happens to the rest of the range, after the resulting endpoint (which is
stored in cit).
To demonstrate remove_if( ), the standard C
library function isupper( ) (in <cctype>) is
called inside the function object class IsUpper, an object of which is
passed as the predicate for remove_if( ). This returns true
only if a character is uppercase, so only lowercase characters will remain.
Here, the end of the range is used in the call to print( ) so only
the remaining elements will appear. The copying versions of remove( )
and remove_if( ) are not shown because they are a simple variation
on the noncopying versions, which you should be able to use without an example.
The range of lowercase letters is sorted in preparation for
testing the unique functions. (The unique functions are not undefined if
the range isn t sorted, but it s probably not what you want.) First, unique_copy( )
puts the unique elements into a new vector using the default element
comparison, and then uses the form of unique( ) that takes a
predicate. The predicate is the built-in function object equal_to( ),
which produces the same results as the default element comparison.
| Thinking in C++ Vol 2 - Practical Programming |
|
Prev |
Home |
Next |
