読者です 読者をやめる 読者になる 読者になる

sortのcomp関数

ちゃんと認識してなかったら4問セット中2問死にました
ここ参照http://en.cppreference.com/w/cpp/concept/Compare
c++にはconceptという(お蔵入りした)ものがあるらしく、呼び出したものが前提条件をみたすかどうかとかを確認するらしいのだが、ここではcomp関数がどういう条件を満たさねばならないか書きます(上のページに書いてあるけど)

  • !comp(a,a)=false
  • comp(a,b) -> !comp(b,a)
  • comp(a,b) && comp(b,c) -> comp(a,c)

また、equiv(a,b) <-> !comp(a,b) && !comp(b,a) とすると、

  • equiv(a,a)
  • equiv(a,b) -> equiv(b,a)
  • equiv(a,b) && equiv(b,c) -> equiv(a,c)

要は順序関係(=を含まない方の)ならいいのだが、これを満たさないとstdで例外が投げられてREが出(る可能性があり)ます!
例えば、

struct edge{int x,y,z;};

とした時に、

bool comp(const edge& l,const edge& r){
	if(l.x!=r.x) return l.x<r.x
	if(l.y!=r.y) return l.y<r.y
	return l.z<r.z;
}

ならいいのだが、xの大小だけsortすればあとはどうでもいいからといって、

bool comp(const edge& l,const edge& r){
	return l.x==r.x ? (true) : l.x<r.x;
}

とか書くと死にます

bool comp(const edge& l,const edge& r){
	if(l.x!=r.x) return l.x<r.x
	if(l.y!=r.y) return l.y<r.y
	return l.z<=r.z;
}

でも多分死にそう
std::stable_sortを使うとこれらの要件は消えているようである(cppreferenceによると)