C++去重函数unique超详解｜有序数组去重必学

unique函数可以删除有序数组中的重复元素， 是 C++ 标准库<algorithm>中的函数。

注意：使用它的前提是有序数组，就是排好序的数组。

unique的意思是“独一无二的”。uni其实就是one的变形，que就是汉语拼音“缺”，所以它的意思就是哥们就哥儿一个，缺少兄弟姐妹。

一、函数原型

这玩艺叫函数模板，比较复杂，以老金的智慧，也解释不清楚，大概看一眼就行了。

// 默认使用 operator== 比较template<classForwardIt>ForwardItunique(ForwardIt first,ForwardIt last);// 使用自定义二元谓词 predtemplate<classForwardIt,classBinaryPredicate>ForwardItunique(ForwardIt first,ForwardIt last,BinaryPredicate pred);

有志于放开手脚好好研究一番的朋友，观迎参观权威文档：cppreference.com–std::unique

只需要知道，这东西就是个像PPT模板一样。它就是给咱的一套模具，让咱不用管那些外壳形状之类的事情，更加专注于内容。

有了这个模板，函数功能就会变强。

强在哪里呢？

正常我们写一个函数，都要预先指定其参数类型，函数返回值。这个参数类型和函数返回值必须是具体的、明确的，因此一个函数只能处理一种类型的数据，返回一种类型的返回值。

比如下面这个求和函数，只能用来求int类型的变量的和。

intadd(inta,intb){returna+b;}

有了函数模板就不一样了，它不预先指定函数的参数类型、返回值，而是随便用一串字符表示这是一个对象的类型（至于是什么类型我不管）。这串很随便的字符只起到“占位符”的作用，通俗来讲就是占着茅坑不拉屎。

等到实际调用函数的时候，系统（编辑器）会根据你传入实际参数的数据类型把这些占位符替换掉，然后再去执行。如此一来，我们只需要编写一个函数，就可以处理不同类型的参数，输出不同类型的返回值。

这就像同一个PPT模板，你编辑时可以敲入任何类型的内容一样。

上面的模板是C++标准库为咱定制好的，咱直接拿过来用即可，其实咱也是可以自己写模板的。

二、函数说明

• 只移除相邻重复元素：如果重复元素不相邻，不会被移除。因此通常先对序列排序。
• 不真正删除元素：本质上只是移动元素，即将不重复元素前移，所以容器大小不变。如果要彻底删除元素，需要配合容器的erase方法物理删除。
• 返回值：指向新的逻辑末尾（第一个“无用”元素的位置）。
• 复杂度：对于非空区间：线性时间，恰好( l a s t − f i r s t ) − 1 (last - first) - 1(last−first)−1次比较。

三、函数用法

3.1 普通有序数组去重

#include<iostream>#include<algorithm>intmain(){intarr[]={1,1,2,2,2,3,4,4,5};intn=sizeof(arr)/sizeof(arr[0]);// unique 将不重复元素移到前面，返回新末尾指针int*new_end=std::unique(arr,arr+n);// 输出逻辑上的去重结果for(int*p=arr;p!=new_end;++p)std::cout<<*p<<" ";// 输出: 1 2 3 4 5std::cout<<std::endl;// 实际数组内容（后面元素未定义，通常保持原样）// arr 现在可能为 {1,2,3,4,5,3,4,4,5}return0;}

3.2 vector去重

因为vector是动态数组(就是长度可以动态调整的数组)，所以去重后可以采用erase方法彻底删除重复元素。

#include<vector>#include<algorithm>std::vector<int>v={1,1,2,2,3,3,3};autoit=std::unique(v.begin(),v.end());v.erase(it,v.end());// 物理删除重复元素// v 变为 {1,2,3}

有关vector的说明参见：cppreference.com–std::vector