std::unique

定义于头文件 `<algorithm>`
template< class ForwardIt > ForwardIt unique( ForwardIt first, ForwardIt last );	(1)	(C++20 起为 constexpr)
template< class ExecutionPolicy, class ForwardIt > ForwardIt unique( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );	(2)	(C++17 起)
template< class ForwardIt, class BinaryPred > ForwardIt unique( ForwardIt first, ForwardIt last, BinaryPred p );	(3)	(C++20 起为 constexpr)
template< class ExecutionPolicy, class ForwardIt, class BinaryPred > ForwardIt unique( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, BinaryPred p );	(4)	(C++17 起)

从范围 [first, last) 中，移除每个连续的等价元素组中除第一个元素外的所有元素，并返回指向新范围末尾的后尾迭代器。

1) 使用 operator== 比较元素。

如果 operator== 未建立等价关系，则行为未定义。

3) 使用给定二元谓词 p 比较元素。

如果 p 未建立等价关系，则行为未定义。

2,4) 同 (1,3)，但按 policy 执行。

仅当满足所有以下条件时，这些重载才参与重载决议

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> 为 true。	(C++20 前)
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> 为 true。	(C++20 起)

first, last	-	定义要处理的元素范围的迭代器对
policy	-	要使用的执行策略
p	-	二元谓词，如果元素应被视为相等，则返回 true。谓词函数的签名应等效于以下内容： bool pred(const Type1 &a, const Type2 &b); 虽然签名不需要包含 const &，但函数不得修改传递给它的对象，并且必须能够接受 `Type1` 和 `Type2` 的所有（可能是 const）类型值，无论其值类别如何（因此，不允许使用 Type1 &，除非对于 `Type1` 移动等同于复制，否则也不允许使用 Type1(自 C++11 起)）。类型 Type1 和 Type2 必须使得类型为 ForwardIt 的对象可以被解引用，然后隐式转换为两者。
类型要求
- `ForwardIt` 必须满足 LegacyForwardIterator 的要求。
- 解引用 `ForwardIt` 的类型必须满足可移动赋值 (MoveAssignable) 的要求。

[edit] 返回值

指向范围新末尾的 ForwardIt。

[edit] 复杂度

给定 $\scriptsize N$ $N$ 作为 std::distance(first, last)

1,2) 使用 operator== 进行恰好

max(0,N-1)

次比较。

3,4) 恰好

max(0,N-1)

次应用谓词 p。

[edit] 异常

带有模板参数 ExecutionPolicy 的重载按如下方式报告错误

如果作为算法一部分调用的函数执行期间抛出异常，并且 ExecutionPolicy 是标准策略之一，则调用 std::terminate。对于任何其他 ExecutionPolicy，行为是实现定义的。
如果算法未能分配内存，则抛出 std::bad_alloc。

[edit] 可能实现

另请参阅 libstdc++、libc++ 和 MSVC STL 中的实现。

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 (3)

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;
}

[edit] 注意

对 unique 的调用通常会后接对容器的 erase 成员函数的调用，以实际从容器中移除元素。

[edit] 示例

运行此代码

#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

[edit] 缺陷报告

下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。

缺陷报告	应用于	发布时的行为	正确的行为
LWG 202	C++98	如果元素使用非等价关系进行比较，则行为不明确。如果元素使用非等价关系进行比较，行为不明确	在这种情况下，行为是未定义的

[edit] 参阅

adjacent_find	寻找第一对相等的（或满足给定谓词的）相邻项 (函数模板) [编辑]
unique_copy	创建一个不含连续重复元素的某个元素范围的副本 (函数模板) [编辑]
removeremove_if	移除满足特定标准的元素 (函数模板) [编辑]
unique	移除连续的重复元素 (`std::list<T,Allocator>` 的公共成员函数) [编辑]
unique	移除连续的重复元素 (`std::forward_list<T,Allocator>` 的公共成员函数) [编辑]
ranges::unique (C++20)	移除一个范围中的连续重复元素 (算法函数对象)[编辑]

编译器支持
自由（freestanding）与宿主（hosted）
语言
标准库
标准库头文件
具名要求
特性测试宏 (C++20)
语言支持库
概念库 (C++20)
诊断库
内存管理库
元编程库 (C++11)
通用工具库
容器库
迭代器库
范围库 (C++20)
算法库
字符串库
文本处理库
数值库
日期和时间库
输入/输出库
文件系统库 (C++17)
并发支持库 (C++11)
执行控制库 (C++26)
技术规范
符号索引
外部库

cppreference.cn

命名空间

变体

视图

操作