HPCメモ

HPC(High Performance Computing)に関連したりしなかったりすることのメモ書き

lower_boundとupper_bound

STlの便利アルゴリズムlower_boundとupper_boundですが、何回説明を読んでも混乱するので、自分でテストプログラムを書いてみました。

とりあえずコード

vector<int> v={0,2,2,4,6};
cout << "v = {";
std::for_each(v.begin(), v.end()-1,[](int x)->void {cout<<x<<",";});
cout<<*(v.end()-1)<<"}"<<endl;
cout<<endl;
cout<<"lower_bound(1) = "<<distance(v.begin(), lower_bound(v.begin(), v.end(), 1))<<endl;
cout<<"upper_bound(1) = "<<distance(v.begin(), upper_bound(v.begin(), v.end(), 1))<<endl;
cout<<"lower_bound(2) = "<<distance(v.begin(), lower_bound(v.begin(), v.end(), 2))<<endl;
cout<<"upper_bound(2) = "<<distance(v.begin(), upper_bound(v.begin(), v.end(), 2))<<endl;
cout<<"lower_bound(4) = "<<distance(v.begin(), lower_bound(v.begin(), v.end(), 4))<<endl;
cout<<"upper_bound(4) = "<<distance(v.begin(), upper_bound(v.begin(), v.end(), 4))<<endl;

0,2,2,4,6という5要素が昇順で並んでいるvectorに対して、

  • 1:コンテナ内には無い値
  • 2:コンテナ内に複数存在する値
  • 4:コンテナ内に1つだけ存在する値

をそれぞれlower_boundとupper_boundで探索します。

結果を見る前に、cppreference.comの説明を読んでみましょう。

http://en.cppreference.com/w/cpp/algorithm/lower_bound

Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value.

lower_boundはvalue以上となる最初の要素を指すイテレータを返す

http://en.cppreference.com/w/cpp/algorithm/upper_bound

Returns an iterator pointing to the first element in the range [first, last) that is greater than value.

upper_boundはvalueより大となる最初の要素を指すイテレータを返す
なるほど、分からんヽ(゚Д゚)ノ

テスト結果はこんな感じ。

v = {0,2,2,4,6}

lower_bound(1) = 1
upper_bound(1) = 1
lower_bound(2) = 1
upper_bound(2) = 3
lower_bound(4) = 3
upper_bound(4) = 4

ややこしいのでここ以降の文章ではlower_bound, upper_boundの第三引数で渡した値を "key" とします。
key=1の時は、1つ目の2が最初にkey以上になり、かつkeyより大にもなるので
どちらも、この2を指すイテレータを返しています(begin()とのdistanceが1となっている)
key=2の時は、1つ目の2が最初にkey以上になるので、lower_boundは1つ目の2を指すイテレータを返していますが
keyより大となるのは4の時なので、4を指すイテレータを返しています。
key=4の時は、最初にkey以上になるのは4,keyより大となるのは6なので、lower_boundでは前者を、upper_boundでは後者を指すイテレータを返します。

ところで、lower_bound, upper_boundともにプレディケートを渡して、比較方法を変えることができます。
ここにstd::less_equalを渡すと次のような結果になります。

lower_bound(1,le) = 1
upper_bound(1,le) = 1
lower_bound(2,le) = 3
upper_bound(2,le) = 1
lower_bound(4,le) = 4
upper_bound(4,le) = 3

最初の結果と違うのは、keyが2,4の時。つまりkeyがコンテナ内に存在する時です。
つまり、lower_boundは最初にkeyより大となる要素へのイテレータを返し、upper_boundでは最初にkey以上となる要素へのイテレータを返しています。


ここらで、ちょっと規格*1を見てみると
lower_boundは

Returns: The furthermost iterator i in the range [first,last] such that for any iterator j in the
range [first,i) the following corresponding conditions hold: *j < value or comp(*j, value) !=
false.

upper_boundは

Returns: The furthermost iterator i in the range [first,last] such that for any iterator j in the
range [first,i) the following corresponding conditions hold: !(value < *j) or comp(value, *j)
== false.

となってます。

つまり、

  • lower_bound:comp(*j, value)が偽とならない最大の要素を指すイテレータを返す
  • upper_bound:comp(value, *j)が偽となる最大の要素を指すイテレータを返す

となっていて、比較の条件式は、両者の間で右辺と左辺が入れかわる上に、真偽判定が逆になる(結局境界値以外は同じ結果になる)ということが分かります。
ということは、lower_boundとupper_boundにstd::less_equalを渡したもの、lower_boundにstd::less_equalを渡したものとupper_boundはそれぞれ同じ結果が得られるわけです。
図にするとこんな感じですね。

f:id:n_so5:20140115004354p:plain

今まで混乱してたのは、upper_boundが条件を見たす最大の要素(この例だとkey=2の時に3番目の要素)を指すイテレータを返すと思い込んでたのが原因だということが、良く分かりました。*2*3

ここまで書いてeffective STLにものすごく分かり易い説明が載ってたような気がしてきた・・・orz

*1:といいつつC++ commiteeが公開しているfinal draftの方だけど

*2:要はend()みたいに範囲の最後をひとつ踏み越したイテレータを返すものなわけか。

*3:equal_rangeでもらったイテレータのペアでforループを回すことを考えるとこうなってるのも当然って気がするが・・・思い込みって怖いわ~