現在, C++でSTLのsortを使って, sortしています. 本来, 欲しいものはsortされた配列ではなく, その添字の順番です. 例えば, v = {3,5,2,4,1}なら, 1,2,3,4,5}というsortされた配列でなく, idx = {4,2,0,3,1}という添字の順番が欲しいのです. STLのsortでは, このidxを返してくれないので, 一つclassを作って,

class A{
int v;
int no;
}
vector<A> tmp; やlist<A> tmp;
として, sort(tmp.begin(),tmp.end())やtmp.sort()したあとで, noからidxを作っています.

ただ, わざわざclass Aにコピーしてソートするので, メモリーもコピーする手間も無駄のような気がしてなりません.

このような無駄なことをしないで, 添字の順番を変える方法をご存知でしょうか?

回答の条件
  • 1人2回まで
  • 登録:2007/12/23 19:48:38
  • 終了:2007/12/30 19:50:02

回答(2件)

id:heart-rhythm No.1

heart-rhythm回答回数32ベストアンサー獲得回数12007/12/23 20:33:45

ポイント18pt

数値計算では必携の名著です。

こちらにそのアルゴリズムとソースが掲載されています。

こちらを参考にSTL版のルーチンを作るのはいかがでしょうか?

ニューメリカルレシピ・イン・シー 日本語版―C言語による数値計算のレシピ

ニューメリカルレシピ・イン・シー 日本語版―C言語による数値計算のレシピ

  • 作者: William H. Press William T. Vetterling Saul A. Teukolsky Brian P. Flannery
  • 出版社/メーカー: 技術評論社
  • メディア: 単行本

id:Q-tarou

ありがとうございます. 現在この書籍を所有していないので, どのようなアルゴリズムなのか分かりませんのですぐに対応はできませんが, 時間ができ次第, 参考にさせていただきます.

2007/12/23 21:41:25
id:pyopyopyo No.2

pyopyopyo回答回数342ベストアンサー獲得回数832007/12/23 21:37:18

ポイント52pt

必要なデータは 添字の順番 ということですので,

すなおに添字の順番をソートしたほうが良いと思います.

具体的には,以下のように関数オブジェクトを使って書きます.

#include <algorithm>

#include <iostream>
#include <iterator>

using namespace std;

// 関数オブジェクトのクラス
struct comp{
     bool operator()(const int& a, const int& b) const {
	  return v[a]<v[b];
     }
     comp(const int *p):v(p){}
private:
     const int *v;
};

int
main()
{
     const int v[]={3,5,2,4,1};
     
     int idx[]={0,1,2,3,4}; // 添字の配列

     // 並び変え前
     copy(&idx[0], &idx[5],  ostream_iterator<int> (cout, " "));
     cout << endl;

     // idx[] を並び替え
     sort(&idx[0], &idx[5], comp(v));

     // 並び変え後
     copy(&idx[0], &idx[5],  ostream_iterator<int> (cout, " "));
     cout << endl;

     return 0;
}

この書き方ですと,実際に書き変るのは idx[] だけです.

const で修飾しているように 元データ v[]自体は書き変らず,無駄なコピーも発生しません.

id:Q-tarou

ありがとうございます. 書いていただいたprogramの中には, 何点か私の知らない構文, 手法が使われているのですが, 頂いたprogramを参考にしながら, 理解しようと思います.

2007/12/23 21:44:10

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません