C++ unique 去重

在 C++ 中，我们可以使用 <algorithm> 头文件中的 std::unique() 函数来去除容器中相邻的重复元素。不过它的去重方式比较特殊，并不会直接把多余的元素从容器里删掉，下面我们就来看看它的具体原理与用法。

std::unique() 的去重原理

很多初学的小伙伴看到 unique（意为 “唯一的”）这个名字，会以为只要调用一次 std::unique()，容器里所有重复的元素就会被自动删干净，容器长度也会跟着变短。实际上，这样理解是不正确的。

在使用 std::unique() 时，我们需要先搞清楚它的以下 2 个特点：

• 只去除相邻的重复元素：它只会对比紧挨着的两个元素。比如 20, 20 连在一起时会把后面重复的 20 去掉，但如果写成 20, 30, 20 中间隔了别的数，它是不会去重的。
• 不会直接改变容器的长度：std::unique() 只接收区间边界，并不持有容器本身，因此不能直接缩短容器长度。它的实际做法是把不重复的元素依次往前挪动覆盖，最后返回一个指向 “不重复元素末尾后一格” 的新位置。

语法：

auto newEnd = std::unique(first, last);

说明：

first 和 last 分别表示去重范围的起始与结束边界迭代器。返回值 newEnd 也是一个迭代器，指向去重后 “最后一个有效元素后面的位置”，也就是新的结束边界。

从 first 到 newEnd 之间的元素就是去重后的有效结果，而从 newEnd 到原容器 end() 之间的位置，则属于不再使用的尾部残留空间。

示例 1：单独调用 std::unique()

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> nums = {10, 20, 20, 30, 30};

    // 将相邻不重复的元素移到前面，返回新边界
    auto newEnd = std::unique(nums.begin(), nums.end());

    std::cout << "容器总长度：" << nums.size() << '\n';
    std::cout << "有效元素：";
    for (auto it = nums.begin(); it != newEnd; ++it) {
        std::cout << *it << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

容器总长度：5
有效元素：10 20 30

分析：

从运行结果可以看出，nums.size() 打印出来的总长度依然是 5，并没有变成 3。为了方便直观理解，我们可以把调用前后的位置变化看成下面这样：

调用前：[10, 20, 20, 30, 30]
调用后：[10, 20, 30] | [?, ?]

std::unique() 把不重复的 10、20、30 依次挪到了前 3 个位置，并将返回值 newEnd 指向竖线后面第 1 个 ? 的位置（即下标 3）。

因此从 nums.begin() 遍历到 newEnd，打印出来的就是有效结果 10 20 30。至于 newEnd 后面残留的两个位置，里面留着什么旧值都有可能，我们不能再把它们当作有效元素读取。

vector 完整去重步骤

弄清楚了 std::unique() 的原理之后，如果我们要对一个顺序打乱的 vector 进行彻底去重，可以按以下 3 个步骤依次完成：

• 先排序：调用 std::sort() 对整个容器进行排序，让所有数值相同的元素全部紧挨在一起。
• 再去重：调用 std::unique() 把相邻不重复的元素移到容器前面，并拿到返回的新边界迭代器 newEnd。
• 擦除尾部残留：调用容器自带的 erase() 成员函数，把从 newEnd 到 end() 之间残留的尾部元素真正删掉。

示例 2：vector 完整去重

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> nums = {30, 10, 20, 10, 30, 20};

    // 1. 先排序，使相同元素相邻
    std::sort(nums.begin(), nums.end());

    // 2. 将不重复元素移到前面
    auto newEnd = std::unique(nums.begin(), nums.end());

    // 3. 擦除从 newEnd 到末尾的残留元素
    nums.erase(newEnd, nums.end());

    std::cout << "去重后的长度：" << nums.size() << '\n';
    for (int n : nums) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

去重后的长度：3
10 20 30

分析：

在这个例子中，前两步完成排序和前移后，第 3 步调用 nums.erase(newEnd, nums.end()) 把尾部多余的位置真正删掉了。最终 nums 只保留了不重复的 10 20 30，真实长度也从 6 缩减成了 3。

对于上面的第 2 步和第 3 步，下面 2 种写法是等价的。

// 写法 1
auto newEnd = std::unique(nums.begin(), nums.end());
nums.erase(newEnd, nums.end());

// 写法 2
nums.erase(std::unique(nums.begin(), nums.end()), nums.end());

其中，写法 1 把去重和擦除分成两行写，步骤清晰，非常适合初学者理解。在实际开发中，很多程序员也习惯采用写法 2 把它们合并成一行。

如果我们在去重前漏掉了第 1 步的排序，会发生什么结果呢？下面我们来看一个例子。

示例 3：未排序直接调用 unique()

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    // 两个 10 中间隔了一个 20
    std::vector<int> nums = {10, 20, 10};

    auto newEnd = std::unique(nums.begin(), nums.end());
    nums.erase(newEnd, nums.end());

    for (int n : nums) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

10 20 10

分析：

在 {10, 20, 10} 中，虽然有两个 10，但中间隔了一个 20，并不相邻。std::unique() 先对比第 1 个 10 和 20 不相等，再对比 20 和第 2 个 10 也不相等，于是认为没有相邻重复项，原样保留了 10 20 10。

使用 std::set 自动去重

除了使用 sort + unique + erase 组合对 vector 原地去重之外，前面学过的 set 容器本身就具备 “自动去重、自动排序” 的特点。

如果数据量不算特别大，或者我们在收集数据的过程中就希望自动过滤掉重复项，也可以直接把数据放进 std::set 中。

示例 4：使用 std::set 去重

#include <iostream>
#include <set>
#include <vector>

int main() {
    std::vector<int> nums = {30, 10, 20, 10, 30, 20};

    // 通过起止迭代器初始化 set
    std::set<int> uniqueNums(nums.begin(), nums.end());

    for (int n : uniqueNums) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

10 20 30

分析：

在这个例子中，我们直接传入 nums 的起止迭代器来初始化集合 uniqueNums。重复的 10、20、30 在插入集合时就会被自动过滤掉，并且元素会自动按从小到大排好序。

在实际开发中，如果数据原本就在 vector 里，且去重后还需要使用下标 [] 访问，我们优先采用 sort + unique + erase 原地去重。这种做法内存连续，运行效率更高。如果需要一边动态插入数据、一边保持不重复，使用 std::set 会更加省事。