人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

現在, 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にコピーしてソートするので, メモリーもコピーする手間も無駄のような気がしてなりません.

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

●質問者: Q-tarou
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:BEGIN C++ Class STL Vector
○ 状態 :終了
└ 回答数 : 2/2件

▽最新の回答へ

1 ● heart-rhythm
●18ポイント

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

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

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

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

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

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

◎質問者からの返答

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


2 ● pyopyopyo
●52ポイント

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

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

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

#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[]自体は書き変らず,無駄なコピーも発生しません.

◎質問者からの返答

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