unique 去重

读完能做什么

• 能说出 unique 只合并相邻的相等元素，并能预测哪些元素会被保留。
• 能解释 unique 的返回值是“新的逻辑末尾”，而不是新的容器长度。
• 能用 sort + unique + erase 三行把一组数据真正去重。
• 能区分“逻辑删除”（有效前缀变短）和“容器真的变小”（size() 改变）。

为什么需要它

题目常常要求：读入 n 个整数，把重复的只保留一个，再按从小到大输出。

不借助算法的手工做法是：先排序，然后从头扫一遍，遇到和“上一个保留的值”不同的就把它留下。第二步“扫描相邻元素并合并”是固定的套路，标准库把它做成了函数 unique。

这里要先分清两件事：排序是为了让相等的值聚到一起，是“全体去重”这个任务需要的；“合并相邻相等元素”才是 unique 的本职工作。unique 并不要求你先排序，后面会用 [1,2,1] 把这层区别展示出来。

它是什么

一句话：unique(first, last) 把区间里相邻的相等元素合并成一个，返回新的逻辑末尾位置。

先解释两个必须用到的概念。

迭代器与区间 [first, last)。 迭代器是“指向容器中某个位置的游标”。v.begin() 指向第一个元素，v.end() 指向最后一个元素的后面一个位置（注意不是最后一个元素本身）。两个迭代器一起表示一段连续的位置，写成左闭右开区间 [first, last)：包含 first 指向的元素，不包含 last 指向的元素。所以 [v.begin(), v.end()) 正好是整个 vector。本页的 unique、sort、erase 都用这种区间来描述要处理的范围。

sort(v.begin(), v.end())。 把区间里的元素按从小到大重新排列，默认用 < 比较。排序之后，值相等的元素一定挨在一起，正好满足 unique 需要的“相邻”条件。sort 的详细用法见 sort 排序。

以数据 A [1, 1, 2, 2, 2, 3] 为例，逐个元素看“相邻”是什么意思：

保留下来的是 1、2、3，也就是有效前缀 [1,2,3]，逻辑长度 3。

unique 会做和不会做的事：

• 会：合并相邻的相等元素，并返回有效前缀末尾的位置。
• 不会：不改变容器大小（数据 A 处理后 size() 仍然是 6）；不处理不相邻的重复值（见后面的 [1,2,1]）；不规定返回位置之后的内容。

最小可运行示例

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 1, 2, 2, 2, 3};

    auto last = unique(v.begin(), v.end());   // 返回新的“逻辑末尾”

    cout << "调用 unique 后：size = " << v.size() << '\n';
    cout << "逻辑长度 = " << (last - v.begin()) << '\n';

    cout << "有效前缀：";
    for (auto it = v.begin(); it != last; it++) cout << *it << ' ';
    cout << '\n';

    cout << "容器里的全部内容：";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';
    cout << '\n';

    v.erase(last, v.end());                   // 真正删除尾段
    cout << "erase 后：size = " << v.size() << "，内容：";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';
    cout << '\n';
    return 0;
}

输出：

调用 unique 后：size = 6
逻辑长度 = 3
有效前缀：1 2 3 
容器里的全部内容：1 2 3 2 2 3 
erase 后：size = 3，内容：1 2 3 

逐行看：

• unique(v.begin(), v.end()) 处理整个 vector，返回一个新的位置。
• auto last = ... 里的 auto 表示“让编译器根据右边的值推断类型”，这里 last 的类型就是 vector<int>::iterator。
• 调用 unique 后：size = 6：unique 没有删除任何元素，容器的大小没变。
• last - v.begin() 是“返回的位置减去起始位置”，得到有效前缀的长度 3。
• for (auto it = v.begin(); it != last; it++) 从起点走到新的逻辑末尾，用 *it 取出元素，打印出有效前缀 1 2 3。
• 接下来一行打印容器里的全部内容。这一行只是本机（GCC 16.2.0）的实测结果：标准没有规定返回位置之后放什么，换一个编译器可能不同。所以只能读 [begin, last) 这一段，last 之后的内容不能当作结果使用。
• 最后 v.erase(last, v.end()) 把尾段真正删掉，size() 才变成 3，内容变成 1 2 3。erase 的用法在“真正删除”一节展开。

一步步看变化

unique 从前往后扫描，拿每个元素和“上一个保留下来的元素”比较：

扫描结束时返回有效前缀末尾的位置，所以逻辑长度是 3。这时容器可以看成两块区域：

注意尾段不是“被删掉的重复值集合”，它只是一段不再读取的旧数据。这也是为什么只调用 unique 还不够——如果后面照旧用 v.size() 遍历，就会把尾段一起读出来。

逐项扩展核心操作

真正删除：sort + unique + erase

要既去掉重复值又让容器真的变小，就在 unique 之后调用 erase(last, v.end()) 删掉尾段。用数据 B [1, 2, 1]（有不相邻的重复值）：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 2, 1};

    sort(v.begin(), v.end());                 // 先排序：相等的值会挨在一起
    cout << "排序后：";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';
    cout << "size = " << v.size() << '\n';

    auto last = unique(v.begin(), v.end());   // 相邻去重
    cout << "unique 后：逻辑长度 = " << (last - v.begin())
         << "，size = " << v.size() << '\n';

    v.erase(last, v.end());                   // 真正删除尾段
    cout << "erase 后：";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';
    cout << "size = " << v.size() << '\n';
    return 0;
}

