std::unique() algorithm
- od C++20
- od C++17
- do C++17
// (1)
template< class ForwardIt >
constexpr ForwardIt unique( ForwardIt first, ForwardIt last );
// (2)
template< class ForwardIt, class BinaryPredicate >
constexpr ForwardIt unique( ForwardIt first, ForwardIt last, BinaryPredicate p );
// (3)
template< class ExecutionPolicy, class ForwardIt >
ForwardIt unique( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );
// (4)
template< class ExecutionPolicy, class ForwardIt, class BinaryPredicate >
ForwardIt unique( ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last, BinaryPredicate p );
// (1)
template< class ForwardIt >
ForwardIt unique( ForwardIt first, ForwardIt last );
// (2)
template< class ForwardIt, class BinaryPredicate >
ForwardIt unique( ForwardIt first, ForwardIt last, BinaryPredicate p );
// (3)
template< class ExecutionPolicy, class ForwardIt >
ForwardIt unique( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );
// (4)
template< class ExecutionPolicy, class ForwardIt, class BinaryPredicate >
ForwardIt unique( ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last, BinaryPredicate p );
// (1)
template< class ForwardIt >
ForwardIt unique( ForwardIt first, ForwardIt last );
// (3)
template< class ForwardIt, class BinaryPredicate >
ForwardIt unique( ForwardIt first, ForwardIt last, BinaryPredicate p );
Eliminates all except the first element from every consecutive group of equivalent elements from the range [first
; last
) and returns a past-the-end iterator for the new logical
end of the range.
-
(1) Elements are compared using
operator==
. -
(2) Elements are compared using the given binary predicate
p
. -
(3 - 4) Same as (1 - 2), but executed according to
policy
.Overload ResolutionThese overloads participate in overload resolution only if
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
(do C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
(od C++20) istrue
.
Removing is done by shifting the elements in the range in such a way that elements to be erased are overwritten.
The behavior is undefined
if it is not an equivalence relation.Parameters
first last | The range of elements to process. |
policy | The execution policy to use. See execution policy for details. |
p | Binary predicate which returns The signature of the function should be equivalent to the following:
|
Type requirements
ForwardIt | LegacyForwardIterator |
Dereferenced ForwardIt | MoveAssignable |
Return value
For nonempty ranges, exactly td::distance(first, last) - 1
applications of the corresponding predicate.
Complexity
Given N
as std::distance(first, last)
:
At most N applications of predicate p
.
Exceptions
The overloads with a template parameter named ExecutionPolicy
report errors as follows:
- If execution of a function invoked as part of the algorithm throws an exception and
ExecutionPolicy
is one of the standard policies,std::terminate
is called. For any otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory,
std::bad_alloc
is thrown.
Possible implementation
unique (1)
template<class ForwardIt>
ForwardIt unique(ForwardIt first, ForwardIt last)
{
if (first == last)
return last;
ForwardIt result = first;
while (++first != last)
if (!(*result == *first) && ++result != first)
*result = std::move(*first);
return ++result;
}
unique (2)
template<class ForwardIt, class BinaryPredicate>
ForwardIt unique(ForwardIt first, ForwardIt last, BinaryPredicate p)
{
if (first == last)
return last;
ForwardIt result = first;
while (++first != last)
if (!p(*result, *first) && ++result != first)
*result = std::move(*first);
return ++result;
}
Notes
Relative order of the elements that remain is preserved and the physical size of the container is unchanged.
Iterators in [r
; last
) (if any), where r
is the return value, are still dereferenceable, but the elements themselves have unspecified values.
A call to std::unique
is typically followed by a call to a container's erase
member function, which erases the unspecified values and reduces the physical
size of the container to match its new logical
size.
Examples
The following code uniques all spaces from a string by shifting all non-space characters to the left and then erasing the extra. This is an example of Erase-remove idiom.
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
// a vector containing several duplicate elements
std::vector<int> v {1, 2, 1, 1, 3, 3, 3, 4, 5, 4};
auto print = [&](int id)
{
std::cout << "@" << id << ": ";
for (int i : v)
std::cout << i << ' ';
std::cout << '\n';
};
print(1);
// remove consecutive (adjacent) duplicates
auto last = std::unique(v.begin(), v.end());
// v now holds {1 2 1 3 4 5 4 x x x}, where 'x' is indeterminate
v.erase(last, v.end());
print(2);
// sort followed by unique, to remove all duplicates
std::sort(v.begin(), v.end()); // {1 1 2 3 4 4 5}
print(3);
last = std::unique(v.begin(), v.end());
// v now holds {1 2 3 4 5 x x}, where 'x' is indeterminate
v.erase(last, v.end());
print(4);
}
@1: 1 2 1 1 3 3 3 4 5 4
@2: 1 2 1 3 4 5 4
@3: 1 1 2 3 4 4 5
@4: 1 2 3 4 5
Hover to see the original license.