2つのキー配列と値配列をキー配列でソートしたいです。
なるべく余分なメモリを確保せずに高速にソートしたいです。
ソート部分は自分で書かずにstd::sortなどをつかいたいです。
現在は構造体の配列に詰め直してからソートする実装になっているので入力と同じサイズのワーキングスペースを使っています。
うまい方法はないでしょうか?
C++
1//sample.cpp 2template <typename T> sort(const int flag,int *k1,int *k2,T *v,const int n){ 3 // flagによってk1とk2のどちらをプライマリキーとするか制御してソート 4 // 不安定なソートでもよい 5} 6int main(){ 7 int keys1[] = {0 , 4 , 5 , 2 , 2 , 2}; 8 int keys2[] = {1 , 5 , 2 , 4 , 0 , 3}; 9 float vals[] = {1 , 2 , 3 , 4 , 5 , 6}; 10 sort<float>(keys1,keys2,vals,6); 11 // 期待する出力 12 // keys1 : 0 2 2 2 4 5 13 // keys2 : 1 0 3 4 5 2 14 // vals : 1 5 6 4 2 3 15}
C++
1// 現在の実装 2// ワーキングスペースとして入力と同じサイズの配列を用いてしまっている 3template <typename T> struct k1_k2 { 4 int k1; 5 int k2; 6 T val; 7 bool operator<(const k1_k2<T> &obj){ 8 return k1 < obj.k1 || (k1 == obj.k1 && k2 < obj.k2); 9 } 10 bool operator>(const k1_k2<T> &obj){ 11 return k1 > obj.k1 || (k1 == obj.k1 && k2 > obj.k2); 12 } 13}; 14template <typename T> struct k2_k1 { 15 int k1; 16 int k2; 17 T val; 18 bool operator<(const k2_k1<T> &obj){ 19 return k2 < obj.k2 || (k2 == obj.k2 && k1 < obj.k1); 20 } 21 bool operator>(const k2_k1<T> &obj){ 22 return k2 > obj.k2 || (k2 == obj.k2 && k1 > obj.k1); 23 } 24}; 25 26template <typename T> sort(const int flag,int *k1,int *k2,T *v,const int n){ 27 if(flag & K1_K2){ 28 vector< k1_k2<T> > vec(n); 29 for(int i=0 ; i<n ; ++i){ vec[i].k1 = k1[i]; vec[i].k2 = k2[i]; vec.val[i] = v[i]; } 30 if(flag & ASC){ 31 std::sort(vec.begin(),vec.end(),less< k1_k2<T> >()); 32 }else{ 33 std::sort(vec.begin(),vec.end(),greater< k1_k2<T> >()); 34 } 35 }else{ 36 vector< k2_k1<T> > vec(n); 37 for(int i=0 ; i<n ; ++i){ vec[i].k1 = k1[i]; vec[i].k2 = k2[i]; vec.val[i] = v[i]; } 38 if(flag & ASC){ 39 std::sort(vec.begin(),vec.end(),less< k2_k1<T> >()); 40 }else{ 41 std::sort(vec.begin(),vec.end(),greater< k2_k1<T> >()); 42 } 43 } 44}
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2015/10/30 00:57
2015/10/30 05:43
2015/10/30 10:39