最も長い名前のSTLアルゴリズム

もっとも長い名前って、どれくらいやねん。

set_symmetric_difference

えーと24文字です。長いですね。STL系は単語と単語を_(アンダーバー)でつなぐからなおさらですね。

どういう意味のアルゴリズムかというと、一つずつ英単語を見ていきましょう。

setは集合って意味ですね。
symmetricは対称的だの対称性だのそんな意味です。
differenceは違いとか差とか言う意味ですが、集合なんで『差』でしょうね。

直訳すると、集合の対称差アルゴリズムです。

対称差ってなんやねんとWikipediaで調べてみたら、
「どちらか一方の集合には含まれるが両方とも含まれることがないような元を集めてできた新たな集合」

だそうです。式を描くと
PΔQ=(P∪Q)＼(P∩Q)=(P＼Q)∪(Q＼P)
のようです。＼は、左の集合から右の集合を削除したものといった意味です。

ベン図で描くと、PまたはQから、PかつQの領域を省いた集合となります。

長々と書きましたが、それをやってくれちゃうのが、この長い名前のアルゴリズムです。

…まぁ、ここまでわかっちゃうと、もう、解説することがないんですけど、注意点としてそれぞれの集合はソート済みであることが事前条件として要求されます。

ちなみに戻り値は、結果の末尾を表す反復子です。

サンプルコード書きます。ここでは集合はあらかじめソート済みなの用意しときます。
非ソート済みならば、sort関数等でソートしてから使ってください。配列長はめんどいので決め打ちにしてます。実際に使う際には必要に応じて配列長をはじき出してください。

サンプルコード

#include

#include

#include
using namespace std;


int main(){

	int  set1[] = {1,3,5,7,9};//集合1

	int  set2[] = {1,2,3,4,5};//集合2

	

	//とりあえず集合のでかさがわかってるんで、多きさ10のベクタ用意しとく

	vector set_result(10);

	

	//あらかじめでかさが分からない場合には挿入子を使うのもいいかもしれません。

	vector::iterator ret_it = set_symmetric_difference(set1,set1+5,set2,set2+5,set_result.begin());

	

	vector::iterator it= set_result.begin();

	vector::iterator itEnd = set_result.end();

	//endまで見てみる

	for(;it!=itEnd;++it){

		cout << *it << ",";

	}

	cout << endl;

	

	//アルゴリズム関数の戻り値＝末尾なので、それを利用してみる

	for(it=set_result.begin();it!=ret_it;++it){

		cout << *it << ",";

	}

	cout << endl;

	return 0;

}

出力結果
2,4,7,9,0,0,0,0,0,0,
2,4,7,9,

え？コンパイラがないですか？そんな人は、http://codepad.org/を活用すると面倒な手間をかけることなくテストできますので、是非活用しましょう。