読者です 読者をやめる 読者になる 読者になる

プログラマーのメモ書き

伊勢在住のプログラマーが気になることを気ままにメモったブログです

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

プログラム関連 C/C++

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