【C++】STLを利用したインデックスソート

STLのsortアルゴリズムでは、引数に与えたシーケンスそのものを変更してしまいます。そこで、シーケンスの値に応じてインデックスソートを行う方法を調べてみましたので、下記にまとめておきます。

考え方としては、STLのsortアルゴリズムを利用して、インデックスの値の配列をソートするのですが、その際の比較関数として、元のシーケンスの値を利用するというものです。具体的には、比較関数（オブジェクト）を、次のように定義します。

template<class Ran>
class IndexSortFunctor {
public:
    explicit IndexSortFunctor(const Ran iter_begin_, const Ran iter_end_) : itbg(iter_begin_), ited(iter_end_) {}
    ~IndexSortFunctor() {}
    bool operator()(const size_t a, const size_t b) const {
        return *(itbg + a) < *(itbg + b);
    }

    protected:
    private:
    const Ran itbg;
    const Ran ited;
};

呼び出し元は、たとえば、ソート対象シーケンスをvector（変数名target）として、さらにインデックスの番号を格納したvector（変数名tidx）を用意して、次のように呼び出します。

std::sort(tidx.begin(), tidx.end(), IndexSortFunctor<std::vector<int>::iterator >(target.begin(), target.end() ) );

このようにすると、targetの内容を見て、tidxをソートしてくれるので、結果としてインデックスソートを得ることができます。

実際には、このまま使うとテンプレートクラスのテンプレート引数の記述が面倒なので、下記のようなテンプレート関数を作っておきます（テンプレート関数は関数の呼び出し引数からテンプレート引数を推測してくれることを利用します）。

template<class Ran>
inline IndexSortFunctor<Ran> IndexSortCmp(const Ran iter_begin_, const Ran iter_end_)
{
    return IndexSortFunctor<Ran>(iter_begin_, iter_end_);
}

そうすると、下記のようなサンプルプログラムでインデックスソートを得ることができます。

#include <algorithm>
#include <vector>
#include <iostream>

/** インデックスソート条件関数オブジェクト
* 前提条件
* シーケンスはランダムアクセス反復子によりアクセス可能
*/
template<class Ran>
class IndexSortFunctor {
public:
    /** コンストラクタ
    *
    * @param iter_begin_ シーケンス先頭のランダムアクセス反復子
    * @param iter_end_ シーケンス終端の次のランダムアクセス反復子
    */
    explicit IndexSortFunctor(const Ran iter_begin_, const Ran iter_end_) : itbg(iter_begin_), ited(iter_end_) {}

    /** デストラクタ
    */
    ~IndexSortFunctor() {}

    /** 関数呼び出し
    * パラメータは、[]演算子の引数を想定
    * 必要があればitedを使って範囲チェックを行うことも可能
    * （ここでは未実装）
    */
    bool operator()(const size_t a, const size_t b) const {
        return *(itbg + a) < *(itbg + b);
    }

    protected:
    private:
    /** インデックスソート対象のコンテナ
    */
    const Ran itbg;
    const Ran ited;
};

/** インデックスソート用関数
*/
template<class Ran>
inline IndexSortFunctor<Ran> IndexSortCmp(const Ran iter_begin_, const Ran iter_end_)
{
    return IndexSortFunctor<Ran>(iter_begin_, iter_end_);
}

int main()
{
    // サンプル用データの準備
    const int num = 10;

    std::vector<int> target(num); // vectorの場合
    //int * target = new int [num]; // 配列の場合

    std::vector<int> tidx(num);
    for (int i = 0; i < num; i++) {
        target[i] = rand();
    tidx[i] = i;
    }

    // 初期値
    std::cout << "original target\n";
    for (unsigned int i = 0; i < num-1; i++) {
        std::cout << target[i] << ",";
    }
    std::cout << target[num-1] << "\n";


    // インデックスソート
    //std::sort(tidx.begin(), tidx.end(), IndexSortFunctor<std::vector<int>::const_iterator >(target.begin(), target.end()) );
    //std::sort(tidx.begin(), tidx.end(), IndexSortFunctor<std::vector<int>::iterator >(target.begin(), target.end()) );

    // vectorの場合
    std::sort(tidx.begin(), tidx.end(), IndexSortCmp(target.begin(), target.end() ) );
    // 配列の場合
    //std::sort(tidx.begin(), tidx.end(), IndexSortCmp(target, target + num ) );


    // ソート結果
    std::cout << "sorted target index and target value\n";
    for (unsigned int i = 0; i < tidx.size()-1; i++) {
        std::cout << tidx[i] << ",";
    }
    std::cout << tidx.back() <<"\n";
    for (unsigned int i = 0; i < tidx.size()-1; i++) {
        std::cout << target[tidx[i]] << ",";
    }
    std::cout << target[tidx.back()] >> "\n";

    std::cout << "target after sorting process\n";
    for (unsigned int i = 0; i < num-1; i++) {
        std::cout << target[i] << ",";
    }
    std::cout << target[num-1] << "\n";

    // 配列の場合
    //delete [] target;

    return 0;
}

このサンプルプログラムでは、部分シーケンスのインデックスソートも行う場合を考慮して、対象シーケンスの先頭と終端の次の反復子を与えるようにしていますが、シーケンス全体を与えるクラスにすることも可能と思います。用途に応じて変更すれば良いかと思います。

また、上記のやり方以外にもいろいろな実現方法があると思われます。

たとえば、インデックスソートを行いたいシーケンスが、（C++の）一次元配列として与えられている場合を考えます。vectorを用意して、配列の各要素のポインタを格納しておきます。比較関数として、間接参照演算子（*）でポインタの内容を比較するようにして、std::sortを呼び出します。ソート後の結果として、、各vectorの要素の値（ポインタ）と配列の先頭アドレスの距離を引き算で求めれば、それによってもインデックスソートを得ることができるのではないかと思われます。（ただ、試してないので本当にうまくできるかは保障できません。）

（参考にしたサイト）

http://www.ddj.com/cpp/184401318

http://www.velocityreviews.com/forums/t283191-sort-and-get-index.html