使用STL对整数向量去重排序

题目

使用STL对整数向量去重排序

信息

• 类型：问答
• 难度：⭐

考点

vector容器使用,算法库应用,迭代器操作

快速回答

使用STL对整数向量去重排序的步骤如下：

1. 使用std::sort对向量排序
2. 使用std::unique将重复元素移到末尾
3. 使用erase方法删除重复元素

示例代码：

std::vector vec = {3, 1, 2, 2, 4, 3};
std::sort(vec.begin(), vec.end());
auto last = std::unique(vec.begin(), vec.end());
vec.erase(last, vec.end());

问题背景

在实际开发中经常需要处理数据去重和排序的需求，例如处理用户输入或数据库查询结果。STL提供了高效的工具链来实现这一功能。

解决方案

核心步骤：

1. 排序：使用std::sort将元素升序排列
2. 去重：使用std::unique将相邻重复元素移到容器末尾
3. 删除：使用向量的erase方法移除重复元素

完整代码示例

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

int main() {
    std::vector<int> numbers = {5, 2, 2, 8, 3, 5, 1};

    // 1. 排序
    std::sort(numbers.begin(), numbers.end());

    // 2. 去重（返回新逻辑结尾的迭代器）
    auto unique_end = std::unique(numbers.begin(), numbers.end());

    // 3. 删除重复元素
    numbers.erase(unique_end, numbers.end());

    // 输出结果：1 2 3 5 8
    for (int num : numbers) {
        std::cout << num << " ";
    }
    return 0;
}

原理说明

• std::sort：使用IntroSort算法（快速排序+堆排序混合），平均时间复杂度O(n log n)
• std::unique：遍历容器，将不重复元素前移，返回去重后的新结尾迭代器。要求容器已排序才能正确去重
• erase：根据迭代器范围删除元素，时间复杂度O(n)

最佳实践

• 对自定义类型去重时，需重载operator<或提供自定义比较函数
• 使用C++11的auto关键字简化迭代器声明
• 若需保留原向量，可先复制：std::vector<int> temp = original;

常见错误

• 忘记先排序导致std::unique失效（只能去除相邻重复）
• 未处理std::unique的返回值直接使用容器
• 误用resize代替erase导致末尾残留数据

扩展知识

• 高效替代方案：使用std::set或std::unordered_set直接去重，但会丢失原顺序
• C++20新特性：std::ranges::sort和std::ranges::unique提供更简洁语法
• 性能对比：对于10万随机整数，此方案比循环遍历快5-8倍