知ってると便利なSTL(8) lower_bound、upper_bound

知ってると便利なSTLシリーズ第8弾。

今回は、○○以上の要素、○○より大きい要素の位置を返すlower_boundとupper_boundについて。

より厳密に説明すると、

lower_bound(x,y,p)は、整列済みコンテナ[x, y)の中から、与えられた値p以上となる要素の位置を返します。

upper_bound(x,y,p)は、整列済みコンテナ[x,y)の中から、与えられた値pより大きくなる要素の位置を返します。

百聞は一見に如かずということで、サンプルソース。

#define SIZE(buff) (sizeof(buff)/sizeof(buff[0]))

int main() {
  int x[] = {0,1,1,2,2,2,4,5,5,10};

  int p1 = (lower_bound(x, x+SIZE(x), 4) - x);
  int p2 = (upper_bound(x, x+SIZE(x), 4) - x);

  printf("x[%d] =%d >= %d\n", p1, x[p1], 4);
  printf("x[%d] =%d > %d\n", p2, x[p2], 4);
  return 0;
}

実行結果：

x[6] (=4) >= 4

x[7] (=5) > 4

さらに、逆順にソートされたコンテナから、○○以下になる要素の位置、○○より小さくなる要素の位置を取り出したいという場合もあるかと思います。そういう場合は、予めコンテナを取得または定義する段階で、マイナスを付けておくといいです。

int main() {
    // The original sequence is: {10,8,8,7,5,5,5,3,1}
    int x[] = {-10,-8,-8,-7,-5,-5,-5,-3,-1};

    int p1 = lower_bound(x, x+SIZE(x), -5) - x;
    int p2 = upper_bound(x, x+SIZE(x), -5) - x;

    printf("x[%d] (=%d) <= %d\n", p1, -x[p1], 5);
    printf("x[%d] (=%d) < %d\n", p2, -x[p2], 5);

    return 0;
}

これだけでは、この関数のありがたみが感じられません。何が嬉しいかというと、○○以上の要素や、○○より大きい要素の位置が対数時間で分かるということです。例えば、最長増加列の問題を高速に解きたい場合は、lower_boundが有効です。