lower_bound,upper_bound(C++)

lower_boundとupper_bound

lower_boundとupper_boundはソート済みSTLコンテナにおいて、それぞれ、指定の値以上の値が最初に現れる位置と、指定の値より大きい値が最初に現れる位置のイテレーターを取得する。図にするとこんな感じ。

コンテナ境界周りの動作仕様

1) begin()から--itするとどうなるか
beginとのdistanceをとると-1だが、イテレーターの指している場所は中身のデータ参照結果は不定。
2) end()から--itするとどうなるか
要素数が1以上あれば、イテレーターは最後の要素を指し、中身のデータ参照可能。要素数が0なら、1)と同じ。
3) end()から++itするとどうなるか
beginとのdistanceをとると+1されているが、イテレーターは不定値になり中身のデータ参照結果は不定。

upper_boundと階段関数

以下のような階段関数をコンテナで表現する場合を考える。

以下、疑似コードである。

vector<pair<int,int>> v; // (x,y)のペア

v.push_back(make_pair<0,y0>);
v.push_back(make_pair<x1,y1>);
v.push_back(make_pair<x2,y2>);

任意のxに対するyの値は、upper_bound(x)で求めたiterator itに対して--itしたペアのyの値を参照すれば良い。
lower_bound(x)で使った場合はダメで、例えばlower_bound(x2)は3番目のペアを表し、--itすると2番目のペアを指すことになってしまうからである。
lower_bound(x)を使った場合は図で白丸と黒丸を逆転させた階段関数に相当する。