高速で省メモリな複数配列のソート

Question

2つのキー配列と値配列をキー配列でソートしたいです。
なるべく余分なメモリを確保せずに高速にソートしたいです。
ソート部分は自分で書かずにstd::sortなどをつかいたいです。
現在は構造体の配列に詰め直してからソートする実装になっているので入力と同じサイズのワーキングスペースを使っています。
うまい方法はないでしょうか？

//sample.cpp
template <typename T> sort(const int flag,int *k1,int *k2,T *v,const int n){
    // flagによってk1とk2のどちらをプライマリキーとするか制御してソート
    // 不安定なソートでもよい
}
int main(){
    int  keys1[] = {0 , 4 , 5 , 2 , 2 , 2};
    int  keys2[] = {1 , 5 , 2 , 4 , 0 , 3};
    float vals[] = {1 , 2 , 3 , 4 , 5 , 6};
    sort<float>(keys1,keys2,vals,6);
    // 期待する出力
    // keys1 : 0 2 2 2 4 5
    // keys2 : 1 0 3 4 5 2
    // vals   : 1 5 6 4 2 3
}

// 現在の実装
// ワーキングスペースとして入力と同じサイズの配列を用いてしまっている
template <typename T> struct k1_k2 {
    int k1;
    int k2;
    T val;
    bool operator<(const k1_k2<T> &obj){
        return k1 < obj.k1 || (k1 == obj.k1 && k2 < obj.k2);
    }
    bool operator>(const k1_k2<T> &obj){
        return k1 > obj.k1 || (k1 == obj.k1 && k2 > obj.k2);
    }
};
template <typename T> struct k2_k1 {
    int k1;
    int k2;
    T val;
    bool operator<(const k2_k1<T> &obj){
        return k2 < obj.k2 || (k2 == obj.k2 && k1 < obj.k1);
    }
    bool operator>(const k2_k1<T> &obj){
        return k2 > obj.k2 || (k2 == obj.k2 && k1 > obj.k1);
    }
};

template <typename T> sort(const int flag,int *k1,int *k2,T *v,const int n){
    if(flag & K1_K2){
        vector< k1_k2<T> > vec(n);
        for(int i=0 ; i<n ; ++i){ vec[i].k1 = k1[i]; vec[i].k2 = k2[i]; vec.val[i] = v[i]; }
        if(flag & ASC){
            std::sort(vec.begin(),vec.end(),less< k1_k2<T> >());
        }else{
            std::sort(vec.begin(),vec.end(),greater< k1_k2<T> >());
        }
    }else{
        vector< k2_k1<T> > vec(n);
        for(int i=0 ; i<n ; ++i){ vec[i].k1 = k1[i]; vec[i].k2 = k2[i]; vec.val[i] = v[i]; }
        if(flag & ASC){
            std::sort(vec.begin(),vec.end(),less< k2_k1<T> >());
        }else{
            std::sort(vec.begin(),vec.end(),greater< k2_k1<T> >());
        }
    }
}

Answer 1

標準関数は，よく使われると思われるプログラムのパーツを作っておくことで，
プログラミングの効率を上げるためにあります．
このような特殊な事情に配慮できるような関数は，
標準の形に合わせるか，通常自分で作らなければなりません．
高速なソートプログラムを書くのは大変なので，
データ構造をstd::sortに合うように変えるべきかと思います．
配列ではなくvectorなどでもstd::sortは使えますが，少し呼び出し方が変わります．

#include <iostream>

struct data_t {
    int key1;
    int key2;
    float value;
};

bool cmp(const data_t& left, const data_t& right) {
    return (left.key1 == right.key1) ? (left.key2 < right.key2) : (left.key1 < right.key1);
}

int main(){
    struct data_t data[] = {{0, 1, 1}, {4, 5, 2}, {5, 2, 3}, {2, 4, 4}, {2, 0, 5}, {2, 3, 6}};
    std::sort(data, data + 6, cmp);
    for (int i = 0; i < 6; i++)
        std::cout << "{" << data[i].key1 
                  << "," << data[i].key2 
                  << "," << data[i].value << "}"
                  << std::endl;

    return 0;
}

Comments

[Chironian]

複数の値を使って大小比較する時、std::tieが便利ですよ。
ここにも良くいらっしゃるyohhoyさんのサイトに分かりやすい解説があります。
http://d.hatena.ne.jp/yohhoy/20120218/p1

展開型を見ると==を使ってないので違うような気がしてしまいますが、>だけを使うためにdon't careをうまいこと使っているだけで、期待通りの大小比較になってます。

[KenTerada]

普段はC++を使っていないので，勉強になりました！ありがとうございます．

[Chironian]

いえいえ、私もつい最近std::tieを知って衝撃を受けたばかりです。