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 开始)

[编辑] 解释

移除是通过以下方式完成的：移位范围内的元素，使不应移除的元素出现在范围的开头。

移位是通过复制赋值(直到 C++11)移动赋值(从 C++11 开始) 完成的。
移除操作是稳定的：不应移除的元素的相对顺序保持不变。
[first, last) 的底层序列不会因移除操作而缩短。假设 result 是返回的迭代器

[result, last) 中的所有迭代器仍然是可解除引用的。

[result, last) 中的每个元素都具有有效的但未指定的狀態，因为移动赋值可以通過从最初位于该范围内的元素移动来消除元素。

(自 C++11 起)

[编辑] 参数

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

[编辑] 返回值

指向范围新末尾的 ForwardIt。

[编辑] 复杂度

假设 $\scriptsize N$ $N$ 为 std::distance(first, last)

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

max(0,N-1)

次比较。

3,4) 恰好

max(0,N-1)

次应用谓词 p。

[编辑] 异常

具有名为 ExecutionPolicy 的模板参数的重载报告错误如下

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

[编辑] 可能的实现

另请参阅 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;
}

[编辑] 注释

通常在对 unique 的调用之后，紧跟着对容器的 erase 成员函数的调用，以实际从容器中删除元素。

[编辑] 示例

运行此代码

#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

[编辑] 缺陷报告

以下行为更改缺陷报告被追溯应用于先前发布的 C++ 标准。

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

[编辑] 另请参阅

adjacent_find	找到第一个相等的两个相邻项（或满足给定谓词的两个相邻项） (函数模板) [编辑]
unique_copy	创建一些不包含连续重复项的元素范围的副本 (函数模板) [编辑]
removeremove_if	删除满足特定条件的元素 (函数模板) [编辑]
unique	删除连续重复元素 (`std::list<T,Allocator>` 的公有成员函数) [编辑]
unique	删除连续重复元素 (`std::forward_list<T,Allocator>` 的公有成员函数) [编辑]
ranges::unique (C++20)	删除范围内的连续重复元素 (niebloid)[编辑]

编译器支持
独立和托管
语言
标准库
标准库头文件
命名要求
功能测试宏 (C++20)
语言支持库
概念库 (C++20)
元编程库 (C++11)
诊断库
通用实用工具库
字符串库
容器库
迭代器库
范围库 (C++20)
算法库
数值库
本地化库
输入/输出库
文件系统库 (C++17)
正则表达式库 (C++11)
并发支持库 (C++11)
执行支持库 (C++26)
技术规范
符号索引
外部库

cppreference.com

命名空间

变体

视图

操作