Home > C++ > C++トリビアルメモ6 STLのsort

C++トリビアルメモ6 STLのsort

  • 2008-07-01 (火) 22:57
  • C++

そろそろSTLのsortについてまじめに語ろうと思う。
でもごめん。余白が足りないのであんまり書けない。

まず、簡単な使い方。
サンプル1:


#include <vector>
#include <algorithm>
using namespace std;

vector< int > target;

target.push_back(3);
target.push_back(1);
target.push_back(4);
target.push_back(0);
target.push_back(2);

sort(target.begin(), target.end());

結果は0,1,2,3,4になる。sortの引数はランダムアクセスイテレータなら何でもよく、vectorじゃなくてもdaqueでもいいし、配列のポインタでもいい。ただし、ソートの範囲は第2引数の終端を含まないので注意が必要。vectorとかのend()は最終要素の一つ先を指しているから上記で問題ない。(配列でやるときは無理矢理一歩先を入れればいいのかな??)
サンプル2:


#include <algorithm>   // for "sort"
using namespace std;

int target[5];

target[0] = 3;
target[1] = 1;
target[2] = 4;
target[3] = 0;
target[4] = 2;

sort(&(target[0]), &(target[4]));

0,1,3,4,2になる。&(target[4])を&(target[5])にすれば、VC2008ではサンプル1と同じ結果になった。

で、前置きはこれくらいにして、書きたかったのは自前の比較関数について。その前にまず、サンプル1は以下のサンプル3と全く同じであることを押さえておく。
サンプル3:


#include <vector>
#include <algorithm>   // for "sort"
#include <functional>   // for "less"

std::vector< int > target;

target.push_back(3);
target.push_back(1);
target.push_back(4);
target.push_back(0);
target.push_back(2);

std::sort(target.begin(), target.end(), std::less< int >());

namespaceのstdを復活させてみたのはlessのnamespaceを明示するため。ようするにサンプル1のsortはデフォルトで比較関数にlessを使っているということ。したがって自前の比較関数を使いたい場合はこのlessの代わりになるような物を作ればいい。lessっていうのはつまり<。小なりで比較する。なので、比較関数というとちょっと語弊がある。一般に(C言語とかPHPで)比較関数というと、


int cmp(int a, int b) {
   if (a < b) {
      return -1;
   } else if (a == b) {
      return 0;
   } else {
      return 1;
   }
}

というように第1引数が第2引数より小さいときに-1、等しいときに0、大きいときに1を返すのが普通(昇順ソートの場合)。たいてい、


int cmp(int a, int b) {
   return a - b;
}

でも間に合う。a、bがint型じゃないときは型にあわせてa-bを定義するようなイメージがある。しかし、stlのsortに対して同じようなイメージで比較関数を作るとハマル。なぜならless< int >(a, b)はa < bの時にtrueを返すから。そもそもlessの戻り値はboolであり、昇順ソートにするためにはa - bが負になるときにtrueを返さないといけなく、a - bが正になるときおよび0になるときにfalseを返さないといけない。降順ソートしたい場合は逆の真偽値にすればよいので、降順ソートにする場合は次のようなtestcmpを定義すればよい。
サンプル4:


bool testcmp(int a, int b) {
	if (a > b) {
		return true;
	} else {
		return false;
	}
}

std::sort(target.begin(), target.end(), testcmp);

もっとも、本当に降順ソートしたいだけなら自分で定義しなくてもstd::greater< int >()を使った方がいい。

サンプル4だとC言語のqsort使ってるのと同じような感じであるが、せっかくC++、STLなので関数オブジェクトを利用した方がいい。
サンプル5:


struct testcmp {
	bool operator()(int a, int b) const {
		if (a > b) {
			return true;
		} else {
			return false;
		}
	}
};

std::sort(target.begin(), target.end(), testcmp());

関数オブジェクトはoperator()をオーバーロードした物で、ソートのための比較オブジェクトを作るためには引数を二つ取るoperator()を作ればいい。関数オブジェクトはオブジェクトでありながらoperator()が定義されているが故に関数みたいに使える物である。関数オブジェクトにすることで比較部分がinline化されるため、より高速にソートできるようになる。上記はstructで作成したが当然classでもいい。ただし、publicをつける(structだと勝手にpublicになる)。
サンプル6:


class testcmp {
public:
	bool operator()(int a, int b) const {
		if (a > b) {
			return true;
		} else {
			return false;
		}
	}
};

testcmp mycmp;
bool result1 = mycmp(3, 1);   // true
bool result2 = mycmp(1, 2);   // false

std::sort(target.begin(), target.end(), mycmp);

サンプル6のようにインスタンス化してからsortの第3引数に渡すこともできるが、これだとたぶんinline化されないんじゃないかと思う(よく知らない)。

たぶん、すぐ忘れるので今のうちにメモっておいた。

以上

Comments:0

Comment Form
Remember personal info

Trackbacks:0

Trackback URL for this entry
http://red-treasure.com/report/wp-trackback.php?p=245
Listed below are links to weblogs that reference
C++トリビアルメモ6 STLのsort from コスミー報告書[社外秘]

Home > C++ > C++トリビアルメモ6 STLのsort

Search
Feeds
Meta
 合計:000854
 今日:0085 昨日:0199

Return to page top