Difference between revisions of "cpp/algorithm/unique"
(Fixed (again) to work with empty ranges) |
|||
| Line 31: | Line 31: | ||
ForwardIterator unique(ForwardIterator first, ForwardIterator last) | ForwardIterator unique(ForwardIterator first, ForwardIterator last) | ||
{ | { | ||
| − | if (first | + | if (first == last) |
| − | ForwardIterator result = first; | + | return last; |
| − | + | ||
| − | + | ForwardIterator result = first; | |
| − | + | while (++first != last) { | |
| − | + | if (!(*result == *first)) { | |
| + | *(++result) = *first; | ||
} | } | ||
} | } | ||
| Line 46: | Line 47: | ||
BinaryPredicate p) | BinaryPredicate p) | ||
{ | { | ||
| − | if (first | + | if (first == last) |
| − | ForwardIterator result = first; | + | return last; |
| − | + | ||
| − | + | ForwardIterator result = first; | |
| − | + | while (++first != last) { | |
| − | + | if (!p(*result, *first)) { | |
| + | *(++result) = *first; | ||
} | } | ||
} | } | ||
Revision as of 13:31, 15 May 2012
Template:cpp/algorithm/sidebar Template:ddcl list begin <tr class="t-dsc-header">
<td><algorithm>
<td></td> <td></td> </tr> <tr class="t-dcl ">
<td >ForwardIterator unique( ForwardIterator first, ForwardIterator last );
<td > (1) </td> <td class="t-dcl-nopad"> </td> </tr> <tr class="t-dcl ">
<td >ForwardIterator unique( ForwardIterator first, ForwardIterator last, BinaryPredicate p );
<td > (2) </td> <td class="t-dcl-nopad"> </td> </tr> Template:ddcl list end
Removes all consecutive duplicate elements from the range [first, last). Removing is done by shifting the range when needed in such a way that elements to be erased are overwritten. Only the first element in each group of equal elements is left. The elements between the old and the new end or the range are left intact. The first version uses operator== to compare the elements, the second version uses the given binary predicate p.
Contents |
Parameters
| first, last | - | the range of elements to process |
| p | - | binary predicate which returns true if the elements should be treated as equal. The signature of the predicate function should be equivalent to the following: bool pred(const Type1 &a, const Type2 &b); While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) |
Return value
forward iterator to the new end of the range
Possible implementation
Example
The following code removes all consecutive equivalent elements from a vector of integers.
#include <iostream> #include <algorithm> #include <vector> int main() { std::vector<int> v{1, 2, 2, 2, 3, 3, 2, 2, 1}; std::vector<int>::iterator last; last = std::unique(v.begin(), v.end()); // 1 2 3 2 1 3 2 2 1 // ^ for (std::vector<int>::iterator it = v.begin(); it != last; ++it) { std::cout << *it << " "; } std::cout << "\n"; }
Output:
1 2 3 2 1
Complexity
linear in the distance between first and last
