利用STL离散化处理数据（unique）

心已赠人 2023-07-05 14:48 9阅读 0赞

# 0x00 使用说明 #

离散化可以很好的减小空间复杂的度，
    它适用于数据中有大量重复的值（或则数据之间跨度特别大），
    使用时可以只需要其中一个。
    下面的离散化处理只是对于有大量重复值的情况。

先数据存入容器对象`vector<int> vec`，  
**保证使用`unique`前 数据是有序的。**

### 1. 先使用`sort`排序： ###

sort(vec.begin(),vec.end());

### 2. 使用`unique`离散化： ###

此时`unique`离散化处理并不是将重复的元素删去，  
而是将后面不重复的数来覆盖重复了的数，  
可以看下面代码的运行结果（或者参考：[cppreference][]）,  
**unique返回值为目标序列最后一个需要的值的地址（或迭代器对象）**,  
可以减去首地址转化一下

int cnt = unique(vec.begin(),vec.end())-vec.begin();

### 3. 删除不需要部分 ###

vec.erase(vec.begin()+cnt,vec.end());

# 0x01 测试代码 #

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        
        int a[8] = {
        1,5,3,2,3,2,7,90};
        sort(a,a+8);
        vector<int>vec(a,a+8);
    
        cout<<"使用unique前:"<<endl;
        for(int i = 0; i < vec.size(); i++)
        {
        
            cout<<vec[i]<<" ";
        }
        cout<<endl;
    
        /*
          使用unique前需要保证数据是有序的，
          unique返回的是不重复序列最后的地址（迭代器形式），
          unique只是将重复的元素的位置用后面与它不同的元素来覆盖
        */
        int cnt = unique(vec.begin(),vec.end())-vec.begin();
    
        cout<<"目标序列长度："<<cnt<<endl;
        cout<<"使用unique后:"<<endl;
        for(int i = 0; i < vec.size(); i++)
        {
        
            cout<<vec[i]<<" ";
        }
        cout<<endl;
        cout<<"使用erase后:"<<endl;
        vec.erase(vec.begin()+cnt,vec.end());
        for(int i = 0; i < vec.size(); i++)
        {
        
            cout<<vec[i]<<" ";
        }
        cout<<endl;
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70]

[cppreference]: http://www.inf.pucrs.br/~flash/lapro2ec/cppreference/w/cpp/algorithm/unique.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200215203627265.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo,size_16,color_FFFFFF,t_70