自己写的 基于map的离散化模板类

 1 #include<iostream>
 2 using namespace std;
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<map> 
 7 /*
 8 基于map
 9 复杂度 nlogn
10 查询复杂度 logn 
11 需要排序,所以需要重载 < ,需要algorithm 
12 */ 
13 template<class T>
14 class Disperse{
15     public:
16         map<T,int>* maps;
17         int* trans_array;
18         int init_num;//离散化初始值 
19         int max_num;//离散化之后的最大数 
20         T *a; 
21         
22         //b为需要离散化的数组,n为数组大小
23         //数组从0开始,init_n为离散化初始值,默认为0 
24         void Creat(const T b[],int n,int init_n=0){
25             a=new T[n];
26             memcpy(a,b,sizeof(T)*n);
27             maps=new map<T,int>();
28             maps->clear();
29             sort(a,a+n);
30             max_num=init_n-1;
31             init_num=init_n;
32             for(int i=0;i<n;++i){
33                 if(i!=0&&a[i]==a[i-1])
34                     continue;
35                 (*maps)[a[i]]=++max_num;
36             }
37         }
38         
39         int get(const T& p){
40             return (*maps)[p];
41         }
42 };
43 int a[]={9000000,8000000,7000000,6000000,5000000,4000000,3000000,2000000,2000000,3000000,2000000,1000000};
44 
45 Disperse<int> dis;
46 int main(){
47     dis.Creat(a,12,1);//离散化a数组的12个元素,离散标号最小为1
48     for(int i=0;i<12;i++){
49         cout<<a[i]<<" "<<dis.get(a[i])<<endl;
50     } 
51     return 0;
52 }