Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-10-25

upper_bound と lower_bound(とdistance)

| 23:28 | upper_bound と lower_bound(とdistance) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - upper_bound と lower_bound(とdistance) - TopCoder煮ブログ

upper_bound と lower_bound が返す場所への理解が曖昧だったので、実証コードを書いて理解を深めた。

図にするとこんな感じ。

  1   1   3   3   5
  | upper_bound 0
          | upper_bound 1
          | upper_bound 2
                  | upper_bound 3

  1   1   3   3   5
  | lower_bound 0
  | lower_bound 1
          | lower_bound 2
          | lower_bound 3

upper_bound はその数を超える最初の場所を指す。lower_bound はその数以下の最大の数字を指す。同じ値が複数あった場合、upper_bound も lower_bound も先頭を指す。

以下、少し長いけど実証コード。イテレータの場所をインデックス番号で取得するために std::distance() を使ってみた。イテレータはポインタみたいに引き算で差分ができなくて悩んだ。


void main(){
    vector<int> v;
    v.push_back(1); v.push_back(1);
    v.push_back(3); v.push_back(3);
    v.push_back(5);

    vector<int>::iterator p;
    p = upper_bound(v.begin(), v.end(), 0);
    cout << distance(v.begin(), p) << endl; // 0
    p = upper_bound(v.begin(), v.end(), 1);
    cout << distance(v.begin(), p) << endl; // 2
    p = upper_bound(v.begin(), v.end(), 2);
    cout << distance(v.begin(), p) << endl; // 2
    p = upper_bound(v.begin(), v.end(), 3);
    cout << distance(v.begin(), p) << endl; // 4

    p = lower_bound(v.begin(), v.end(), 0);
    cout << distance(v.begin(), p) << endl; // 0
    p = lower_bound(v.begin(), v.end(), 1);
    cout << distance(v.begin(), p) << endl; // 0
    p = lower_bound(v.begin(), v.end(), 2);
    cout << distance(v.begin(), p) << endl; // 2
    p = lower_bound(v.begin(), v.end(), 3);
    cout << distance(v.begin(), p) << endl; // 2
}