输出：

排序后：1 1 2 size = 3
unique 后：逻辑长度 = 2，size = 3
erase 后：1 2 size = 2

三步各自负责什么：

erase(first, last) 删除的是左闭右开区间 [first, last)。这里 first 是 unique 返回的逻辑末尾，last 是 v.end()，正好覆盖整个尾段。

不相邻的重复不会被合并

同一个数据 [1, 2, 1]，不排序直接调用 unique 会怎样？

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {1, 2, 1};
    auto la = unique(a.begin(), a.end());     // 只合并相邻的相等元素
    cout << "直接 unique：逻辑长度 = " << (la - a.begin()) << "，有效前缀：";
    for (auto it = a.begin(); it != la; it++) cout << *it << ' ';
    cout << '\n';

    vector<int> b = {1, 2, 1};
    sort(b.begin(), b.end());                 // 排成 1 1 2
    auto lb = unique(b.begin(), b.end());
    b.erase(lb, b.end());
    cout << "先排序再处理：size = " << b.size() << "，内容：";
    for (int i = 0; i < (int)b.size(); i++) cout << b[i] << ' ';
    cout << '\n';
    return 0;
}

输出：

直接 unique：逻辑长度 = 3，有效前缀：1 2 1 
先排序再处理：size = 2，内容：1 2 

两个程序完成的是不同任务：前者的任务叫“压缩相邻重复”，后者的任务叫“全体数值去重”。unique 本身只负责前者，排序是为了把后者变成前者。

综合：10 个整数去重

把数据量放大一点，读入 n 个整数，按从小到大的顺序输出去重后的结果：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a.begin(), a.end());
    auto last = unique(a.begin(), a.end());
    a.erase(last, a.end());

    cout << a.size() << '\n';
    for (int i = 0; i < (int)a.size(); i++) {
        if (i > 0) cout << ' ';
        cout << a[i];
    }
    cout << '\n';
    return 0;
}

输入：

10
1 2 9 1 2 9 8 7 6 8

输出：

6
1 2 6 7 8 9

输入里的 10 个数排序后是 1 1 2 2 6 7 8 8 9 9，去重后剩下 6 个：1 2 6 7 8 9。vector<int> a(n); 表示创建有 n 个元素的 vector（这里 n 由输入决定），然后逐个读入。

什么时候选它、哪里容易错

先纠正两个关于 unique 的常见错误说法。

错误说法一：“使用 unique 前必须先排序”。 排序不是调用 unique 的前提，unique 的语义就是合并相邻的相等元素，不排序也能正常调用。只有当你的任务是“把所有重复值都去掉”时，才需要先排序把相等的值聚到一起——这一步是你为了完成任务自己加的，不是 unique 的要求。前面的 [1,2,1] 例子正好说明了两者的区别。

错误说法二：“unique 把重复的元素放到数组最后面藏起来了”。 unique 只保证返回位置之前的有效前缀是正确的，返回位置之后的内容标准没有规定，既不是“重复值集合”，也不保证数量或顺序。看本页实测：[1,1,2,2,2,3] 处理后容器里是 1 2 3 2 2 3，尾段是 2 2 3，并不是“被去掉的重复值”。所以不要读取尾段，也不要打印它当成结果。

其他容易错的地方：

• 只调用 unique 而忘记 erase：size() 不变，后面按 size() 遍历就会读到无效的尾段。要么用 last 控制遍历终点，要么补上 erase。
• 逻辑长度不是 size()：要得到保留下来的元素个数，用 last - v.begin()；size() 只有在 erase 之后才等于它。
• erase 的写法：v.erase(last, v.end()) 两个参数构成一个区间，删掉的是 [last, end)。写成 v.erase(last) 只会删掉一个元素。
• 复杂度：sort 是 O(n log n)，unique 是 O(n)（顺着走一遍），erase 删除尾段时元素本身不需要搬动，但整体任务的开销由排序决定。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），请先手推出输出，再运行核对：

vector<int> v = {5, 5, 5, 7, 7, 6};
auto last = unique(v.begin(), v.end());

cout << (last - v.begin()) << '\n';

第 2 题：修改代码

下面这段片段只做了相邻去重，对 [1, 2, 1] 一个元素都去不掉。请把它改成“全体数值去重”的程序，让输出变成 2 和 1 2：

vector<int> v = {1, 2, 1};

auto last = unique(v.begin(), v.end());
v.erase(last, v.end());          // 还缺一步，想想缺什么

cout << v.size() << '\n';
for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';

验证条件：先说出缺的那一步为什么必须放在 unique 之前，再运行核对。

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {5, 5, 5, 7, 7, 6};
    auto last = unique(v.begin(), v.end());

    cout << (last - v.begin()) << '\n';
    return 0;
}

3

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 2, 1};

    sort(v.begin(), v.end());
    auto last = unique(v.begin(), v.end());
    v.erase(last, v.end());

    cout << v.size() << '\n';
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';
    cout << '\n';
    return 0;
}

2
1 2 

立即练习

做完后请说明：如果把题目改成“按输入顺序输出，重复的只保留第一次出现的那个”，sort 还能用吗？为什么？