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とupper_boundにstd::less_equalを渡したもの、lower_boundにstd::less_equalを渡したものとupper_boundはそれぞれ同じ結果が得られるわけです。
図にするとこんな感じですね。
今まで混乱してたのは、upper_boundが条件を見たす最大の要素(この例だとkey=2の時に3番目の要素)を指すイテレータを返すと思い込んでたのが原因だということが、良く分かりました。*2*3
ここまで書いてeffective STLにものすごく分かり易い説明が載ってたような気がしてきた・・・orz