STLのset

今日はC++STLのsetを使ってみた。

set::eraseがvoidなのが理解出来ない。なぜiteratorを返さないのか。まとめて複数の要素を削除したいときとか、不便じゃないのか。逆にinsertの方はboolで良いと思う。map::eraseも同じ。

さらに、setクラスにはメンバ関数として、isSubsetOf(set)があっても良いのではないか。集合の包含関係は順序(厳密弱順序と言うらしい)にはならないのでoperator<は今のままで良いと思うが、operator+, operator-, operator* もあって良いと思う。

#include <set>
template <typename Key, typename Compare1, typename Allocator1, typename Compare2, typename Allocator2>
bool isSubset(const std::set<Key, Compare1, Allocator1>& A, const std::set<Key, Compare2, Allocator2>& B){
	for(typename std::set<Key, Compare1, Allocator1>::const_iterator i=A.begin(); i != A.end(); ++i){
		if(B.find(*i) == B.end()){
			return false;
		}
	}
	return true;
}

template <typename Key, typename Compare, typename Allocator1, typename Allocator2>
bool isSubset(const std::set<Key, Compare, Allocator1>& A, const std::set<Key, Compare, Allocator2>& B){
	typename std::set<Key, Compare, Allocator1>::const_iterator i = A.begin();
	typename std::set<Key, Compare, Allocator2>::const_iterator j = B.begin();
	
	while(i != A.end()){
		if(j == B.end() || Compare()(*i, *j)){
			return false;
		}
		else if(*i == *j){
			++i;
			++j;
		}
		else{
			++j;
		}
	}
	return true;
}

みたいな感じ。

あと、binary_searchに渡すiteratorってForwardIteratorで良くて、RandomAccessIteratorである必要は無いみたいで、実際setに対しても出来るみたいだが、なぜだろう。beginとendの中間点が計算出来ないとbinary_search出来ないように思うんだけれど、ForwardIteratorじゃ、そこまでひたすらインクリメントしないといけないのでは？(たしかにSGIのコードを見るとそうなっている、、、binary_searchなのに計算量が log n でないらしい)