C++ unique函数去重原理_C++ STL去除相邻重复元素的实现

unique函数去除相邻重复元素并返回新逻辑结尾迭代器，需配合erase才能真正删除冗余；其原理为双指针移动非重复元素至前部，常与sort结合实现完全去重。

在C++ STL中，unique 函数用于去除相邻的重复元素，但它并不会真正“删除”元素，而是将不重复的部分向前移动，并返回一个指向新逻辑结尾的迭代器。理解其原理对正确使用该函数至关重要。

unique函数的基本作用

std::unique 定义于 <algorithm> 头文件中，它的主要功能是遍历区间，移除连续相等的元素，只保留每组相同元素中的第一个。它只对相邻重复项起作用，不会处理非连续的重复值。

例如：

原始序列：1, 2, 2, 3, 3, 3, 2, 2
调用 unique 后：1, 2, 3, 2, ?, ?, ?, ?（? 表示无意义数据）

去重的实现原理

unique 的内部实现采用双指针思想：

立即学习“C++免费学习笔记（深入）”；

• 使用一个读指针遍历整个容器
• 使用一个写指针记录去重后应存放的位置
• 从第二个元素开始比较当前元素是否与前一个不同
• 若不同，则通过写指针将其复制到结果区域，并移动写指针

初始时，写指针和读指针都指向首元素。读指针逐个前进，当发现当前元素不同于前一个“保留”的元素时，就把它写入写指针位置。

伪代码示意：

STORYD

帮你写出让领导满意的精美文稿

164

查看详情

Iterator write = begin;
for (Iterator read = begin + 1; read != end; ++read) {
    if (*read != *(write)) {
        ++write;
        *write = *read;
    }
}
return ++write; // 返回新的逻辑结尾

如何真正删除冗余元素

unique 返回的是新结尾迭代器，原容器大小不变。要真正缩短容器，必须显式调用容器的 erase 方法：

vec.erase(std::unique(vec.begin(), vec.end()), vec.end());

这种组合称为“erase-unique 惯用法”，是 STL 中常见的模式。

注意：使用 unique 前通常需要先排序，否则只能去除连续重复项。例如想完全去重，应先调用 sort：

std::sort(vec.begin(), vec.end());
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());

基本上就这些。unique 不改变容器内存布局，仅重排有效数据，高效且通用，配合 erase 才能完成真正的去重操作。

以上就是C++ unique函数去重原理_C++ STL去除相邻重复元素的实现的详细内容，更多请关注php中文网其它相关文章！