class A{
int v;
int no;
}
vector<A> tmp; やlist<A> tmp;
として, sort(tmp.begin(),tmp.end())やtmp.sort()したあとで, noからidxを作っています.
ただ, わざわざclass Aにコピーしてソートするので, メモリーもコピーする手間も無駄のような気がしてなりません.
このような無駄なことをしないで, 添字の順番を変える方法をご存知でしょうか?
数値計算では必携の名著です。
こちらにそのアルゴリズムとソースが掲載されています。
こちらを参考にSTL版のルーチンを作るのはいかがでしょうか?
ニューメリカルレシピ・イン・シー 日本語版―C言語による数値計算のレシピ
必要なデータは 添字の順番 ということですので,
すなおに添字の順番をソートしたほうが良いと思います.
具体的には,以下のように関数オブジェクトを使って書きます.
#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を参考にしながら, 理解しようと思います.
ありがとうございます. 現在この書籍を所有していないので, どのようなアルゴリズムなのか分かりませんのですぐに対応はできませんが, 時間ができ次第, 参考にさせていただきます.