読者です 読者をやめる 読者になる 読者になる

Pebble's Diary

プログラマーの作業メモ

lower_bound,upper_bound(C++)

C++11

lower_boundとupper_bound

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

f:id:pebble8888:20160707221323p:plain

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

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

upper_boundと階段関数

以下のような階段関数をコンテナで表現する場合を考える。 f:id:pebble8888:20160707224803p:plain

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

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)を使った場合は図で白丸と黒丸を逆転させた階段関数に相当する。