2012/10/20

C++で2種類のコンテナを同時にソートする

C++でデータを扱っていると,2種類のコンテナを同時にソートしたい場合が時々出てくる.どういうことかというと,
int main() {
    int keys[]   = {5, 3, 1, 2, 4};
    int values[] = {1, 2, 3, 4, 5};
    aoba::sort_by_key(keys, keys+5, values);
    for(int i=0; i<5; ++i) {
        std::cout << keys[i] << " ";   // 1 2 3 4 5
    }
    std::cout << std::endl;
    for(int i=0; i<5; ++i) {
        std::cout << values[i] << " "; // 3 4 2 5 1
    }
    std::cout << std::endl;
    return 0;
}
と,片方のソート結果を元にもう片方をソートするような感じ.これはCUDAライブラリであるthrustに標準搭載されており,sort_by_keyという名前がついている.

さて,こういうときに一からソートアルゴリズムを組み直すなんてことは馬鹿らしい.じゃあどうするか.基本的には既存のstd::sortに渡すイテレータを変形することで,なんとか解決しようとする.そうなると,boostにzip_iteratorが存在することに気付けば,イテレータをboost::tupleの組で表現することによって,まとめてソートさせればいいような気がしてくる.こんな風に:
std::sort(
    boost::make_zip_iteator(
        boost::make_tuple(
            keys_first, values_first)),
    boost::make_zip_iterator(
        boost::make_tuple(
            keys_last, values_last)),
    compare_functor());
しかし,そうは問屋が降ろさない.何故なら,boost::zip_iteratorはWritableではない.これはソートアルゴリズムの要件を満たしていないため,適用させようとしてもコンパイルエラーが発生してしまう!

それじゃあどのようにして解決するかというと,一番楽な方法としてはWritableなコンセプトを満たしたzipイテレータを新しく作ってやって,それを用いてstd::sortを行うのがいい.とはいっても,C++でそれをやるのは若干手間のかかる作業になる.具体的にはこんな感じで実装した:
実装したといっても,実際には『Sorting two arrays simultaneously』の内容を若干手直しするだけなので基本的にはそんなに大変じゃないし,ただ利用するぶんには単純にsort_by_key()を呼び出すだけでよい.

しかし,なんでこんなにC++は行数が多くなってしまうのか.haskellなんか一行で済むのに.