自前のクラスでsortをする

自前のクラスでsortをするとき、自前のクラスにてオペレータ<を定義してあげないといけない。

なぜならsortは、オペレータ<を用いてソートを行うからである。

ということで、見本を。

例の如く、PKUからの出題。今回は、2376 Cleaning Shiftsという問題。あーこんな問題TopCoderでもあったなー。ソートしてgreedyで解きます。

ソースはこんな感じ。

view plainprint?

1. class Shift {  
2. public:  
3. int s;  
4. int e;  
5. Shift(int s, int e) {  
6. this->s = s;  
7. this->e = e;  
8. }  
9. bool operator<(const Shift &shift) const {  
10. return this->s < shift.s;  
11. }  
12. };  
13.   
14. int main() {  
15. int N, T;  
16. cin >> N >> T;  
17.   
18. int s, e;  
19. vector<Shift> cows;  
20. REP(i, N) {  
21. cin >> s >> e;  
22. cows.PB(Shift(s,e));  
23. }  
24. SORT(cows);  
25.   
26. int p = 0;  
27. int up = 0;  
28. int ret = 0;  
29. while(p < N) {  
30. int max = -1;  
31. for (;p < N; p++) {  
32. if (cows[p].s > up + 1)  
33. break;  
34. max = MAX(max, cows[p].e);  
35. }  
36. if (max == -1)  
37. break;  
38. ret++;  
39. up = max;  
40. if (up == T)  
41. break;  
42. }  
43. printf("%d\n", (up == T) ? ret : -1);  
44. return 0;  
45. }  

class Shift {
public:
int s;
int e;
Shift(int s, int e) {
this->s = s;
this->e = e;
}
bool operator<(const Shift &shift) const {
return this->s < shift.s;
}
};

int main() {
int N, T;
cin >> N >> T;

int s, e;
vector<Shift> cows;
REP(i, N) {
cin >> s >> e;
cows.PB(Shift(s,e));
}
SORT(cows);

int p = 0;
int up = 0;
int ret = 0;
while(p < N) {
int max = -1;
for (;p < N; p++) {
if (cows[p].s > up + 1)
break;
max = MAX(max, cows[p].e);
}
if (max == -1)
break;
ret++;
up = max;
if (up == T)
break;
}
printf("%d\n", (up == T) ? ret : -1);
return 0;
}

Shiftというクラスでオペレータを定義していますね。このようにクラスの中で<を定義してあげないとsortは使えません。

ここで注意しないといけないのはconstってちゃんと書かないといけない（※引数部と関数部に２ヵ所書かないとダメです。）ということです。constを書かないとoperatorとして認識してくれないようで、コンパイラエラーになってしまいます。

じゃ、constって2つあるけどどう違うの？

引数のconstは引数の値を関数内で変更しないっていう意味です。引数が、参照渡しになっているため、関数内で値を書きかえることができるんですね。。値が変えられると困るのでconstって書いています。

では、そもそも何故引数は、参照渡しなの？んーいい質問です。プリミティブ型（int, doubleなど基本的な型）の場合は、関数に値をするのが基本ですが、構造体やクラスを渡すときはポインタ渡しや参照渡しを行います。これはメモリ量を節約するためです。（クラスそのものを渡すより、クラスのアドレスを渡した方がメモリが節約できますよね！）

で、まー大体こんな風に使い分けるのが基本です。

	引数を変更するとき	引数を変更しないとき
プリマティブ型	値渡し	値渡し
構造体、クラス	ポインタ渡し	参照渡し（constを付けます。）

で、関数についているconst。これは、メンバ関数内でオブジェクトのメンバ変数を変更しないということを意味しています。さらに、constがついた関数からはconstがついていない関数を呼び出すことができません。（呼び出せてしまうと、constじゃない関数の中で値を変えることができてしまい、constの意味がなくなりますね。）

つまり、このconstは、大小を比較する際に、自分のメンバ変数を変えることを禁止しているんですね。

ということで、まとめると、

• 変数部のconstは、比較相手のメンバ変数の値が変わるのを防ぐ。
• 関数部のconstは、自身のメンバ変数の値が変わるのを防ぐ。

っていう意味ですね。確かに、大小比較するんだから、値が変わらないことを担保するのは当然と言えば当然。