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を使います。