45項 count、find、binary_search、lower_bound、upper_bound、およびequal_rangeの違いを理解しよう

count、find、binary_search、lower_bound、upper_bound、およびequal_rangeの違いを理解しよう

本書にまとまった表が載っていたので、引用します。

何を知りたいか	使用するアルゴリズム		使用するメンバ関数
	未ソートの範囲	ソート済みの範囲	setまたはmap	multisetまたはmultimap
必要な値が存在するか	find	binary_search	count	find
必要な値の最初の位置	find	equal_range	find	findまたはlower_bound
必要な値以上の値の最初の位置	find_if	lower_bound	lower_bound	lower_bound
必要な値より大きい値の最初の位置	find_if	upper_bound	upper_bound	upper_bound
必要な値の数	count	equal_range	count	count
必要な値のすべての位置	find(繰り返し)	equal_range	equal_range	equal_range

必要な値が存在するかを調べるのにcountを使っているのは、setが要素の重複を許さないため、countの戻り値が1か0かで存在を調べられるからです。

multisetまたはmultimapの必要な値の最初の位置を調べるとき、同じ値が複数存在すると、findの返す要素が最初の要素であるという保証はありません。
同じ値が複数存在する可能性があるときは、lower_boundを使います。