526互联

C++ STL Unique 底层实现原理 - 代码

发布时间 2023-04-08 01:39:14作者: 攻城狮小Liu

事实上在搜STL Unique的时候发现网上绝大部分都是错的，包括unique元素提到前面或者非unique元素提到后面。

Unique前后里面的元素是不一样的！！！

Unique前后里面的元素是不一样的！！！

Unique前后里面的元素是不一样的！！！

我们来看代码

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

class Solution
{
public:
    int removeDuplicates(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++)
        {
            cout << "#" << nums[i] << endl;
        }
        auto last = unique(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++)
        {
            cout << "@" << nums[i] << endl;
        }
        nums.erase(last, nums.end());
        return nums.size();
    }
};

int main()
{
    vector<int> nums;
    nums.push_back(1);
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(2);
    nums.push_back(3);
    nums.push_back(5);
    nums.push_back(5);
    Solution s;

    cout << s.removeDuplicates(nums);
}

输出结果：

#1
#1
#2
#2
#3
#5
#5
@1
@2
@3
@5
@3
@5
@5
4

划重点，最后三个元素，3,5,5

 

再看一个新的：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int myints[] = {1, 2, 3, 1, 1};
    int len = sizeof(myints) / sizeof(int);
    vector<int> vec(myints, myints + len);
    sort(vec.begin(), vec.end());
    for (int x : vec)
        cout << x << ",";
    cout<<endl;
	unique(vec.begin(), vec.end()), vec.end();
    for (int x : vec)
        cout << x << ",";
    return 0;
}

　　

结果：

 

 

 

得出结论：

事实上是把unique的元素覆盖掉前n个，后面的原来是什么就还是什么

 

看源码：STL Unqiue

这段代码是STL中unique函数的实现代码，其作用是去除一个序列中的连续重复元素，保留第一个出现的元素。代码中包含了一些概念检查的语句。

首先，函数模板unique的定义使用了typename关键字，表示__first和__last是一种类型，而这个类型要满足_Mutable_ForwardIteratorConcept的要求，也就是满足前向迭代器的要求。此外，还要求这个类型的value_type满足_EqualityComparableConcept的要求，即可比较相等。

在函数实现的开头，我们可以看到几个概念检查的语句。其中__glibcxx_function_requires和__glibcxx_requires_valid_range是一些特殊的宏，它们的作用是对参数类型进行概念检查。如果参数类型不满足概念要求，编译器就会报错，从而避免在编译时出现一些潜在的问题。这些概念要求可以在头文件中定义，如上文所示。

最后，代码调用了STL中的__unique函数，该函数是unique函数真正的实现。该函数接受三个参数：序列的起始和结束迭代器，以及一个比较相等的函数对象。该函数对象的作用是用于判断两个元素是否相等。最后，函数返回去重后的序列的尾后迭代器。

 

 再往下：

  1. 首先调用STL中的__adjacent_find函数，查找序列中第一个相邻的重复元素，将__first指向该元素的第一个出现位置。
  2. 如果序列中没有重复元素，直接返回__last。
  3. 否则，从__first+1开始，遍历序列中的所有元素，依次判断当前元素是否与前一个元素相等，如果相等，则跳过该元素，否则将该元素复制到结果序列中，并将结果序列的指针__dest向前移动一位。
  4. 最后返回去重后的序列的尾后迭代器。